Wie man die Aufgabe zur Zuordnungsoptimierung traktbar löst

Question

Ich arbeite an einem Skript, das die Elemente aus nimmt companies und kombiniert sie mit den Elementen von people. Ziel ist es, die Paarungen so zu optimieren, dass die Summe aller Paarwerte maximiert wird (der Wert jeder einzelnen Paarung ist vorberechtigt und im Wörterbuch gespeichert ctrPairs).

Sie sind alle in einer 1: 1 gepaart, jede Firma hat nur eine Person und jede Person gehört nur einer Firma, und die Anzahl der Unternehmen entspricht der Anzahl der Personen. Ich habe einen Top-Down-Ansatz mit einer Memoisierungstabelle verwendet (memDict), um die bereits gelösten Neuberechnung zu vermeiden.

Ich glaube, ich könnte die Geschwindigkeit dessen, was hier vor sich geht, erheblich verbessern, aber ich bin mir nicht sicher, wie. Bereiche, über die ich mir Sorgen machte, sind mit markiert #slow?, jeder Rat würde geschätzt (das Skript funktioniert für Eingaben von Listen n <15, aber es wird unglaublich langsam für 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

Für alle, die sich über die Verwendung der Lerntheorie wundern, ist diese Frage eine gute Illustration. Die richtige Frage besteht nicht über einen "schnellen Weg, zwischen Listen und Tupeln in Python zu springen" - der Grund für die Langsamkeit ist etwas tieferes.

Was Sie hier lösen möchten, ist als die bekannt als die Zuordnungsproblem: Bei zwei Listen von N -Elementen jeweils und N × n -Werte (der Wert jedes Paares), wie sie sie zuweisen, so dass der Gesamtwert "Wert" maximiert (oder äquivalent, minimiert) wird. Es gibt mehrere Algorithmen dafür, wie die Ungarischer Algorithmus (Python -Implementierung), oder Sie können es mit allgemeineren Min-Kosten-Flussalgorithmen lösen oder sogar als lineares Programm werfen und einen LP-Solver verwenden. Die meisten davon hätten eine Laufzeit von o (n³).

Ihr oben genannter Algorithmus ist, jede mögliche Art zu versuchen, sie zu kombinieren. (Die Memoisierung hilft nur dabei, Antworten für Untergruppenpaare neu zu berechnen.²2²ⁿ). Für n = 16, n³ ist 4096 und n²2²ⁿ Ist 1099511627776. In jedem Algorithmus gibt es natürlich konstante Faktoren, aber sehen Sie den Unterschied? :-) (Der Ansatz in der Frage ist immer noch besser als das naive o (n!), Was viel schlechter wäre.) Verwenden Sie einen der O (n^3) -Algorithmen, und ich prognostiziert, dass er rechtzeitig für UP laufen sollte zu n = 10000 oder so, anstatt nur bis zu n = 15.

"Frühgeborene Optimierung ist die Wurzel des gesamten Bösen", wie Knuth sagte, aber es ist eine verzögerte/überfällige Optimierung: Sie sollten vor dem Umsetzung zunächst einen geeigneten Algorithmus in Betracht ziehen, nicht ein schlechtes auswählen und sich dann fragen, was Teile davon langsam sind. :-) Sogar schlecht um einen guten Algorithmus in Python umzusetzen, wäre es schneller Größenordnungen, als das gesamte "langsame" zu reparieren? Teile des obigen Codes (z. B. durch Umschreiben in C).

Answer 2

Ich sehe hier zwei Probleme:

1. Effizienz: Sie erstellen dasselbe remainingPeople Sublisten für jedes Unternehmen. Es wäre besser, alle zu erschaffen remainingPeople und alle remainingCompanies Einmal und dann alle Kombinationen.

2. Memoisierung: Sie verwenden Tupel anstelle von Listen, um sie als zu verwenden dict Schlüssel zur Memoisierung; Aber die Tupelidentität ist ordnungsempfindlich. Iow: (1,2) != (2,1) Sie benutzen besser sets und frozensets dafür: frozenset((1,2)) == frozenset((2,1))

Answer 3

Diese Linie:

Restkompanien = Unternehmen [1: Len (Unternehmen)

Kann durch diese Linie ersetzt werden:

remainingCompanies = companies[1:]

Für eine sehr leichte Geschwindigkeitserhöhung. Das ist die einzige Verbesserung, die ich sehe.

Answer 4

Wenn Sie eine Kopie eines Tupels als Liste erhalten möchten, können Sie myList = liste (mytuple) erstellen, dass