Python:大型int键的快速字典
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Python:大型int键的快速字典,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1865字,纯文字阅读大概需要3分钟。
内容图文
![Python:大型int键的快速字典](/upload/InfoBanner/zyjiaocheng/719/105c83bef9444bddadc9cdb430e1e705.jpg)
我有一个> 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)]
...
对[7]的内容是我正在寻找的.它给了我两对具有相同值的总和.
我已经实现了如下 – 我想知道它是否可以更快地完成.目前,对于10,000个物品,在快速机器上需要> 6小时. (正如我所说,l的值和对的键是最多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 ... ]
我已经有一个函数类比(a,b,c,d)如果a:b :: c:d则给出True.但是,我需要检查从列表中创建的所有可能的四元组,这将是O((n ^ 4)/ 2)的复杂性.
作为预过滤器,我想使用char-count属性.它表示每个字符在(a,d)和(b,c)中具有相同的计数.例如,在“layssaid”中我们有2个,所以我们在“laidsays”中做
所以直到现在的想法是
>为每个单词创建一个“字符计数向量”并将其表示为整数(列表中的项目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:大型int键的快速字典全部内容,希望文章能够帮你解决Python:大型int键的快速字典所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。