如何使贪婪集覆盖的实现更快？

一尘不染

如何使贪婪集覆盖的实现更快？

algorithm

经过大量讨论，我在这里提出了“贪婪套装”的以下实现方案。从收到的帮助中，我将问题编码为“贪婪的封面”，在这里获得更多帮助后，我想到了以下实现。我感谢每个人都为我提供了帮助。以下实现工作正常，但我想使其可扩展/更快。

可扩展/更快，我的意思是说：

我的数据集包含约5万至10万套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的优化都会非常好。

阅读 196

2020-07-28

共1个答案

一尘不染

您获得什么样的时间与需要什么时间？当然，大多数执行时间都用在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可以做的事不多，那么为什么要打扰呢？

2020-07-28