Как мне ускорить реализацию моей жадной обложки? - PullRequest
2 голосов
/ 30 октября 2011

Я придумал следующую реализацию для Greedy Set Cover после долгих обсуждений относительно моего первоначального вопроса здесь . Из полученной помощи я закодировал проблему в «Обложке жадного набора» и после получения дополнительной справки здесь я придумал следующую реализацию. Я благодарен всем за помощь в этом. Следующая реализация работает нормально, но я хочу сделать ее масштабируемой / быстрее.

Под масштабируемым / более быстрым, я имею в виду, что:

  • Мой набор данных содержит около 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 оптимизации этого кода были бы действительно хорошими.

Ответы [ 2 ]

3 голосов
/ 26 ноября 2011

Я использую трюк, когда я реализовал знаменитый жадный алгоритм для набора покрытия (без весов) в Matlab.Вполне возможно, что вы могли бы как-то распространить этот трюк на взвешенный случай, используя набор кардинальности / набор веса вместо набора кардинальности.Более того, если вы используете библиотеку NumPy, экспорт кода Matlab в Python должен быть очень простым.

Вот хитрость:

  1. (необязательно). Я отсортировал наборы в порядке убывания по количеству элементов (т. Е. По количеству элементов, которые они содержат).Я также сохранил их количество элементов.
  2. Я выбираю набор S , в моей реализации он является самым большим (то есть первым набором списка), и я считаю, сколько открытых элементов оно содержит.Допустим, он содержит n непокрытых элементов.
  3. Поскольку теперь я знаю, что существует набор S с n непокрытых элементов, я неНеобходимо обработать все наборы с количеством элементов меньше, чем n элементов, потому что они не могут быть лучше, чем S .Поэтому мне просто нужно найти оптимальный набор среди наборов с кардинальностью не менее n ;с моей сортировкой мы можем легко сфокусироваться на них.
3 голосов
/ 30 октября 2011

В какие времена вы получаете то, что вам нужно? Конечно, большую часть времени выполнения тратится на поиск кода на пересечении множеств на уровне c, так что не так много оптимизации можно сделать? С некоторыми случайными данными (результаты могут отличаться от ваших данных, конечно, не уверен, что это правильные значения) из 100000 наборов, 40 элементов в каждом наборе, 500 уникальных элементов, весовые коэффициенты от 1 до 10 * 1001

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, так что зачем?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...