[解決済み] リストよりセットの方が速いのはなぜか？

質問

Pythonのwikiによると、"集合や辞書を使ったメンバシップテストは配列を検索するO(n)よりもずっと速く、O(1)です。a in b"をテストするとき、bはリストまたはタプルではなく、セットまたはディクショナリでなければなりません。

私は自分のコードで速度が重要なときはいつでもリストの代わりにセットを使用してきましたが、最近、なぜセットがリストよりはるかに速いのか不思議に思っています。誰かが説明するか、または説明するソースに私を指して、正確にセットをより速くするためにpythonの舞台裏で何が起こっているのでしょうか？

どのように解決するのですか？

セットの実装は ハッシュテーブル . オブジェクトをセットに追加すると、そのオブジェクトのメモリ内での位置が set オブジェクトのメモリ内での位置は、追加されるオブジェクトのハッシュを使用して決定されます。 メンバシップのテストでは、基本的にそのハッシュで決められた位置にオブジェクトがあるかどうかを調べるだけなので、この処理の速さはセットのサイズに依存しない。 これに対してリストの場合は、リスト全体を検索する必要があり、リストが大きくなるにつれて遅くなる。

これは、セットが追加したオブジェクトの順序を保持しない理由でもあります。

メンバシップテストはセットでは速く、要素の削除も速いです。 これらの操作を必要としない限り、リストの方が速いことが多いのです。