在对我原来的问题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,你可以做的不多,所以为什么要这么麻烦？