Python quicksort - List comprehension vs Recursion (procedura partycji)

Question

Oglądałem rozmowę Three Beautiful Quicksorts i bawiłem się z quicksort. Moja implementacja w Pythonie była bardzo podobna do c (wybierz pivot, partycję wokół niego i powtarzanie na mniejszych i większych partycjach). Które myślałem, że nie był pythonic.

Jest to implementacja wykorzystująca zrozumienie list w pythonie.

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 

Pozwala wywołać metodę rekursji qsortR. teraz zauważyłem, że qsortR działa znacznie wolniej niż qsort dla dużych (r) list. Właściwie "maksymalna głębokość rekurencji przekroczona w cmp" nawet dla 1000 elemów dla metody rekursji. Które resetuję w sys.setrecursionlimit.

Niektóre numery:

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

Cały kod jest here.

Mam kilka pytań:

• Dlaczego lista zrozumienie tak dużo szybciej?
• Oświecenie na granicy rekursji w pytonie. Najpierw ustawiłem ją na 100000 w jakich przypadkach powinienem być ostrożny?
  • (Co dokładnie należy rozumieć przez „optymalizację rekursji ogon”, jak to się robi?)
• Próbując uporządkować 1000000 elementy hogged pamięć o moim laptopie (metodą rekursji). Co powinienem zrobić, jeśli chcę sortować tak wiele elementów? Jakie rodzaje optymalizacji są możliwe?

Answer 1

1. Dlaczego lista zrozumienie tak dużo szybciej?

   Ponieważ rozumienie listowe implikuje pętlę C, która jest znacznie szybsza niż powolny ogólny sposób korzystania z bloku Pythona for.

2. Oświecenie na granicy rekursji w pytonie. Najpierw ustawiłem ją na 100000 w jakich przypadkach powinienem być ostrożny?

   W przypadku wyczerpania pamięci.

3. Próba posortowania 1000000 elementów zhakowanej pamięci mojego laptopa (metodą rekursji). Co powinienem zrobić, jeśli chcę sortować tak wiele elementów? Jakie rodzaje optymalizacji są możliwe?

   Rekurencja w języku Python daje taki narzut, ponieważ każde wywołanie funkcji przydziela dużo miejsca na stosie w każdym wywołaniu.

   Ogólnie rzecz biorąc, iteracja jest odpowiedzią (zapewni lepszą wydajność w statystycznie 99% przypadków użycia).

   Mówiąc o strukturach pamięci, jeśli masz proste struktury danych, takie jak znaki, liczby całkowite, zmiennoprzecinkowe: używaj wbudowanego array.array, który jest o wiele bardziej wydajny niż pamięć list.

Answer 2

Czy próbowałeś napisać nierekurencyjną implementację partition? Podejrzewam, że różnica w wydajności jest wyłącznie implementacją partition. Powtarzasz dla każdego elementu w swojej implementacji.

Aktualizacja

Oto szybka realizacja. Nadal nie jest superszybki ani nawet wydajny, ale jest znacznie lepszy niż oryginalny rekursywny.

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

Uważam również, że istnieje większa liczba list tymczasowych wygenerowanych w "tradycyjnej" wersji.

Answer 3

Spróbuj porównać zrozumienie listy z algorytmem lokalnym, gdy pamięć jest naprawdę duża. Poniższy kod uzyskuje przybliżony czas wykonania przy sortowaniu liczb całkowitych 100K, ale prawdopodobnie utkniesz w rozwiązaniu ze zrozumieniem listy podczas sortowania liczb całkowitych 1M. Wykonałem testy przy użyciu maszyny 4Gb. Pełny kod: 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)