☰

Python 3.6 以降では辞書は順序付けられますか? 質問する

tag-icon • tag-icon python python-3.x dictionary python-internals python-3.6
Python 3.6 以降では辞書は順序付けられますか? 質問する

Python 3.6以降では辞書は挿入順に並び替えられる。これは言語機能ではなくCPythonの実装の詳細として説明されている。ドキュメンテーション状態:

dict()「コンパクトな」表現を使用するようになりましたPyPyが先駆者新しい dict() のメモリ使用量は、Python 3.5 と比較して 20% から 25% 小さくなります。ペップ468(関数内の **kwargs の順序の保持) は、これによって実装されます。この新しい実装の順序保持の側面は実装の詳細と見なされ、依存すべきではありません (これは将来変更される可能性がありますが、言語仕様を変更して、現在および将来のすべての Python 実装で順序保持セマンティクスを義務付ける前に、この新しい辞書実装を言語にいくつかのリリースで組み込むことが望まれます。これにより、ランダム反復順序がまだ有効な言語の古いバージョン (例: Python 3.5) との下位互換性も維持されます)。 (INADA Naoki による寄稿問題 27350。 アイデアレイモンド・ヘッティンガーが最初に提案した。

新しい辞書の実装は、要素の順序を維持しながら、古いものよりもパフォーマンスが優れているのはなぜですか?

2017年12月更新: dictsの保持掲載注文は保証されたPython 3.7の場合

ベストアンサー1

Python 3.6 以降では辞書は順序付けられますか?

これらは挿入順に並べられている[1]。

Python 3.6 以降、Python の CPython 実装では、辞書は挿入された項目の順序を記憶します。これは Python 3.6 の実装の詳細と見なされており、他の Python 実装で保証される挿入順序(およびその他の順序付けられた動作[1] )OrderedDictが必要な場合は、を使用する必要があります。

Python 3.7 以降では、これは単なる実装の詳細ではなく、保証された言語機能です。GvR による python-dev メッセージより:

そうしてください。「辞書は挿入順序を維持する」というのが決まりです。ありがとうございます!

これは単に、それに依存できることを意味します。Python の他の実装も、Python 3.7 に準拠した実装になりたい場合は、挿入順序付き辞書を提供する必要があります。

Python辞書の実装は、要素の順序を維持しながら、古いものよりも3.6パフォーマンスが優れているのはなぜでしょうか[2] ?

基本的には、2 つの配列を保持することによって。

  • 最初の配列、dk_entriesは、エントリ（タイプの PyDictKeyEntry) を辞書に追加します。順序の保持は、新しい項目が常に末尾に挿入される (挿入順序) 追加専用の配列にすることで実現されます。

  • 二番目、dk_indicesは、配列のインデックスdk_entries（つまり、 内の対応するエントリの位置を示す値dk_entries）を保持します。この配列はハッシュテーブルとして機能します。キーがハッシュされると、 に格納されているインデックスの1つにつながり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辞書のサイズに応じて)型のスパース配列 s full が保持されるため、これは当てはまりません。空きスペースは、型から2/3 * dk_sizeに変更されました。PyDictKeyEntryintX_t

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

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

レイモンド・ヘッティンガーによる当初の提案では、使用されたデータ構造の視覚化を見ることで、アイデアの要点を把握できます。

たとえば、辞書では次のようになります。

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

現在、[キーハッシュ、キー、値]として保存されています:

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 が存在するため、「順序付けられた」は `dict` オブジェクトが *提供しない* さらなる動作を示唆するからです。OrderedDict は可逆的で、順序に依存するメソッドを提供し、主に順序に依存する等価テスト (`==`、`!=`) を提供します。`dict` は現在、これらの動作/メソッドを提供していません。
[2]: 新しい辞書の実装は、よりコンパクトに設計されているため、**メモリの観点で**パフォーマンスが向上しています。これがここでの主な利点です。速度の観点では、違いはそれほど劇的ではなく、新しい辞書によってわずかな回帰が生じる可能性がある場所があります（キー検索、例えば) ですが、他の場合 (反復処理やサイズ変更が思い浮かびます) ではパフォーマンスの向上が見られるはずです。 全体として、導入されたコンパクトさにより、特に実際の状況では辞書のパフォーマンスが向上します。

おすすめ記事