python - 異なる長さの辞書からアイテムをポップアウトするときの時間差

Question

私はPythonでソフトウェアを設計していますが、非常に短い長さのディクショナリからアイテムをポップアウトするときと、非常に長いディクショナリからアイテムをポップアウトするときに時間差があるかどうか、またはすべての場合で同じであるかどうかについて、ほとんど興味がありませんでした.

Answer 1

timeitモジュールを使用すると、この質問に簡単に答えることができます。しかし、ディクショナリの全体的なポイントは、キーによって目的の要素にほぼ瞬時にアクセスできることなので、2 つのシナリオに大きな違いがあるとは考えていません。

Answer 2

Python TimeComplexityに関するこの記事を確認してください。

dict オブジェクトに対してリストされている平均ケース時間は、オブジェクトのハッシュ関数が十分に堅牢であり、衝突が一般的ではないことを前提としています。Average Case は、パラメータで使用されるキーがすべてのキーのセットから一様にランダムに選択されることを前提としています。

(実際には) str キーのみを扱う dict の高速パスがあることに注意してください。これはアルゴリズムの複雑さには影響しませんが、一定の要因 (典型的なプログラムの終了速度) に大きな影響を与える可能性があります。

この記事によると、「Get Item」操作の場合、平均的なケースは O(1) で、最悪のケースは O(n) です。つまり、最悪のケースは、時間がサイズに比例して増加することです。詳細については、Wikipedia のBig O Notationを参照してください。