Pythonのin演算子は遅いのか？ (ABC167Dより)

「リストの中に或る要素が有るかどうか」を繰り返し判断するような場合、毎回inを使う（ループの中でinを使う）と遅くなるのではないかという話。
結論から言うと、inそのものが遅いというよりは「inを使ってリスト内を検索するのが遅い。」ということらしい。うすうす気づいてはいたが、これだけの速さの違いを実感したのはたぶん初めて。

以下ABC167Dで提出した似たようなプログラムだが、1つ目はループの中でinを使ってリスト内を検索しTLEのオンパレードとなった。それに対し、2つ目は別にフラグ用のリストを作って処理し、軽々AC(139ms)となっている。また、3つ目は親切な方の「検索対象をlistでなくsetにすればいい」とのアドバイスにより実験したもの。これも楽々AC(188ms)となった。

AtCoder Beginner Contest 167 D - Teleporter

ABC167D/TLE

n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #今まで行った町（最初も含む）のリスト
twn = 1 #テレポーター転送先
for _ in range(k):
    if a[twn - 1] not in dst: #テレポーター転送先が今まで行った町リストに入っていなかったら
        dst.append(a[twn - 1]) #入っていなかったら今まで行った町リストに追加
        twn = a[twn - 1] #テレポーター転送先の更新
    else: #テレポーター転送先が今まで行った町リストに入っていたら（そこから先の転送先はループする）
        index = dst.index(a[twn - 1]) #今まで行った町リストでのテレポーター転送先のindex取得
        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/AC139ms

n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n #各町に行ったかどうかのフラグリスト(行ってなかったらTrue)
dst = [1]
twn = 0 #テレポーター転送先(フラグリストの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] #今まで行った町（最初も含む）のリスト
dsts = set(dst) #今まで行った町（最初も含む）のset
twn = 1 #テレポーター転送先
for _ in range(k):
    if a[twn - 1] in dsts: #テレポーター転送先が今まで行った町setに入っていたら（そこから先の転送はループする）
        index = dst.index(a[twn - 1]) #今まで行った町リストでのテレポーター転送先のindex取得
        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()
    else: #テレポーター転送先が今まで行った町setに入っていなかったら
        dst.append(a[twn - 1]) #入っていなかったら今まで行った町リストに追加
        dsts.add(a[twn - 1])
        twn = a[twn - 1] #テレポーター転送先の更新
print(dst[-1])

結論
ループの中で何回も有無の判断をする場合は、目的のリストを直接inを使って調べるのではなく、別に作った検索用setをinを使って調べるか、フラグ用のリストを作ってそれで調べたほうが圧倒的に速い。