如何在Python列表中有效地計數共現

Question

我有一個相對較大的（〜3GB，300萬條目）的子列表列表，其中每個子列表包含一組標籤。這裏是一個非常簡單的例子：

tag_corpus = [['cat', 'fish'], ['cat'], ['fish', 'dog', 'cat']] 

unique_tags = ['dog', 'cat', 'fish'] 
co_occurences = {key:Counter() for key in unique_tags} 

for tags in tag_corpus: 
    tallies = Counter(tags) 
    for key in tags: 
     co_occurences[key] = co_occurences[key] + tallies 

這就像魅力，排序的，但它的實際數據集，其中有非常大的子表（30K〜總獨特的標記）超慢。任何python專業人士都知道我可以如何加速這件事？

Answer 1

This might go faster。你必須測量。

from collections import Counter 
from collections import defaultdict 

tag_corpus = [['cat', 'fish'], ['cat'], ['fish', 'dog', 'cat']] 

co_occurences = defaultdict(Counter) 
for tags in tag_corpus: 
    for key in tags: 
     co_occurences[key].update(tags) 
unique_tags = sorted(co_occurences) 

print co_occurences 
print unique_tags 

Answer 2

我只是搞亂不期待任何東西更有效地結束了，但100000家貓，狗和魚，這是相當快，在0.07秒打卡，而不是1.25。

我試圖用更短的解決方案，結束了，但事實證明這種方式是最快的，即使它看起來非常簡單:)

occurances = {} 
for tags in tag_corpus: 
    for key in tags: 
     for key2 in tags: 
      try: 
       occurances[key][key2] += 1 
      except KeyError: 
       try: 
        occurances[key][key2] = 1 
       except KeyError: 
        occurances[key] = {key2: 1} 

Answer 3

，你可以嘗試用defaultdict梳理避免在使用從彼得斯答案的邏輯開始初始化，運行時會顯著快：

In [35]: %%timeit 
co_occurences = defaultdict(Counter) 
for tags in tag_corpus: 
    for key in tags: 
     co_occurences[key].update(tags) 
    ....: 

1 loop, best of 3: 513 ms per loop 

In [36]: %%timeit 
occurances = {k1: defaultdict(int) for k1 in unique_tags} 
for tags in tag_corpus: 
    for key in tags: 
     for key2 in tags: 
      occurances[key][key2] += 1 
    ....: 
10 loops, best of 3: 65.7 ms per loop 

In [37]: %%timeit 
    ....: co_occurences = {key:Counter() for key in unique_tags} 
    ....: for tags in tag_corpus: 
    ....:  tallies = Counter(tags) 
    ....:  for key in tags: 
    ....:   co_occurences[key] = co_occurences[key] + tallies 
    ....: 
1 loop, best of 3: 1.13 s per loop 
    In [38]: %%timeit 
    ....: occurances = defaultdict(lambda: defaultdict(int)) 
    ....: for tags in tag_corpus: 
    ....:  for key in tags: 
    ....:   for key2 in tags: 
    ....:    occurances[key][key2] += 1 
    ....: 
10 loops, best of 3: 66.5 ms per loop 

至少在python2，一個計數器字典是沒有實際工作Ÿ最快的方法來獲得計數，但默認爲，但即使使用拉姆達也是快速的。

即使滾動自己計數功能會更快：

def count(x): 
    d = defaultdict(int) 
    for ele in x: 
     d[ele] += 1 
    return d 

不太一樣快的速度最快，但還是不錯的：

In [42]: %%timeit 
    ....: co_occurences = {key: defaultdict(int) for key in unique_tags} 
    ....: for tags in tag_corpus: 
    ....:  tallies = count(tags) 
    ....:  for key in tags: 
    ....:   for k, v in tallies.items(): 
    ....:    co_occurences[key][k] += v 
    ....: 

10 loops, best of 3: 164 ms per loop 

如果你想要更多的加速，有點用Cython的可能會走很長的路。