我有一个包含 >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) 左右,但这仍然很多,尤其是经常进行字典查找和插入。
最佳答案
有一些微不足道的优化,例如在局部变量中缓存常量值以及使用 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))
但是,不预先计算列表而是在概念层面优化方法可能更为明智。你想要实现的内在目标是什么?你真的只想计算你做了什么吗?还是您打算将该结果用于其他用途?那是什么东西?
关于Python:大整数键的快速字典,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5911191/