Python：大int鍵快字典

Question

我有一個> 10.000 int類型的項目列表。這些物品的價值可能非常高，高達10^27。現在我想創建所有項目對並計算它們的總和。然後我想用相同的總和查找不同的對。

例如：

l[0] = 4 
l[1] = 3 
l[2] = 6 
l[3] = 1 
... 

pairs[10] = [(0,2)] # 10 is the sum of the values of l[0] and l[2] 
pairs[7] = [(0,1), (2,3)] # 7 is the sum of the values of l[0] and l[1] or l[2] and l[3] 
pairs[5] = [(0,3)] 
pairs[9] = [(1,2)] 
... 

的pairs[7]的內容是什麼，我期待的。它給了我兩個相同的價值總和。

我已經實現它如下 - 我不知道它可以做得更快。目前，對於10.000個物品，在快速機器上需要> 6個小時。 （正如我所說，l和值的pairs所以鍵是整數可達10^27）

l = [4,3,6,1] 
pairs = {} 
for i in range(len(l ) ): 
    for j in range(i+1, len(l)): 
     s = l[i] + l[j] 
     if not s in pairs: 
      pairs[s] = [] 
     pairs[s].append((i,j)) 

# pairs = {9: [(1, 2)], 10: [(0, 2)], 4: [(1, 3)], 5: [(0, 3)], 7: [(0, 1), (2, 3)]} 

---

編輯：我想添加一些背景，要求由西蒙·Stelling 。

的目標是要找到正規的類比象

lays : laid :: says : said 

單詞列表內的類似

[ lays, lay, laid, says, said, foo, bar ... ] 

我已經有一個函數analogy(a,b,c,d)給True如果a : b :: c : d。但是，我需要檢查從列表創建的所有可能的四元組，這將是O（（n^4）/ 2）左右的複雜度。

作爲一個預過濾器，我想使用char-count屬性。它說每個char在（a，d）和（b，c）中都有相同的計數。例如，在「layssaid」我們有2級的，所以我們在「laidsays」

做這樣的想法到現在爲止是

• 的每一個字，以創建一個「字符計數矢量」和代表它作爲一個整數（列表中的項目l）
• 在pairs中創建所有配對並查看是否存在「配對簇」，即對於特定的char計數向量和有多於一對。

它的工作原理，它只是緩慢。複雜度下降到O（（n^2）/ 2）左右，但這仍然很多，特別是字典查找和插入操作經常完成。

Answer 1

最後，我想出了我自己的解決方案，平均只需要一半的計算時間。

基本思路：我不是在閱讀和寫入增長字典n^2次，而是首先收集列表中的所有金額。然後我排序列表。在排序列表中，我然後查找相同的鄰居項目。

這是代碼：

from operator import itemgetter 

def getPairClusters(l): 

    # first, we just store all possible pairs sequentially 
    # clustering will happen later 
    pairs = [] 

    for i in xrange(len(l) ): 
     for j in xrange(i+1, len(l)): 
      pair = l[i] + l[j] 
      pairs.append((pair, i, j)) 
    pairs.sort(key=itemgetter(0)) 

    # pairs = [ (4, 1, 3), (5, 0, 3), (7, 0, 1), (7, 2, 3), (9, 1, 2), (10, 0, 2)] 
    # a list item of pairs now contains a tuple (like (4, 1, 3)) with 
    # * the sum of two l items: 4 
    # * the index of the two l items: 1, 3 

    # now clustering starts 
    # we want to find neighbouring items as 
    # (7, 0, 1), (7, 2, 3) 
    # (since 7=7) 

    pairClusters = [] 

    # flag if we are within a cluster 
    # while iterating over pairs list 
    withinCluster = False 

      # iterate over pair list 
    for i in xrange(len(pairs)-1): 
     if not withinCluster: 
      if pairs[i][0] == pairs[i+1][0]: 
       # if not within a cluster 
       # and found 2 neighbouring same numbers: 
       # init new cluster 
       pairCluster = [ (pairs[i][1], pairs[i][2]) ] 
       withinCluster = True 
     else: 
      # if still within cluster 
      if pairs[i][0] == pairs[i+1][0]: 
       pairCluster.append((pairs[i][1], pairs[i][2])) 
      # else cluster has ended 
      # (next neighbouring item has different number) 
      else: 
       pairCluster.append((pairs[i][1], pairs[i][2])) 
       pairClusters.append(pairCluster) 
       withinCluster = False 

    return pairClusters 

l = [4,3,6,1] 

print getPairClusters(l) 

Answer 2

只是一個提示。看看itertools.combinations。

這不是你在尋找什麼（因爲它存儲對值，而不是指數的），但它可以是一個開始代碼：

from itertools import combinations 
for (a, b) in combinations(l, 2): 
    pairs.setdefault(a + b, []).append((a, b)) 

Answer 3

有瑣碎的優化，例如緩存常量在一個局部變量，並使用xrange代替range：

pairs = {} 
len_l = len(l) 
for i in xrange(len_l): 
    for j in xrange(i+1, len_l): 
     s = l[i] + l[j] 
     res = pairs.setdefault(s, []) 
     res.append((i,j)) 

但是，它可能是更明智的做法是不預先計算的列表，而是優化在概念水平的方法。你想達到的內在目標是什麼？你真的只想計算一下你做了什麼嗎？或者你打算把這個結果用於別的東西嗎？那是什麼？

Answer 4

以上SimonStelling的評論是正確的;生成所有可能的配對基本上是很慢的，除了改變算法之外，沒有什麼可以做的。從itertools使用的正確功能是product;你可以通過不創建額外的變量或做不必要的列表索引來進行一些小的改進，但是在底層，這些仍然都是O（n^2）。下面是我該怎麼做：

from itertools import product 
l = [4,3,6,1] 
pairs = {} 
for (m,n) in product(l,repeat=2): 
    pairs.setdefault(m+n, []).append((m,n))