如何更快地实现贪婪设置封面？

经过对我的原始问题here进行了大量讨论后，我想出了贪婪集封面的以下实现。从我收到的帮助中，我将问题编码为“贪婪集封面”，在收到更多帮助后，我想出了以下实现。我很感谢大家帮助我解决这个问题。下面的实现工作正常，但我想使其可扩展/更快。如何更快地实现贪婪设置封面？

通过可扩展/速度更快，我的意思是说：

我的数据集包含约50K-100K集S中
以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特定的优化都会非常好。

来源

2011-10-29 Legend

什么样的时候你vs你需要什么？无疑，大部分执行时间都花在c级代码查找集合交集上，所以没有太多的优化可以做到？对于某些随机数据（结果可能与当然数据有所不同，不能确定是否这些都是良好的值）的10万台，在每一组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做什么，那么为什么要麻烦呢？

来源

2011-10-30 00:02:13 Thomas

+1谢谢。你是对的。我正在寻找不必要的优化。就我而言，它在大约15秒内运行对我来说很好。再一次感谢你。 – Legend

我使用一个技巧，当我在implemented着名的贪婪算法集覆盖（无权）在Matlab中。有可能你可以以某种方式将这个技巧扩展到加权的情况下，使用set cardinality/set weight而不是set cardinality。而且，如果你使用NumPy库，将Matlab代码导出到Python应该很容易。

这是使用方法：

（可选）我排序相对于降序的基数（即要素数它们包含）的套。我还储存了他们的基数。
我选择了一组S，在我的实现中，它是最大的（即列表的第一个集合），并且我计算它包含多少个未覆盖的元素。假设它包含n未发现的元素。
因为现在我知道有一组小号与ň发现的元素，我不需要用基数来处理所有的套低于ñ元素，因为他们不能优于小号。所以我只需要在基数至少为n;随着我的排序，我们可以轻松地关注它们。

来源

2011-11-26 19:54:35

如何更快地实现贪婪设置封面？

回答

相关问题