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))