python - OrderedDict を使用しない理由はありますか?

Question

モジュールのOrderedDictを参照していcollectionsます。これは順序付けられた辞書です。

注文可能な機能が追加されている場合、それは必要ないことが多いと思いますが、それでも欠点はありますか? 遅いですか？機能が不足していませんか？不足しているメソッドはありませんでした。

要するに、通常の辞書の代わりにこれを常に使用すべきではないのはなぜですか?

Answer 1

OrderedDictは のサブクラスでありdict、キーが追加される順序を追跡するためにより多くのメモリが必要です。これは簡単なことではありません。この実装dictでは、内部に 1 秒が追加され、すべてのキーの二重リンク リスト (順序を記憶する部分) と、weakref プロキシの束が追加されます。それほど遅くはありませんが、プレーンを使用するよりもメモリが少なくとも 2 倍になりますdict。

しかし、それが適切であれば、それを使用してください！それがそこにある理由です:-)

使い方

基本辞書は、キーを値にマッピングする単なる通常の辞書であり、まったく「順序付け」されていません。<key, value>ペアが追加されるkeyと、 がリストに追加されます。リストは順番を記憶する部分です。

しかし、これが Python リストの場合、キーの削除O(n)には2 倍の時間 がかかりO(n)ます。リスト内のキーを見つける時間と、リストO(n)からキーを削除する時間です。

したがって、代わりに二重にリンクされたリストです。これにより、キーの削除が定数 ( O(1)) 時間になります。しかし、キーに属する二重リンク リスト ノードを見つける必要があります。その操作O(1)時間を短縮するために、2 番目の非表示の dict は、二重リンク リスト内のノードにキーをマップします。

したがって、新しい<key, value>ペアを追加するには、ペアをベース dict に追加し、キーを保持する新しい二重リンク リスト ノードを作成し、その新しいノードを二重リンク リストに追加し、非表示の辞書内のその新しいノードにキーをマッピングする必要があります。 . 作業量は 2 倍強ですが、それでもO(1)(予想されるケースでは) 全体的に時間がかかります。

同様に、存在するキーを削除するのも 2 倍強の作業ですが、O(1)全体的に予想される時間です: 非表示の dict を使用してキーの二重リンク リスト ノードを見つけ、そのノードをリストから削除し、両方の dict からキーを削除します。

などなど、かなり効率的です。