Is Python's in operator slow? (From ABC167D)

It is said that using ʻin (using ʻin in a loop) every time when repeatedly judging "whether there is an element in the list" may be slow. From the conclusion, it seems that ʻin itself is not slow, but" searching in the list using ʻin is slow." I had noticed it lightly, but it was probably the first time I realized such a difference in speed.

A similar program submitted in ABC167D below, but the first was an on-parade of TLE by searching the list using ʻin in a loop. On the other hand, the second one creates a separate list for flags and processes it, and it is lightly ʻAC (139ms). In addition, the third is an experiment based on the advice of a kind person, "You should set the search target to set instead of list". This also easily became ʻAC` (188ms).

AtCoder Beginner Contest 167 D - Teleporter

ABC167D/TLE

n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #List of towns (including the first) I have visited so far
twn = 1 #Teleporter transfer destination
for _ in range(k):
    if a[twn - 1] not in dst: #If the teleporter transfer destination is not on the list of towns you have visited
        dst.append(a[twn - 1]) #If not, add it to the list of towns you have visited
        twn = a[twn - 1] #Update teleporter transfer destination
    else: #If the teleporter transfer destination is in the list of towns you have visited so far (the transfer destination from there will loop)
        index = dst.index(a[twn - 1]) #Get the index of the teleporter transfer destination in the town list you have done so far
        ld = len(dst[:index]) #Find the length before looping and the period of the loop part
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

ABC167D/AC139ms

n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n #Flag list of whether you went to each town(True if not gone)
dst = [1]
twn = 0 #Teleporter transfer destination(Flag list index)
for _ in range(k):
    if flg[twn]:
        dst.append(a[twn])
        flg[twn] = False
        twn = a[twn] - 1
    else:
        index = dst.index(a[twn])
        ld = len(dst[:index])
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

ABC167D/AC188ms

n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #List of towns (including the first) I have visited so far
dsts = set(dst) #Set of towns (including the first) I have visited so far
twn = 1 #Teleporter transfer destination
for _ in range(k):
    if a[twn - 1] in dsts: #If the teleporter transfer destination is in the town set you have been to (transfers from there will loop)
        index = dst.index(a[twn - 1]) #Get the index of the teleporter transfer destination in the town list you have done so far
        ld = len(dst[:index]) #Find the length before looping and the period of the loop part
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
    else: #If the teleporter transfer destination is not in the town set you have been to
        dst.append(a[twn - 1]) #If not, add it to the list of towns you have visited
        dsts.add(a[twn - 1])
        twn = a[twn - 1] #Update teleporter transfer destination
print(dst[-1])

Conclusion If you want to determine the presence or absence many times in a loop, instead of searching the target list directly using ʻin, use ʻin to check a separately created search set, or use ʻin` for flags. It is overwhelmingly faster to make a list and look it up.