Python ordinano array paralleli sul posto?

Question

Esiste un modo semplice (ovvero senza attivare la propria funzione di ordinamento) per ordinare gli elenchi paralleli senza copiare inutilmente in Python? Per esempio:

foo = range(5) 
bar = range(5, 0, -1) 
parallelSort(bar, foo) 
print foo # [4,3,2,1,0] 
print bar # [1,2,3,4,5] 

Ho visto gli esempi che utilizzano zip ma sembra sciocco per copiare tutti i dati da elenchi in parallelo ad una lista di tuple e viceversa se questo può essere facilmente evitato.

Answer 1

Per raggiungere questo obiettivo, è necessario implementare il proprio tipo.

Tuttavia: la copia non necessaria fa veramente male all'applicazione? Spesso anche parti di Python mi sembrano inefficienti, ma sono abbastanza efficienti per quello di cui ho bisogno.

Answer 2

C'è un modo semplice? Sì. Usa zip.

C'è un "modo semplice che non utilizza una variante di zip"? No.

Se volessi approfondire il motivo per cui ti opponi all'uso di zip, sarebbe utile. O stai copiando oggetti, nel qual caso Python copierà per riferimento, o stai copiando qualcosa di così leggero in una tupla leggera da non essere degno di ottimizzazione.

Se davvero non ti interessa la velocità di esecuzione, ma sono particolarmente preoccupato per qualche motivo sulla pressione della memoria, puoi impostare il tuo bubble sort (o il tuo algoritmo di scelta) nell'elenco delle chiavi che scambia sia l'elenco delle chiavi e il bersaglio elenca gli elementi quando fa uno scambio. Lo definirei il contrario di facile, ma sicuramente limiterebbe il tuo working set.

Answer 3

Qualsiasi soluzione che posso immaginare, a meno di introdurre una sorta da zero, utilizza indici, o un ditt, o qualcos'altro che non è in grado di salvarti la memoria. In ogni caso, l'utilizzo di zip aumenterà l'utilizzo della memoria solo di un fattore costante, quindi vale la pena assicurarsi che questo sia davvero un problema prima di una soluzione.

Se può essere un problema, potrebbero esserci soluzioni più efficaci. Poiché gli elementi di foo e bar sono così strettamente correlati, sei sicuro che la loro giusta rappresentazione non sia un elenco di tuple? Sei sicuro che non dovrebbero trovarsi in una struttura dati più compatta se stai esaurendo la memoria, come una matrice numpy o un database (l'ultimo dei quali è veramente buono in questo tipo di manipolazione)?

(anche, per inciso, itertools.izip può risparmiare un po 'di memoria nel zip, anche se è ancora finire con l'elenco zip completo sotto forma di lista come il risultato di ordinato.)

Answer 4

Ecco un modo semplice:

perm = sorted(xrange(len(foo)), key=lambda x:foo[x]) 

Questo genera un elenco di permutazioni - il valore in perm [i] è l'indice del esimo valore più piccolo nella foo. Quindi, è possibile accedere a entrambe le liste in ordine:

for p in perm: 
    print "%s: %s" % (foo[p], bar[p]) 

Avresti bisogno di punto di riferimento per scoprire se è più efficiente, anche se - dubito che fa molta differenza.