効率的な辞書検索ですか？

Question

大きい辞書をPythonで検索することの効率について簡単に質問しました。私は大きなカンマ区切りのファイルを読み込み、各行からキーと値を取得しています。私のキーがすでに辞書に入っている場合は、辞書に記載されている値に値を追加します。もしそのキーが辞書に存在しなければ、単にその値を追加します。以前私はこれを使用していた：

は

if key in data_dict.keys(): 
    add values 
else: 
    data_dict[key] = value 

これはかなり速い始まりますが、辞書が大きくなるにつれて、それは私がすべてでそれを使用することができない点まで、遅く、遅くなります。これは無限に高速であり、そして3秒でコード35万行の上に読み取り/書き込みができ

try: 
    # This will fail if key not present 
    data_dict[keyStr] = input_data[keyStr] + load_val 
except: 
    data_dict[keyStr] = load_val 

：私は、私はこれに辞書内のキーを検索する方法を変更しました。

私の質問は、なぜif key in data_dict.keys():コマンドがtry: data_dict[keyStr]の呼び出しよりもはるかに長い時間を取るのですか？なぜ、Pythonは辞書の中でキーを検索するときにtry文を利用しないのですか？

Answer 1

問題はすべてのテストで、.keys()という新しいキーリストを生成していることです。キーのリストが長くなると、必要な時間が長くなります。またas noted by dckrooneyでは、辞書のハッシュテーブル構造を利用する代わりに、キーの検索が線形になります。

と交換してください：

if key in data_dict: 

Answer 2

これは質問に答えるのではなく、むしろそれを回避します。 collections.defaultdictを試してみてください。 if/elseまたはtry/exceptは必要ありません。

from collections import defaultdict 

data_dict = defaultdict(list) 
for keyStr, load_val in data: 
    data_dict[keyStr].append(load_val) 

Answer 3

data_dict.keys()が（少なくともPythonの2.xで）辞書にキーを含むリストを返すからです。キーがリストにあるかどうかを調べるには、線形検索が必要です。

ディクテーションの要素に直接アクセスすると、辞書の素晴らしい特性が利用されるため、アクセスはほぼ瞬時に行われます。

Answer 4

お手伝いをすべきtry関数に似て何かがあります： dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val 

Answer 5

ディクショナリにあるキーのソートされていないリストを返しdata_dict.keys()が。したがって、指定されたキーがディクショナリにあるかどうかを確認するたびに、キーのリスト（O（n）操作）で線形検索が行われます。リストが長ければ長いほど、特定のキーを検索するのに時間がかかります。

これはdata_dict[keyStr]とは対照的です。これはO（1）操作であるハッシュルックアップを実行します。それは（直接的に）辞書のキーの数に依存しません。より多くのキーを追加しても、指定されたキーが辞書内にあるかどうかを確認する時間は一定のままです。前述のように

Answer 6

あなたは、単に代わりに

if key in data_dict.keys(): 

の

if key in data_dict: 

を使用することができ、最初は直接のハッシュ・ルックアップである - ことを意図したオフセットを直接計算して、チェックされている - それはおおよそですO（1）であり、キーのチェックは線形探索であり、O（n）である。

我々は setdefaultを使用昔戻る

In [258]: data_dict = dict([(x, x) for x in range(100000)]) 

In [259]: %timeit 999999 in data_dict.keys() 
100 loops, best of 3: 3.47 ms per loop 

In [260]: %timeit 999999 in data_dict 
10000000 loops, best of 3: 49.3 ns per loop 

Answer 7

：

data_dict.setdefault(keyStr, []).append(load_val) 

Answer 8

いくつか他の人が指摘したように、問題はkey in data_dict.keys()がkeys()メソッドから返さ順不同listを使用するという事実であります（Python 2.xでは）linear timeO（n） thrを検索するこれは、実行時間が辞書のサイズに比例して増加し、キーのリストを生成すること自体が、サイズが上がるにつれて長くかかることを意味します。

一方、key in data_dictは内部でのみ、それはhash tableルックアップを行うためにかかわらず、辞書のサイズの検索を実行するには、平均で、O（1）一定の時間を要します。さらに、このハッシュテーブルは辞書の内部表現の一部であるため既に存在しているため、使用する前に生成する必要はありません。

in演算子は、ソースではなく2つのオペランドの型しか知っていないため、自動的には処理しません。したがって、キーとリストだけが表示されている最初のケースを自動的に最適化することはできません。

しかし、この場合、組み込みのcollectionsモジュールにあるdefaultdictという辞書の特殊バージョンにデータを格納することで、おそらく検索速度の問題を避けることができます。ここでは、1を使用した場合、あなたのコードがどのように見えるかです：

from collections import defaultdict 

input_data = defaultdict(float) # (guessing factory type) 
... 
data_dict[keyStr] = input_data[keyStr] + load_val 

input_data[keyStr] 1のための既存のエントリがありません場合は、デフォルト値（この例ではfloatため0.0）で自動的に生成されます。ご覧のように、コードは短く、おそらく高速であり、すべてのテストや例外処理を必要としません。