OrderedDictはアイテムの挿入順序を維持する必要があるので、私はget/set/popitemのパフォーマンスがPython 2.7でどうなっているのでしょうか？これまでの公式文書は見つかりませんでした。 私はgetがO(1)であり、setがO(logN)であり、popitemがO(1)であると推測しています。OrderedDictの取得とpopitemのパフォーマンス
ここにはcollection.OrdereDict です。
Implementation of python Orderedlist object from Python mercurial repositoryにチェックを入れました。 odictobject.cファイルのコメントで、彼らは言った：One invariant of Python's OrderedDict is that it preserves time complexity of dict's methods, particularly the O(1) operations.
クーンさん、ありがとうございました。実装のロジックに関するコード・レポを読み、 'popitem'実装の論理について少し混乱させました。私はそれが 'O（1）'を使ってどのように実装されているのだろうか？通常、挿入順序を維持するためにヒープまたは他の同様のデータ構造が存在するはずです。そうすれば、最後か最初のポップで常に正しい項目を見つけることができますか？ –
（続き）コードの実装から、私はヒープや他のデータ構造を使用しているのではないので、あなたは正しいと思う 'O（1）'実装を使用していると思います。彼らは 'O（1）'を使ってパフォーマンスを達成します。これは素晴らしいことです。 :) –
こんにちは、私の上記の質問に助言できるなら、それは素晴らしいでしょう。ありがとう。 –
@Kun、感謝と投票アップ。私は尋ねる前にいくつかの文書とディスカッションをオンラインで紹介しました。あなたが言及した議論では、結論はset/get/popitemがすべて 'O（1）'であるようです。しかし、私は彼らが本当に「O（1）」であることを述べている公式文書は見当たりません。ところで、あなたが私のポストを読むなら、私の質問は、OrderedDictの時間の複雑さに関する公式文書です。 :) 私が何かを間違って読んだら私を修正してください。 –