如何提升我的贪心集合覆盖实现速度？

2 投票

2 回答

4577 浏览

提问于 2025-04-17 05:16

经过很多讨论，我想出了一个“贪心集合覆盖”的实现方案，这个讨论是围绕我最初的问题展开的，具体可以查看这里。在得到一些帮助后，我把问题转化成了“贪心集合覆盖”，然后又得到了更多的帮助，具体可以看这里，最终我得出了以下的实现方案。非常感谢大家的帮助！这个实现方案运行得不错，但我希望能让它更具扩展性和更快。

这里说的“扩展性/更快”是指：

我的数据集中大约有5万到10万个集合
集合中的元素数量很少，大约在100到500之间
每个集合的大小可能从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特定的优化，那就太好了。

数据结构算法优化性能提升复杂度分析数据集处理贪心算法扩展性集合覆盖

2 个回答

我在用Matlab实现著名的贪心算法来解决集合覆盖问题时，使用了一个小技巧。这个技巧可能也能扩展到有权重的情况，方法是用集合的大小或权重来替代集合的大小。此外，如果你使用NumPy库，把Matlab代码转到Python应该会很简单。

下面是这个技巧：

（可选）我先把所有的集合按元素数量从大到小排序，并记录下它们的元素数量。
我选择一个集合S，在我的实现中，它是列表中最大的集合（也就是第一个集合），然后我计算它包含了多少个未覆盖的元素。假设它包含n个未覆盖的元素。
现在我知道集合S有n个未覆盖的元素，所以我不需要处理所有元素数量少于n的集合，因为它们不可能比S更好。因此，我只需要在元素数量至少为n的集合中寻找最优集合；由于我已经排序过了，这样查找会变得很简单。

回答于 2025-04-17 由 Python大师

分享举报

你得到的执行时间和你需要的时间相比怎么样？大多数时间肯定是在处理集合交集的代码里，所以其实能优化的地方不多吧？我用一些随机数据（当然，结果可能会因你的数据而异，不确定这些值是否合适），比如有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}

嗯，看起来大约有三分之一的时间并不是在处理集合交集。不过我个人觉得不需要再进一步优化了，尤其是如果这样会影响代码的清晰度。剩下的三分之二时间也没什么好优化的，那何必呢？

回答于 2025-04-17 由 Python大师

分享举报

如何提升我的贪心集合覆盖实现速度？

2 个回答

撰写回答