Quicksort di Python - Comprensione delle liste vs Ricorsione (routine di partizione)

Question

Ho guardato la conversazione Tre bei Quicksorts e mi sono messo a fare i conti con quicksort. La mia implementazione in python era molto simile a c (selezionare pivot, partizionare attorno ad esso e ricorrere su partizioni sempre più piccole). Che pensavo non fosse pythonic.

Quindi questa è l'implementazione utilizzando la comprensione degli elenchi in python.

def qsort(list): 
    if list == []: 
     return [] 
    pivot = list[0] 
    l = qsort([x for x in list[1:] if x < pivot]) 
    u = qsort([x for x in list[1:] if x >= pivot]) 
    return l + [pivot] + u 

Consente di richiamare il methoqsortR di ricorsione. ora ho notato che qsortR gira molto più lentamente di qsort per elenchi di grandi dimensioni (r). In realtà "profondità massima di ricorsione superata in cmp" anche per 1000 elemetri per metodo di ricorsione. Che ho ripristinato in sys.setrecursionlimit.

Alcuni numeri:

list-compr 1000 elems 0.491770029068 
recursion 1000 elems 2.24620914459 
list-compr 2000 elems 0.992327928543 
recursion 2000 elems 7.72630095482 

Tutto il codice è here.

Ho un paio di domande:

• Perché è di lista in modo molto più veloce?
• Alcuni chiarimenti sul limite della ricorsione in python. Per prima cosa l'ho impostato su 100000 in quali casi dovrei stare attento?
  • (Che cosa si intende per 'ottimizzare ricorsione in coda', come si fa?)
• cercando di risolvere 1000000 elementi accaparrati memoria del mio computer portatile (con il metodo ricorsione). Cosa devo fare se voglio ordinare tanti elementi? Che tipo di ottimizzazioni sono possibili?

Answer 1

1. Perché di lista in modo molto più veloce?

   A causa di lista comporta ciclo C che è molto più veloce di modo lento generale di usare for blocco di Python.

2. Alcuni chiarimenti sul limite della ricorsione in python. Per prima cosa l'ho impostato su 100000 in quali casi dovrei stare attento?

   In caso di esaurimento della memoria.

3. Cercando di ordinare 1000000 elementi ho tenuto la memoria del mio laptop (con il metodo di ricorsione). Cosa devo fare se voglio ordinare tanti elementi? Che tipo di ottimizzazioni sono possibili?

   La ricorsione di Python fornisce un tale sovraccarico perché ogni chiamata di funzione alloca un sacco di spazio di memoria di stack su ogni chiamata.

   In generale, l'iterazione è la risposta (fornirà prestazioni migliori in termini statisticamente del 99% dei casi d'uso).

   Parlando di strutture di memoria, se si dispone di strutture dati semplici, come caratteri, numeri interi, float: utilizzare array.array incorporato che è molto più efficiente della memoria di uno list.

Answer 2

Hai provato a scrivere un'implementazione non ricorsiva di partition? Sospetto che la differenza di prestazioni sia puramente l'implementazione partition. Stai ricorsivamente per ogni elemento nella tua implementazione.

Aggiornamento

Ecco una rapida implementazione. Non è ancora super veloce o efficiente, ma è molto meglio del tuo originale ricorsivo.

>>> def partition(data): 
... pivot = data[0] 
... less, equal, greater = [], [], [] 
... for elm in data: 
... if elm < pivot: 
... less.append(elm) 
... elif elm > pivot: 
... greater.append(elm) 
... else: 
... equal.append(elm) 
... return less, equal, greater 
... 
>>> def qsort2(data): 
... if data: 
... less, equal, greater = partition(data) 
... return qsort2(less) + equal + qsort2(greater) 
... return data 
... 

Penso anche che ci sia un numero maggiore di liste temporanee generate nella versione "tradizionale".

Answer 3

Cercare di confrontare la comprensione della lista con un algoritmo sul posto quando la memoria diventa davvero grande. Il codice qui sotto ottiene un tempo di esecuzione vicino quando si ordinano numeri interi da 100K, ma probabilmente si rimarrà nella soluzione di comprensione degli elenchi quando si ordinano gli interi da 1M. Ho fatto i test usando una macchina da 4Gb. Il codice completo: http://snipt.org/Aaaje2

class QSort: 
def __init__(self, lst): 
    self.lst = lst 

def sorted(self): 
    self.qsort_swap(0, len(self.lst)) 
    return self.lst 

def qsort_swap(self, begin, end): 
    if (end - begin) > 1: 
     pivot = self.lst[begin] 
     l = begin + 1 
     r = end 
     while l < r: 
      if self.lst[l] <= pivot: 
       l += 1 
      else: 
       r -= 1 
       self.lst[l], self.lst[r] = self.lst[r], self.lst[l] 

     l -= 1 
     self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]  
     # print begin, end, self.lst 
     self.qsort_swap(begin, l) 
     self.qsort_swap(r, end)