Python quicksort - Lista de comprensión vs Recursion (rutina de partición)

Question

Vi la charla Tres hermosos Quicksorts y estaba jugando con el quicksort. Mi implementación en python fue muy similar a c (seleccione pivote, particion alrededor y recursión en particiones más pequeñas y más grandes). Lo cual pensé que no era pythonic.

Así que esta es la implementación que usa la lista de comprensión en 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 

Llamemos a la recursion metho qsortR. ahora noté que qsortR corre mucho más lento que qsort para listas grandes (r). En realidad, "la máxima profundidad de recursión excedida en cmp" incluso para 1000 elems para el método de recursión. Lo reinicié en sys.setrecursionlimit.

Algunos números:

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

Todo el código es here.

Tengo un par de preguntas:

• ¿Por qué es tan lista por comprensión mucho más rápido?
• Alguna aclaración sobre el límite de la recursión en python. Primero lo configuré en 100000, ¿en qué casos debo tener cuidado?
  • (¿Qué se entiende exactamente por 'la optimización de recursión de cola', ¿cómo se hace?)
• Tratando de resolver 1000000 elementos hogged memoria de mi ordenador portátil (con el método de la repetición). ¿Qué debo hacer si quiero ordenar tantos elementos? ¿Qué tipo de optimizaciones son posibles?

Answer 1

1. ¿Por qué es tan lista por comprensión mucho más rápido?

   Porque la comprensión de la lista implica C loop, que es mucho más rápido que la forma lenta y general de usar el bloque for de Python.

2. Algunas aclaraciones sobre el límite de recursión en python. Primero lo configuré en 100000, ¿en qué casos debo tener cuidado?

   En caso de que se quede sin memoria.

3. Tratando de ordenar 1000000 elementos almacenados en la memoria de mi computadora portátil (con el método de recursión). ¿Qué debo hacer si quiero ordenar tantos elementos? ¿Qué tipo de optimizaciones son posibles?

   La recursión de Python proporciona una sobrecarga porque cada llamada de función asigna mucho espacio de memoria de pila en cada llamada.

   En general, la iteración es la respuesta (dará un mejor rendimiento en el 99% de casos de uso estadísticamente).

   Hablando de estructuras de memoria, si tiene estructuras de datos simples, como caracteres, números enteros, flotantes: use el array.array incorporado que es mucho más eficiente que list.

Answer 2

¿Ha intentado escribir una implementación no recursiva de partition? Sospecho que la diferencia de rendimiento es puramente la implementación partition. Está recurriendo a cada elemento en su implementación.

actualización

Aquí hay una rápida implementación. Todavía no es súper rápido o incluso eficiente, pero es mucho mejor que tu recursivo original.

>>> 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 
... 

También creo que hay un mayor número de listas temporales generadas en la versión "tradicional".

Answer 3

Trate de comparar la comprensión de la lista con un algoritmo in situ cuando la memoria sea realmente grande. El siguiente código obtiene un tiempo de ejecución cercano cuando se ordenan 100K números enteros, pero es probable que quede atrapado en la lista de solución de comprensión al ordenar enteros de 1M. Realicé las pruebas con una máquina de 4 Gb. El código 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)