Pythonのリストよりもセットを速くするには？

Question

python wikiは次のように言っています： "セットと辞書を使ったメンバシップテストは、シーケンスを検索するよりもはるかに高速です、O（1）、" a in b "をテストする場合、bはaリストまたはタプル。

私はコードの中でスピードが重要なときは常にリストの代わりにセットを使用していましたが、最近セットがリストよりもずっと速いのかと思っています。誰かが説明するか、説明するソースに私を指摘することができますか、セットをより速くするために、Pythonのシーンの裏で正確に何が起こっているのでしょうか？

Answer 1

hash tablesを使用して設定します。オブジェクトをセットに追加するたびに、setオブジェクトのメモリ内の位置は、追加するオブジェクトのハッシュを使用して決定されます。メンバシップをテストするとき、基本的には、オブジェクトがハッシュによって決定された位置にあるかどうかを調べるだけです。したがって、この操作の速度はセットのサイズに依存しません。対照的に、リストの場合は、リスト全体を検索する必要があります。リストが大きくなるにつれて、リストの作成が遅くなります。

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

集合は一般的にリストより高速ではないことに注意してください。メンバーシップテストは集合に対してより高速であり、要素を削除することもできます。これらの操作を必要としない限り、リストはしばしばより高速です。

Answer 2

PythonはO（1）ルックアップを持つhashtablesを使用します。

Answer 3

私はあなたがデータ構造に関する本をよく見てみる必要があると思います。基本的に、Pythonリストはdynamic arraysとして実装され、セットはhash tablesとして実装されています。

これらのデータ構造の実装は、根本的に異なる特性を与えます。例えば、ハッシュテーブルは非常に高速の検索時間を有するが、挿入の順序を保持することはできない。

Answer 4

リストを1つずつ検索する必要があります。セットまたは辞書には、検索を高速化するためのインデックスがあります。

Answer 5

list：あなたのクローゼットの中にあなたの靴下を探しているが、あなたはあなたの靴下をドロワーているかわからない想像はしているので、あなたは、あなたがそれらを見つけるまで引き出しによって引き出しを検索する必要が（または多分あなたは決してしません）。これは最悪の場合、すべての引き出しを見ることになります（nは引き出しの数です）。O(n)と呼んでいます。

set：さて、あなたはまだあなたのクローゼットの中にあなたの靴下を探している想像しますが、今はここで、あなたの靴下があるドロワー第三引き出しの中に言うのを知っています。したがって、すべての引き出しを検索するのではなく、3番目の引き出しを検索するだけです。それは最悪のシナリオでは1つの引き出しを見るため、O(1)と呼ばれています。

Answer 6

これまでのところ、Pythonでパフォーマンスに関連するものは何も測定していませんが、リストはしばしば高速であることを指摘したいと思います。

はい、O（1）とO（n）があります。しかし、これは何かの漸近的な行動についてのみ情報を与えることを常に忘れないでください。つまり、あなたのnが非常に高い場合、O（1）は常に理論的により高速になります。しかし実際には、nはしばしば通常のデータセットよりもはるかに大きくなる必要があります。

したがって、多くの要素を処理する必要がある場合にのみ、リスト自体がリストよりも高速になるわけではありません。