0

ファイルの各行をリストと辞書の両方に読み込んでいます。

with open("../data/title/pruned2_titleonly.txt", 'rb') as f_titles:
    titles_lst = f_titles.read().split('\n')
assert titles_lst[-1] == ''
titles_lst.pop() # remove the last element, an empty string

titles_dict = {}
with open("../data/title/pruned2_titleonly.txt", 'rb') as f_titles:
    for i,line in enumerate(f_titles):
        titles_dict[i] = line

リスト/辞書の各項目にランダムな順序でアクセスして、パフォーマンスをテストしています。

n = len(titles_lst)
a = np.random.permutation(n)

%%time
for i in xrange(10):
    t = []
    for b in a:
        t.append(titles_lst[b])
    del t

>>> CPU times: user 18.2 s, sys: 60 ms, total: 18.2 s
>>> Wall time: 18.1 s

%%time
for i in xrange(10):
    t = []
    for b in a:
        t.append(titles_dict[b])
    del t

>>> CPU times: user 41 s, sys: 208 ms, total: 41.2 s
>>> Wall time: 40.9 s

上記の結果は、辞書ルックアップが O(1) であるのに対し、リスト ルックアップは O(n) であるにもかかわらず、辞書はルックアップ テーブルのリストほど効率的ではないことを暗示しているようです。以下をテストして、O(n)/O(1) のパフォーマンスが正しいかどうかを確認しました...そうではないことがわかりました...

%timeit titles_lst[n/2]
>>> 10000000 loops, best of 3: 81 ns per loop

%timeit titles_dict[n/2]
>>> 10000000 loops, best of 3: 120 ns per loop

契約は何ですか？重要な点として、私は Ubuntu 12.04 で Python 2.7.6 Anaconda ディストリビューションを使用しており、Intel MKL で NumPy をビルドしました。

4

3 に答える 3

8

上記の結果は、辞書ルックアップが O(1) であるのに対し、リスト ルックアップは O(n) であるにもかかわらず、辞書はルックアップ テーブルのリストほど効率的ではないことを暗示しているようです。以下をテストして、O(n)/O(1) のパフォーマンスが正しいかどうかを確認しました...そうではないことがわかりました...

コードがテストしているように見える「アイテムを取得する」という意味で、dict ルックアップが O(N) であるというのは正しくありません。要素が存在する場合、その場所を特定することは O(N) になる可能性があります。たとえばsomelist.index(someval_not_in_the_list)、someval_not_in_the_list in somelist両方が各要素をスキャンする必要があります。と比較x in somelistしx in somedictてみて、大きな違いを確認してください。

しかし、単純にアクセスするsomelist[index]のは O(1) です (時間の複雑さのページを参照してください)。また、キーをハッシュする必要がないため、係数はおそらく辞書の場合よりも小さくなり、O(1) になります。

于 2014-01-18T03:43:47.597 に答える