[解決済み】Python 3.6+で辞書は順番に並びますか？

質問

Python 3.6 (少なくとも CPython の実装では) では、以前のバージョンと異なり、辞書が順序付けされます。これは実質的な変更のように見えますが、Python 3.6では ドキュメント . これは言語機能ではなく、CPythonの実装の詳細として説明されていますが、将来的にこれが標準になる可能性があることも示唆しています。

新しい辞書の実装は、要素の順序を維持しながら、古いものよりもどのように優れたパフォーマンスを発揮するのでしょうか？

以下は、ドキュメントに掲載されている文章です。

dict() は、「コンパクト」な表現になりました。 PyPyによって開拓された . 新しい dict() のメモリ使用量は、Python 3.5 と比較して 20% から 25% 少なくなっています。 PEP 468 (Preserving order of **kwargs in a function.) が実装されています。この新しい実装の順序保持の側面は、実装の詳細とみなされ、依存すべきではありません (これは将来変わるかもしれませんが、現在と将来のすべての Python 実装で順序保持のセマンティクスを義務付けるために言語仕様を変更する前に、いくつかのリリースでこの新しい dict の実装を言語内に持つことが望まれます。これはまた、ランダム反復順序がまだ有効な古いバージョンの言語との下位互換性保持にも役立ちます、例えば Python 3.5)．(Contributed by INADA Naoki in 課題27350 . アイデア 原案：Raymond Hettinger .)

2017年12月更新 dict の保持挿入順序は 保証 Python 3.7 の場合

解決方法は？

<ブロッククオート

Python 3.6+では、辞書は順序付けされますか？

それは 挿入順 ^[1] . Python 3.6以降、PythonのCPython実装では、ディクショナリ 挿入されたアイテムの順番を記憶する . これはPython 3.6での実装の詳細とされている を使用する必要があります。 OrderedDict 挿入順序が必要な場合、その順序は 保証 Pythonの他の実装にまたがって（他の順序付き動作の ^[1] ).

Python 3.7時点 これはもはや実装の詳細ではなく、言語的な特徴となります。 GvRによるpython-devメッセージより :

<ブロッククオート

Dict keeps insertion order"で決まりです。ありがとうございます。

これは、単純に 頼りになる . Pythonの他の実装も、Python 3.7に準拠した実装でありたいなら、挿入順辞書を提供しなければなりません。

---

<ブロッククオート

Pythonはどのように 3.6 辞書の実装の方が ^[2] 要素の順序を維持したまま、古いものよりも？

基本的に、以下の方法で 2つの配列を保持する .

• 最初の配列です。 dk_entries は、エントリ ( タイプの PyDictKeyEntry ) を、挿入された順番に辞書に追加します。この配列は、新しい項目が常に最後に挿入される (挿入順) 追加専用の配列であるため、順序を維持することができます。

• 2つ目は dk_indices のインデックスを保持する。 dk_entries 配列の対応するエントリの位置を示す値です。 dk_entries ). この配列がハッシュテーブルとして機能します。キーがハッシュ化されるとき、それは dk_indices をインデックス化し、対応するエントリを取得します。 dk_entries . インデックスのみが保持されるため、この配列のタイプは辞書の全体サイズに依存します（タイプは int8_t ( 1 バイト)から int32_t / int64_t ( 4 / 8 バイトで 32 / 64 ビットビルド)

これまでの実装では、型の疎な配列である PyDictKeyEntry とサイズ dk_size を超える配列は作成できないため、残念ながら多くの空き領域が発生します。 2/3 * dk_size フル パフォーマンス上の理由から . (そして空いたスペースは 今も があった。 PyDictKeyEntry のサイズ！）。

のみであるため、現在はこの限りではありません。 必須 の疎な配列が格納されます。 intX_t ( X ディクショナリーのサイズに依存) 2/3 * dk_size が満杯になることはありません。空いたスペースは、型から変更 PyDictKeyEntry から intX_t .

したがって、明らかに、型 PyDictKeyEntry を格納するための疎な配列よりも、はるかに多くのメモリを必要とします。 int s.

会話の全文を見ることができます Python-Devで この機能に興味がある方は、ぜひ読んでみてください。

---

レイモンド・ヘッティンガー氏による原案では このアイデアの要点を捉えた、使用するデータ構造のビジュアライゼーションを見ることができます。

<ブロッククオート

例えば、辞書。

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

は現在、[keyhash, key, value]として格納されています。

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

その代わり、データは以下のように整理しておく。

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

今、視覚的にお分かりのように、オリジナルの提案では、衝突を減らし、検索を高速化するために、多くのスペースが基本的に空になっています。新しいアプローチでは、スパースネスを本当に必要な場所、つまりインデックスに移動することで、必要なメモリを削減します。

---

<サブ [1]: というのも、OrderedDict が存在すると、 "ordered" は、 `dict` オブジェクトが *doesn't provide* している、さらなる動作を示唆しているからです。OrderedDicts は可逆的であり、順序を考慮したメソッドを提供し、主に順序を考慮した等値性テスト (`==`, `!=`) を提供します。現在、 `dict` はこれらの動作やメソッドを提供していません。

---

<サブ [2]: 新しい辞書の実装は、よりコンパクトに設計されているため、**メモリ面でより良いパフォーマンスを発揮します。スピードの面では、それほど劇的な違いはありませんが、新しいディクショナリーが若干のリグレッションを引き起こすかもしれない場所があります ( キーのルックアップなど ) 一方、他のもの (反復処理やリサイズが思い浮かびます) では、パフォーマンスが向上するはずです。 <サブ 全体として、特に実生活の場面では、導入されたコンパクトさにより、辞書の性能が向上する。