Как решить задачу оптимизации заданий

Question

Я работаю над сценарием, который берет элементы из companies и соединяет их с элементами people. Цель состоит в том, чтобы оптимизировать пары таким образом, чтобы сумма всех значений пары была максимизирована (значение каждой отдельной пары предварительно вычисляется и сохраняется в словаре ctrPairs).

Все они в паре 1: 1, в каждой компании есть только один человек, и каждый человек принадлежит только одной компании, а количество компаний равно количеству людей. Я использовал нисходящий подход с таблицей напоминаний (memDict), чтобы избежать пересчета областей, которые уже были решены.

Я верю, что смогу значительно улучшить скорость происходящего здесь, но я не совсем уверен, как. Области, о которых я беспокоюсь, помечены #slow?, любой совет был бы оценен (скрипт работает для ввода списков n <15, но невероятно медленно для n> ~ 15)

def getMaxCTR(companies, people):
    if(memDict.has_key((companies,people))):
        return memDict[(companies,people)] #here's where we return the memoized version if it exists
    if(not len(companies) or not len(people)):
        return 0

    maxCTR = None
    remainingCompanies = companies[1:len(companies)] #slow?

    for p in people:
        remainingPeople = list(people) #slow?
        remainingPeople.remove(p) #slow?
        ctr = ctrPairs[(companies[0],p)] + getMaxCTR(remainingCompanies,tuple(remainingPeople)) #recurse
        if(ctr > maxCTR):
            maxCTR = ctr
    memDict[(companies,people)] = maxCTR
    return maxCTR

Answer 1

Для всех тех, кто задается вопросом об использовании теории обучения, этот вопрос является хорошей иллюстрацией. Правильный вопрос не о «быстром способе отскока между списками и кортежами в Python» - причина медлительности кроется в более глубоком.

То, что вы пытаетесь решить здесь, известно как проблема назначения : с учетом двух списков из n элементов каждый и n & times; n значений (значения каждой пары), как их назначить так, чтобы общее «значение» максимизируется (или, что эквивалентно, минимизируется). Для этого есть несколько алгоритмов, таких как Венгерский алгоритм ( Реализация Python ), или вы можете решить его, используя более общие алгоритмы потока с минимальными затратами, или даже привести его как линейный запрограммируйте и используйте LP-решатель. Большинство из них будут иметь время работы O (n ³ ).

То, что делает ваш алгоритм выше, состоит в том, чтобы попробовать все возможные способы их объединения (Запоминание помогает избежать повторного вычисления ответов для пар подмножеств, но вы по-прежнему просматриваете все пары подмножеств.) Этот подход составляет не менее Ω (n ² 2 ²ⁿ ). Для n = 16 n ³ равно 4096, а n ² 2 ²ⁿ равно 1099511627776. Конечно, в каждом алгоритме есть постоянные коэффициенты, но видите разницу? :-) (Подход в вопросе все же лучше, чем наивный O (n!), Что было бы намного хуже.) Используйте один из алгоритмов O (n ^ 3), и я предсказываю, что он должен работать вовремя до п = 10000 или около того, а не просто до п = 15.

«Преждевременная оптимизация - это корень всего зла», как сказал Кнут, но это также относится и к отложенной / просроченной оптимизации: сначала вы должны тщательно продумать подходящий алгоритм перед его реализацией, а не выбирать плохой, а затем задаться вопросом, какие его части медленные :-) Даже плохая реализация хорошего алгоритма в Python будет на несколько порядков быстрее, чем исправление всех «медленных»? части кода выше (например, переписав в C).

Answer 2

я вижу два вопроса здесь:

1. эффективность: вы воссоздаете одинаковые remainingPeople списки для каждой компании. было бы лучше создать все remainingPeople и все remainingCompanies один раз, а затем выполнить все комбинации.

2. памятка: вы используете кортежи вместо списков, чтобы использовать их в качестве dict ключей для памятки; но идентичность кортежа чувствительна к порядку. IOW: (1,2) != (2,1) вам лучше использовать set s и frozenset s для этого: frozenset((1,2)) == frozenset((2,1))

Answer 3

Если вы хотите получить копию кортежа в виде списка, вы можете сделать mylist = список (mytuple)

Answer 4

Эта строка:

остальных компаний = компании [1: len (компании)]

Можно заменить на эту строку:

remainingCompanies = companies[1:]

Для очень небольшого увеличения скорости. Это единственное улучшение, которое я вижу.