Как сделать мою реализацию жадного набора обложки быстрее?

Я придумал следующую реализацию для 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 для этого кода была бы очень приятной.

  • мобильное приложение python-social-auth +
  • Как выбрать точку в подзаголовке и выделить ее в смежных подзаговорах в matplotlib (расширение до области точек)
  • urrlib2.urlopen: «Имя или услуга не известна» сохраняется при запуске скрипта без подключения к Интернету
  • Одна строка if-condition-assign
  • smtplib отправляет пустое сообщение, если сообщение содержит определенные символы
  • Преобразование строки в значение ASCII python
  • Число меньше отрицательной бесконечности в python?
  • Как проверить содержимое входящего запроса заголовка HTTP
  • 2 Solutions collect form web for “Как сделать мою реализацию жадного набора обложки быстрее?”

    Какие времена вы получаете против того, что вам нужно? Разумеется, большая часть времени выполнения расходуется на скрещивание кода на уровне 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} 

    Hm, поэтому в основном, по-видимому, 1/3 времени не находится в установленных пересечениях. Но я лично больше не буду оптимизировать, особенно ценой ясности. Там не будет много, что вы можете сделать с другими 2/3, так зачем беспокоиться?

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

    Вот трюк:

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