如何更快地实现贪婪集合覆盖？

Question

在对我原来的问题这里进行多次讨论后，我提出了贪婪集覆盖的以下实现。根据我收到的帮助，我将问题编码为“Greedy Set Cover”，并在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 的优化都非常好。

Answer 1

当我在 Matlab 中实现著名的集合覆盖（无权重）贪婪算法时，我使用了一个技巧。您可以使用设置基数/设置权重而不是设置基数，以某种方式将此技巧扩展到加权情况。 此外，如果您使用 NumPy 库，将 Matlab 代码导出到 Python 应该非常容易。

秘诀如下：

1. （可选）我根据基数（即它们包含的元素数量）按降序对集合进行排序。我还存储了他们的基数。
2. 我选择一个集合S，在我的实现中它是最大的（即列表的第一组），并且我计算它包含多少个未覆盖的元素。假设它包含 n 未覆盖的元素。
3. 既然现在我知道有一个集合S有n个未被覆盖的元素，我不需要处理所有基数低于n元素的集合，因为它们不可能比S更好。所以我只需要在基数至少为n的集合中搜索最优集合；通过我的排序，我们可以轻松关注它们。

Answer 2

您得到的时间与您需要的时间是什么样的？ 当然，大部分执行时间都花在寻找集合交集的 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 来说，你无能为力，那为什么还要麻烦呢？

Answer 3

多年后，如果您愿意使用 numpy + 将集合列表转换为稀疏 CSC 矩阵，那么可以节省成本。

假设您已将集合列表转换为行索引，并将这些集合按列收集到 SciPy CSC 数组中

subsets

。现在，宇宙的大小

U

就是行数和集合数以及列数。

要找到未覆盖元素数量最多的集合，只需将左侧的

subsets

乘以给出当前包含在覆盖中的元素的指示向量即可。得到的向量

set_counts

给出了每个集合中不包含在封面中的元素数量；通过将（正）权重除以该向量并最小化，我们可以通过

np.argmin

获得贪婪选择。

下面是简化的代码（取自here，它的作用就是：

def greedy_set_cover(subsets: csc_array, weights: np.ndarray):
    n, J = subsets.shape

    ## The below extracts set at index j efficiently 
    slice_col = lambda j: subsets.indices[slice(*subsets.indptr[[j,j+1]])] 
    
    ## Vectorized version of the set version that uses matrix multiplication
    set_counts = subsets.sum(axis=0)
    point_cover, soln = np.zeros(n, dtype=bool), np.zeros(J, dtype=bool)
    while not np.all(point_cover):
        opt_s = np.argmin(weights / set_counts)
        point_cover[slice_col(opt_s)] = True
        set_counts = np.maximum((1 - point_cover) @ subsets, 1/n)
        soln[opt_s] = True
    return np.flatnonzero(soln), cost

在我的机器上，使用

timeit

我看到您给出的代码使用 Thomas 的测试用例平均需要约 5 秒。

timeit.timeit(lambda: greedy_set_cover_simple(U, S, w), number=15)/15
# 4.851530780732476 seconds 

相比之下，numpy 解决方案平均只需要不到 0.4 秒：

timeit.timeit(lambda: greedy_set_cover(subsets, w), number=15)/15
# 0.376905655732844 seconds 

将集合

S

转换为稀疏数组会产生开销（在我的机器上大约约 0.6 秒）。