19

「in」演算子を使用してリスト内の項目を検索する場合

if item in list:
  print item

このアイテムの検索に使用されるアルゴリズム。リストを最初から最後まで真っ直ぐに検索しますか、それとも二分探索のようなものを使用しますか?

4

2 に答える 2

21

lists はソートされた順序 (または任意の順序) であると想定できないため、二分探索は機能しません。また、キーがハッシュ可能であると想定することもできないため、dictまたはsetハッシュ テーブル ルックアップとは異なり、検索を高速化するために使用することはできません。

推測では、最初から最後までのすべての要素の単純なチェックです。

関連する Python ソース コードを掘り下げてみます。

--

編集:演算子list.__contains__()を実装する Python 関数は、 listobject.cで定義されています。in

   393 static int
   394 list_contains(PyListObject *a, PyObject *el)
   395 {
   396     Py_ssize_t i;
   397     int cmp;
   398 
   399     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
   400         cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
   401                                            Py_EQ);
   402     return cmp;
   403 }

最初の要素から最後の要素まで (または一致する要素が見つかるまで)、リスト内のすべての要素を反復処理します。ショートカットはありません。

--

編集 2: プロットが厚くなります。定数 listまたはの要素のメンバーシップをテストしていることを Python が検出した場合、次setのようになります。

if letter in ['a','e','i','o','u']:    # list version
if letter in {'a','e','i','o','u'}:    # set version

編集 3 [@JohnMachin]:

定数リストは、2.5-2.7 および 3.1-3.3の定数タプルに最適化されています。
定数セットは、3.3 で (定数) 凍結セットに最適化されています。

@CoryCarsonの回答も参照してください。

于 2012-05-06T05:56:52.973 に答える
6

がリテラル リストの場合list、Python 3.2+ はより高速なアプローチを採用します: http://docs.python.org/dev/whatsnew/3.2.html#optimizations

于 2012-05-06T06:12:59.470 に答える