私は〜30の浮動小数点数のリストを持っています。特定のフロートが私のリストにあるかどうかを確認したい。例えば：私のコードでPython：アイテムがリスト内にあるかどうかを検索するより速い選択肢
1 >> # For the example below my list has integers, not floats
2 >> list_a = range(30)
3 >> 5.5 in list_a
False
4 >> 1 in list_a
True
ボトルネックは、アイテムが私のリストに何回ある場合、私は、検索ライン3である、と私はより高速な代替手段を必要としています。このボトルネックは私の時間の99％以上を占めます。
リストの代わりにlist_aをセットするとコードを高速化できました。このラインを大幅にスピードアップする他の方法はありますか？
リストがソートされていない場合、要素がリストに含まれているかどうかを確認する最善の時間は、要素がどこにあっても各項目を見て、探しているかどうかを確認する必要があるためO（n）
アレイがソートされている場合は、バイナリ検索を使用してO（ログn）ルックアップ時間を持つことができます。また、ハッシュマップを使用して平均O（1）ルックアップ時間を持たせることもできます（または基本的には同じタスクを実行する辞書である組込みセットを使用できます）。
しかし、それは長さ30のリストにはあまり意味がありません。
なぜ誰かがこれを落としたのか不思議です。 –
私は有権者の一人です。私の理由は次のとおりです。1.組み込みの 'set'は検索ツリーのようなものではなく、' O（1） 'の償却された検索複雑さを持つハッシュテーブルです。 ';あなたの投稿は最高のコメントです。 –
@EliKorvigo私は理由1で大丈夫ですが、コメントについての事は私が共有していません。この答えはコードを示しておらず、短いかもしれませんが、多くの重要な事項（下限、ソートベースの検索、漸近複雑さと実際の実行時間（短いリスト）の違い）を挙げています。 – sascha
私の経験上、長いリストで何かを検索すると、実際にはPythonが遅くなります。
上記の提案を補足するために、私の提案はリストがサブセット化され、正しいサブセットに簡単に割り当てることができる場合にのみ、リストをサブセット化することになります。
例では、英語の辞書で単語を検索します。最初に、各単語の頭文字に基づいて辞書を26個の「ABCD」セクションにサブセット化します。クエリが「apple」の場合は、「A」セクションのみを検索する必要があります。これの利点は、検索スペースが大幅に制限され、速度が向上することです。
数値リストの場合は、範囲に基づいてサブセットを設定するか、最初の桁に合わせます。
これが役に立ちます。
'list'を' set'（1回）にしてから、メンバーシップテストに 'set'を使うのが、これをスピードアップするための標準的な方法です。特定のケース（リストがソートされている場合は2分法）で役立つことができる他のものがありますが、他の「一般的な」解決策はありません。 – mgilson
Btw。メンバーシップをテストしてもよろしいですか？平等をチェックし、[浮動小数点数学は壊れていることが知られています]（http://stackoverflow.com/questions/588004/is-floating-point-math-broken）。 –
[巨大なリスト（python）の検索/検索のための最も効率的な方法]の複製の可能性（http://stackoverflow.com/questions/2701173/most-efficient-way-for-a-lookup-search-in- a-huge-list-python） –