161

Python の辞書またはセットのループ処理が「任意の」順序で行われる方法がわかりません。

つまり、プログラミング言語なので、言語のすべてが 100% 決定されている必要がありますね。Python には、辞書またはセットのどの部分が選択されるか (1 番目、2 番目など) を決定する何らかのアルゴリズムが必要です。

私は何が欠けていますか？

4

5 に答える 5

255

注:この回答はdict、Python 3.6 で型の実装が変更される前に書かれました。この回答の実装の詳細のほとんどは引き続き適用されますが、辞書内のキーのリスト順はハッシュ値によって決定されなくなりました。セットの実装は変更されません。

順序は任意ではありませんが、辞書またはセットの挿入と削除の履歴、および特定の Python 実装に依存します。この回答の残りの部分では、「辞書」については「セット」と読むこともできます。セットは、キーのみで値を持たない辞書として実装されます。

キーはハッシュされ、ハッシュ値は動的テーブルのスロットに割り当てられます (必要に応じて拡大または縮小できます)。そして、そのマッピング プロセスは衝突につながる可能性があります。つまり、既に存在するものに基づいて、キーを次のスロットに挿入する必要があります。

コンテンツの一覧表示はスロットをループするため、キーは現在テーブルに存在する順序で一覧表示されます。

たとえば、キー'foo'と を取り、テーブル サイズが 8 スロットであると仮定します。'bar'Python 2.7 では、hash('foo')is -4177197833195190597、hash('bar')is 327024216814240868. モジュロ 8、つまり、これら 2 つのキーがスロット 3 と 4 にスロットされていることを意味します。

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

これにより、リストの順序が通知されます。

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

3 と 4 を除くすべてのスロットは空です。テーブルをループすると、最初にスロット 3 がリストされ、次にスロット 4'foo'がリストされるため、 の前にリストされ'bar'ます。

barとbazのハッシュ値は正確に 8 離れているため、まったく同じスロット にマップされます4。

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

それらの順序は、最初に挿入されたキーによって異なります。2 番目のキーは次のスロットに移動する必要があります。

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

どちらかのキーが最初に挿入されたため、ここではテーブルの順序が異なります。

CPython (最も一般的に使用される Python 実装) で使用される基本構造の技術的な名前は、オープン アドレスを使用するハッシュ テーブルです。興味があり、C を十分に理解している場合は、(十分に文書化された) すべての詳細についてC の実装を調べてください。Brandon Rhodes によるこのPycon 2010 プレゼンテーションでCPython の仕組みについて説明したり、Andrew Kuchling によって書かれた実装に関する章を含むBeautiful Codedictのコピーを入手することもできます。

Python 3.3 の時点では、ランダム ハッシュ シードも使用されており、特定の種類のサービス拒否 (攻撃者が大量のハッシュ衝突を引き起こすことによって Python サーバーを応答不能にする) を防ぐために、ハッシュ衝突を予測不能にすることに注意してください。これは、指定された辞書またはセットの順序が、現在の Python 呼び出しのランダム ハッシュ シードにも依存することを意味します。

他の実装では、文書化された Python インターフェースを満たす限り、辞書に異なる構造を自由に使用できますが、これまでのすべての実装はハッシュ テーブルのバリエーションを使用していると思います。

CPython 3.6 では、挿入順序を維持する新しい dict実装が導入され、ブートがより高速でメモリ効率が向上しています。各行が保存されたハッシュ値、およびキーと値のオブジェクトを参照する大規模なスパース テーブルを保持するのではなく、新しい実装では、別の「密な」テーブル (同じ数の行のみを含むテーブル) のインデックスのみを参照する小さなハッシュ配列を追加します。実際のキーと値のペアがあるため)、含まれているアイテムをたまたま順番にリストするのは密集したテーブルです。詳細については、Python-Dev への提案を参照してください。Python 3.6 では、これは実装の詳細と見なされることに注意してください。、Python-the-language は、他の実装が順序を保持する必要があることを指定していません。これは Python 3.7 で変更され、この詳細は言語仕様に引き上げられました。実装が Python 3.7 以降と適切に互換性を持つためには、この順序を維持する動作をコピーする必要があります。明確に言うと、セットには既に「小さな」ハッシュ構造があるため、この変更はセットには適用されません。

Python 2.7 以降では、キーの順序を記録するための追加のデータ構造を追加するサブクラスであるOrderedDictclassも提供されます。dict速度と余分なメモリを犠牲にして、このクラスはキーを挿入した順序を記憶します。キー、値、またはアイテムをリストすると、その順序でリストされます。追加のディクショナリに格納された二重リンク リストを使用して、注文を効率的に最新の状態に保ちます。アイデアの概要を説明している Raymond Hettingerの投稿を参照してください。オブジェクトには、 re-orderableOrderedDictなどの他の利点があります。

順序付きセットが必要な場合は、osetパッケージをインストールできます。Python 2.5 以降で動作します。

于 2013-03-18T15:01:12.857 に答える
39

これはPython 3.41 A set before it was closed as a duplicate への応答です。

他の人は正しいです。順序に頼らないでください。あるふりさえしないでください。

そうは言っても、信頼できることが1つあります。

list(myset) == list(myset)

つまり、注文は安定しています。

認識された順序がある理由を理解するには、いくつかのことを理解する必要があります。

  • その Python はハッシュ セットを使用します。

  • CPython のハッシュ セットがどのようにメモリに格納され、

  • 数値のハッシュ方法

上から：

ハッシュ セットは、非常に高速なルックアップ時間でランダム データを格納する方法です。

バッキング配列があります：

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

これらのセットから削除しないため、削除を扱いやすくするためだけに存在する特別なダミー オブジェクトは無視します。

非常に高速なルックアップを行うために、オブジェクトからハッシュを計算する魔法を使います。唯一のルールは、等しい 2 つのオブジェクトは同じハッシュを持つということです。(ただし、2 つのオブジェクトが同じハッシュを持つ場合、それらは等しくない可能性があります。)

次に、配列の長さでモジュラスを取得して、インデックスを作成します。

hash(4) % len(storage) = index 2

これにより、要素へのアクセスが非常に高速になります。

ハッシュは、同じ数になる可能性があるためhash(n) % len(storage)、ストーリーの大部分にすぎません。hash(m) % len(storage)その場合、いくつかの異なる戦略で競合の解決を試みることができます。CPython は、複雑なことを行う前に「線形プローブ」を 9 回使用するため、他の場所を探す前にスロットの左側を最大 9 か所探します。

CPython のハッシュ セットは次のように格納されます。

  • ハッシュ セットは、フルの 2/3 を超えることはできません。20 個の要素があり、バッキング配列の長さが 30 個の場合、バッキング ストアのサイズが変更されて大きくなります。これは、バッキング ストアが小さいと衝突が頻繁に発生し、衝突によってすべてが遅くなるためです。

  • バッキング ストアは、8 から始まる 4 の累乗でサイズ変更されます。ただし、2 の累乗でサイズが変更される大きなセット (50k 要素) (8、32、128、...) を除きます。

そのため、配列を作成すると、バッキング ストアの長さは 8 になります。5 がいっぱいのときに要素を追加すると、一時的に 6 つの要素が含まれます。6 > ²⁄₃·8これによりサイズ変更がトリガーされ、バッキング ストアは 4 倍のサイズ 32 になります。

最後に、数値をhash(n)返すだけです (特別なものnを除く)。-1

それでは、最初のものを見てみましょう。

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)は 10 なので、すべてのアイテムが追加された後、バッキング ストアは少なくとも 15(+1)になります。関連する 2 の累乗は 32 です。したがって、バッキング ストアは次のようになります。

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

我々は持っています

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

したがって、これらは次のように挿入されます。

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

したがって、次のような順序が期待されます

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

他のどこかで開始していない 1 または 33 を使用します。これは線形プロービングを使用するため、次のいずれかになります。

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

また

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

1 が既に存在していたので、33 が置き換えられたものであると予想するかもしれませんが、セットの構築中にサイズ変更が発生するため、実際にはそうではありません。セットが再構築されるたびに、すでに追加されている項目が効果的に並べ替えられます。

これで理由がわかります

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

順調かもしれません。14 個の要素があるため、バッキング ストアは少なくとも 21+1、つまり 32 になります。

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

最初の 13 スロットに 1 ～ 13 のハッシュ。20 はスロット 20 に入ります。

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55hash(55) % 32は 23 のスロットに入ります。

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

代わりに 50 を選択した場合、

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

そして見よ：

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop実装は非常に単純です。リストをトラバースし、最初のリストをポップします。

これはすべて実装の詳細です。

于 2014-09-29T12:13:10.043 に答える
17

「任意」と「未定」は同じではありません。

彼らが言っているのは、「パブリック インターフェイスにある」辞書反復順序の有用なプロパティがないということです。現在ディクショナリ反復を実装しているコードによって完全に決定される反復順序の多くのプロパティがあることはほぼ確実ですが、作成者はそれらを使用できるものとして約束していません。これにより、Python のバージョン間でこれらのプロパティをより自由に変更できます (または、異なる動作条件で、または実行時に完全にランダムに)、プログラムが壊れる心配はありません。

したがって、ディクショナリの順序で任意のプロパティに依存するプログラムを作成すると、ディクショナリ型を使用するという「契約を破る」ことになり、Python 開発者は、動作しているように見えても、これが常に動作することを約束していません。今のところ、テストするとき。これは基本的に、C の「未定義の動作」に依存するのと同じです。

于 2013-11-03T01:47:49.693 に答える
7

この質問に対する他の回答は素晴らしく、よく書かれています。OPは、「どうやって逃げるのか」または「なぜ」と解釈する「どのように」と尋ねます。

Python のドキュメントによると、Python 辞書は抽象データ型の連想配列を実装しているため、辞書は順序付けされていません。彼らが言うように

バインディングが返される順序は任意です

つまり、コンピューター サイエンスの学生は、連想配列が順序付けられていると想定できません。同じことが数学の集合にも当てはまります

セットの要素がリストされている順序は関係ありません

およびコンピュータ サイエンス

セットは、特定の順序なしで特定の値を格納できる抽象データ型です

ハッシュ テーブルを使用したディクショナリの実装は、順序に関する限り連想配列と同じプロパティを持つという点で興味深い実装の詳細です。

于 2015-02-08T02:18:25.297 に答える