Python：大整型键的快速字典

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

---

编辑： 我想要按照西蒙·斯特林的要求添加一些背景。

找到形式类比

lays : laid :: says : said

目标是在单词列表中

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

，就像我已经有一个函数 analogy(a,b,c,d) 给出 True if a :b::c:d。但是，我需要检查从列表创建的所有可能的四元组，这将是 O((n^4)/2) 左右的复杂性。

作为预过滤器，我想使用字符计数属性。它表示每个字符在 (a,d) 和 (b,c) 中具有相同的计数。例如，在“layssaid”中我们有 2 个 a，所以我们在“laidsays”中也是如此。

所以到目前为止的想法是

• 为每个单词创建一个“字符计数向量”并将其表示为一个整数（列表中的项目） l)
• 创建pairs 中的所有配对，并查看是否存在“对簇”，即特定字符计数向量和的多个对。

它确实有效，只是速度很慢。复杂度降至 O((n^2)/2) 左右，但这仍然很多，尤其是字典查找和插入经常完成。

Answer 1

有一些琐碎的优化，例如在局部变量中缓存常量值以及使用 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))

但是，不预先计算列表并使用 xrange 可能更明智。相反，在概念层面上优化该方法。您想要实现的内在目标是什么？你真的只想计算你所做的事情吗？或者您打算将该结果用于其他用途吗？那是什么别的东西？

Answer 2

只是一个提示。查看 itertools.combinations。

这并不完全是您正在寻找的（因为它存储一对值，而不是索引），但它可以是一个起始代码：

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

Answer 3

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

Answer 4

最后，我想出了自己的解决方案，平均只需要一半的计算时间。

基本思想：我首先将所有总和收集到一个列表中，而不是读取和写入不断增长的字典 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)