Come risolvere tractably il compito di ottimizzazione assegnazione

Question

Sto lavorando a uno script che prende gli elementi da companies e li coppie in su con gli elementi della people. L'obiettivo è quello di ottimizzare gli abbinamenti tale che la somma di tutti i valori coppia è massimizzata (il valore di ogni singolo accoppiamento è precalcolate e memorizzato nel ctrPairs dizionario).

Sono tutti accoppiati in un 1: 1, ogni azienda ha una sola persona e ogni persona appartiene ad una sola società, e il numero di aziende è pari al numero di persone. Ho usato un approccio top-down con un tavolo memoization (memDict) per evitare le zone recomputing che sono già stati risolti.

Credo che avrei potuto migliorare notevolmente la velocità di quello che sta succedendo qui, ma io non sono davvero sicuro di come. Aree che mi preoccupano sono contrassegnati con #slow?, tutto il consiglio sarebbe apprezzato (lo script funziona per gli ingressi delle liste n <15 ma diventa incredibilmente lento per 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

A tutti coloro che si chiedono circa l'uso della teoria dell'apprendimento, questa domanda è un buon esempio. La domanda giusta non si tratta di un "modo veloce a rimbalzare tra le liste e tuple in pitone" -. Il motivo della lentezza è qualcosa di più profondo

Quello che stai cercando di risolvere qui è conosciuto come il problema : dato due liste di n elementi ciascuna e n × n valori (il valore di ciascuna coppia), come assegnare in modo che il "valore" totale viene massimizzata (o equivalentemente, minimizzata). Ci sono diversi algoritmi per questo, come il ungherese algoritmo ( Python implementazione ), oppure si potrebbe risolverlo utilizzando algoritmi di flusso più generale min costo, o addirittura lanciarla come un programma lineare e utilizzare un risolutore LP. La maggior parte di questi avrebbe un tempo di esecuzione di O (n ³ ).

Che cosa il vostro algoritmo di cui sopra non è quello di provare ogni possibile modo di loro accoppiamento. (L'memoizzazione aiuta solo ad evitare ricalcolare le risposte per le coppie di sottoinsiemi, ma si sta ancora guardando tutte le coppie di sottoinsiemi.) Questo approccio è almeno Ω (n ² 2 ²ⁿ ). Per n = 16, n ³ è 4096 e n ² 2 ²ⁿ è 1099511627776. Ci sono costanti in ogni algoritmo naturalmente, ma vedi la differenza? :-) (L'approccio in questione è ancora migliore rispetto alla O ingenuo (n!), Il che sarebbe molto peggio.) Utilizzare uno dei O (n ^ 3) algoritmi, e prevedo che dovrebbe funzionare in tempo per un massimo per n = 10000 o così, invece di un massimo di n = 15.

"ottimizzazione prematura è la radice di ogni male", come ha detto Knuth, ma così è in ritardo / ottimizzazione ritardo: si deve prima considerare con attenzione un algoritmo appropriato prima di implementarlo, non scegliere uno cattivo e poi ci domandiamo quali parti di esso sono lenti. :-) Anche gravemente l'attuazione di un buon algoritmo in Python sarebbe ordini di grandezza più veloce di fissare tutti i "lento?" parti del codice di cui sopra (ad esempio, riscrivendo in C).

Answer 2

vedo due problemi qui:

1. efficienza: si sta ricreando le stesse sottoliste remainingPeople per ogni azienda. sarebbe meglio per creare tutte le remainingPeople e tutta la remainingCompanies una volta e poi fare tutte le combinazioni.

2. Memoizzazione: si sta utilizzando tuple invece di liste di usarli come chiavi dict per Memoizzazione; ma l'identità tupla è sensibile ordine-. IOW: si (1,2) != (2,1) migliori sets d'uso e frozensets per questo: frozenset((1,2)) == frozenset((2,1))

Answer 3

Questa riga:

remainingCompanies = aziende [1: len (aziende)]

Può essere sostituito con questa linea:

remainingCompanies = companies[1:]

Per un aumento di velocità molto ridotta. Questo è l'unico miglioramento che vedo.

Answer 4

Se si desidera ottenere una copia di una tupla come un elenco si può fare mialista = lista (mytuple)