python – 如何更快地实现贪婪集？
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 如何更快地实现贪婪集？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2368字，纯文字阅读大概需要4分钟。
内容图文
在对我原来的问题here进行了大量讨论之后,我想出了以下关于贪婪套装的实现.从我收到的帮助中,我将问题编码为“贪婪套装”,在收到更多帮助here后,我想出了以下实施.我很感谢大家帮助我解决这个问题.以下实现工作正常但我想使其可扩展/更快.
通过可扩展/更快,我的意思是说：
>我的数据集在S中包含大约50K-100K集
> U本身的元素数量非常小,大约为100-500
> S中每组的大小可以是0到40之间的任何值
这是我的尝试：
U = set([1,2,3,4])
R = U
S = [set([1,2]),
set([1]),
set([1,2,3]),
set([1]),
set([3,4]),
set([4]),
set([1,2]),
set([3,4]),
set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]
C = []
costs = []
def findMin(S, R):
minCost = 99999.0
minElement = -1
for i, s in enumerate(S):
try:
cost = w[i]/(len(s.intersection(R)))
if cost < minCost:
minCost = cost
minElement = i
except:
# Division by zero, ignore
pass
return S[minElement], w[minElement]
while len(R) != 0:
S_i, cost = findMin(S, R)
C.append(S_i)
R = R.difference(S_i)
costs.append(cost)
print "Cover: ", C
print "Total Cost: ", sum(costs), costs
我不是Python的专家,但是对这段代码的任何特定于Python的优化都会非常好.
解决方法:
你得到什么样的时间与你需要的一样？当然,大多数执行时间都花在c级代码查找集合交叉点上,所以你可以做多少优化？随着一些随机数据(结果可能会随着您的数据而变化,不确定这些是否是好的值)的100000组,每组40个元素,500个独特元素,权重随机从1到10,
print 'generating test data'
num_sets = 100000
set_size = 40
elements = range(500)
U = set(elements)
R = U
S = []
for i in range(num_sets):
random.shuffle(elements)
S.append(set(elements[:set_size]))
w = [random.randint(1,100) for i in xrange(100)]
C = []
costs = []
我用cProfile得到了这样的表现：
8200209 function calls in 14.391 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 14.391 14.391 <string>:1(<module>)
41 4.802 0.117 14.389 0.351 test.py:23(findMin)
1 0.001 0.001 14.391 14.391 test.py:40(func)
4100042 0.428 0.000 0.428 0.000 {len}
82 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
41 0.001 0.000 0.001 0.000 {method 'difference' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
4100000 9.160 0.000 9.160 0.000 {method 'intersection' of 'set' objects}
嗯,所以大多数时间显然是1/3的时间不在集合交叉点.但我个人不会再进行优化,尤其是以清晰度为代价.对于其他2/3,你可以做的不多,所以为什么要这么麻烦？
内容总结
以上是互联网集市为您收集整理的python – 如何更快地实现贪婪集？全部内容，希望文章能够帮你解决python – 如何更快地实现贪婪集？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。