Python:大整数键的快速字典

Question

我有一个包含 >10.000 个 int 项目的列表。项目的值(value)可以非常高，高达 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)]}

---

编辑:我想根据 Simon Stelling 的要求添加一些背景。

目标是找到像这样的形式类比

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) 的复杂度。

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

所以到目前为止的想法是

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

它确实有效，只是速度很慢。复杂度降至 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))

但是，不预先计算列表而是在概念层面优化方法可能更为明智。你想要实现的内在目标是什么？你真的只想计算你做了什么吗？还是您打算将该结果用于其他用途？那是什么东西？