用Cython詞典/地圖

我有元素的列表，標籤對這樣的：[(e1, l1), (e2, l2), (e3, l1)]用Cython詞典/地圖

我都數不過來二元多少標籤的共同點 - 即。在上面的列表e1和e3中共有標籤l1，因此共有1個標籤。

我有這樣的Python實現：

def common_count(e_l_list): 
    count = defaultdict(int) 
    l_list = defaultdict(set) 

    for e1, l in e_l_list: 
     for e2 in l_list[l]: 
      if e1 == e2: 
       continue 
      elif e1 > e2: 
       count[e1,e2] += 1 
      else: 
       count[e2,e1] += 1 

     l_list[l].add(e1) 

    return count

它需要一個列表類似上面並計算元素對和計數的字典。上面列表的結果應該給出{(e1, e2): 1}

現在我必須將這個擴展到數百萬個元素和標籤，我認爲Cython會是一個很好的解決方案來節省CPU時間和內存。但是我找不到關於如何在Cython中使用地圖的文檔。

我將如何在純Cython中實現上述操作？

可以假定所有元素和標籤都是無符號整數。

在此先感謝:-)

來源

2016-02-05 user28906

將標籤作爲關鍵字和元素作爲標籤的值會更有意義嗎？如果你這樣設置它，那麼將1000萬個元素和〜50000個標籤的列表轉換爲字典只需要幾秒鐘。在排序元素時切換鍵和值需要大約一半的時間來製作字典。 – SirParselot

林不知道我跟着你...我怎麼能夠查找有多少共同的標籤2元素有？ – user28906

啊，我誤解了你的問題。我以爲你在尋找共享標籤的所有元素。所以你的標籤和元素不一定是唯一的？ – SirParselot

我認爲你正試圖在創建元素對和存儲所有常見的標籤作爲值這個複雜的時候，你可以創建一個元素爲重點的字典，並有與該元素相關的所有值的列表。當你想找到共同的標籤將列表轉換爲一個集合並對它們執行交集時，結果集合將具有兩者之間的公共標籤。交集，用〜20000所列出檢查的平均時間大約是0.006還是挺快的

我用這個代碼測試這個

from collections import * 
import random 
import time 

l =[] 
for i in xrange(10000000): 
    #With element range 0-10000000 the dictionary creation time increases to ~16 seconds 
    l.append((random.randrange(0,50000),random.randrange(0,50000))) 

start = time.clock()  
d = defaultdict(list) 
for i in l: #O(n) 
    d[i[0]].append(i[1]) #O(n) 

print time.clock()-start 

times = [] 
for i in xrange(10000): 
    start = time.clock() 
    tmp = set(d[random.randrange(0,50000)]) #picks a random list of labels 
    tmp2 = set(d[random.randrange(0,50000)]) #not guaranteed to be a different list but more than likely 
    times.append(time.clock()-start) 
    common_elements = tmp.intersection(tmp2) 
print sum(times)/100.0 

18.6747529999 #creation of list 
4.17812619876 #creation of dictionary 
0.00633531142994 #intersection

注：時代就取決於標籤的數量略有變化。另外創建字典可能對您的情況來說太長，但這只是一次性操作。

我也極力不建議創建所有元素對。如果你有五百萬個元素，並且他們至少共享一個標籤，這是最糟糕的情況，那麼你就會看到1.24e + 13對，或者更直白地說，是12.5萬億。這將是〜1700 TB或〜1.7 PB

來源

2016-02-05 16:10:30 SirParselot

很抱歉，但它並不真正有幫助，建議完全不同的東西。我對解決這個問題感興趣，因爲重要的是它可以像解決其他程序流程一樣解決問題。使用地圖的 – user28906

@ user28906幾乎不會爲您節省時間。昂貴的部分是創建所有的對。如果你的程序需要對，那麼你可能需要重新思考你是如何做到這一點的。最簡單的方法並不總是最好的方法 – SirParselot

用Cython詞典/地圖

回答

相關問題