Pythonのdictから要素をポップする時間の複雑さは何ですか？

Question

これはコンビナトリアル問題の一種です。私は非常に大規模なリストを持って、格納all_possible —は、可能な値—と、すべての非常に大規模な実際に存在するすべての値を格納dict、presentは、例えば：

all_possible = [1, 2, 3, 4, 5] 
present = {1: 'some_value', 3: 'some_other_value'} 

は現在、私の検索が少し見えます以下のような：反復ごとに一つだけの辞書で検索、およびPythonの辞書is O(1)の平均検索時間があるので

for key in all_possible: 
    value = present.get(key, None) 
    if value is None: 
     do_something_if_key_not_present() 
    else: 
     do_something_if_key_is_present() 

これは、うまく動作します。

しかし、償却された最悪の場合の検索時間はO（N）であり、ディクショナリは非常に大きい（何百万もの要素）ので、私が検討した最適化の1つは、

for key in all_possible: 
    value = present.pop(key, None) # this line changes, dict shrinks 
    if value is None: 
     do_something_if_key_not_present() 
    else: 
     do_something_if_key_is_present() 

私の質問は、辞書popの時間複雑で何次のとおりですので、その後のルックアップは小さい探索空間）を持っていますか？listのような構造の平均操作pop操作はO（N）ですが、dictからポップする複雑さを示す信頼できるドキュメントは見つかりません。それがO（1）になったら、これは私の検索をスピードアップするかもしれませんが、もしそれがそれ以上であれば、私は自分自身を傷つけるかもしれません。

Answer 1

dict.popの時間複雑度は、dict.getのものとまったく同じです。 list.popは要素をシフトする必要があるためO（N）ですが、dict.popはそうしません。

つまり、dict.popはおそらく検索時間を改善しません。辞書からキーを削除すると、その場所にDKIX_DUMMYというマーカーが残っている必要があります。ルックアップルーチンは、ハッシュ衝突であるかのように見つけ出し、続行しなければならないDKIX_DUMMYを処理する必要があります。せいぜい、削除されたキーには==の比較が保存されます。

dict.popが改善されていても、O（N）ワーストケースの検索時間を節約することはできません。あなたが対立的なキーの選択に対処する必要がある場合、dictsはあなたのユースケースに適していないかもしれません。