Pchanie sortowanie Radix (i python) do jego granic

Question

Byłem niezmiernie sfrustrowany z wielu implementacji python radix sortowania tam w Internecie.

Konsekwentnie używają one pozycji dziesiętnej i otrzymują cyfry liczb, które powtarzają, dzieląc przez potęgę 10 lub biorąc log10 liczby. Jest to niezwykle nieefektywne, ponieważ log10 nie jest szczególnie szybką operacją w porównaniu do zmiany bitów, która jest prawie 100 razy szybsza!

O wiele skuteczniejsza implementacja wykorzystuje podstawienie 256 i sortuje liczbę bajtów według bajtów. Pozwala to na wykonanie "pobierania bajtów" za pomocą niewiarygodnie szybkich operatorów bitowych. Niestety, wydaje się, że absolutnie nikt tam nie zaimplementował sortowania radix w pythonie, który używa operatorów bitowych zamiast logarytmów.

Więc wziąłem sprawy w swoje ręce i wyszedł z tej bestii, czyli około połowy prędkości klasyfikowane na małych tablic i działa prawie tak szybko na większe (np len około 10.000.000):

import itertools 

def radix_sort(unsorted): 
    "Fast implementation of radix sort for any size num." 
    maximum, minimum = max(unsorted), min(unsorted) 

    max_bits = maximum.bit_length() 
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 

    min_bits = minimum.bit_length() 
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 

    sorted_list = unsorted 
    for offset in xrange(lowest_byte, highest_byte): 
     sorted_list = radix_sort_offset(sorted_list, offset) 

    return sorted_list 

def radix_sort_offset(unsorted, offset): 
    "Helper function for radix sort, sorts each offset." 
    byte_check = (0xFF << offset*8) 

    buckets = [[] for _ in xrange(256)] 

    for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

    return list(itertools.chain.from_iterable(buckets)) 

Ta wersja sortowania radix polega na znalezieniu bajtów, według których ma sortować (jeśli przekażesz tylko liczby całkowite poniżej 256, będzie sortować tylko jeden bajt, itd.), A następnie posortuj każdy bajt od LSB w górę przez zrzucenie ich w wiadra, aby następnie połączyć łańcuchy. Powtórz to dla każdego bajtu, który należy posortować, a masz ładną posortowaną tablicę w czasie O (n).

Nie jest to jednak tak szybkie, jak mogłoby być, i chciałbym je przyspieszyć, zanim napiszę o nim jako o lepszym sortowaniu radix niż wszystkie inne rodzaje radików.

Running cProfile na to mówi mi, że dużo czasu wydawane są na metodzie append na listach, co sprawia, że ​​myślę, że tego bloku:

for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

w radix_sort_offset je dużo czasu. Jest to również blok, który, jeśli naprawdę na to patrzysz, stanowi 90% pracy dla całego rodzaju. Wygląda na to, że kod ten może być numpy, co, jak sądzę, spowodowałoby znaczny wzrost wydajności. Niestety, nie jestem zbyt dobry z bardziej złożonymi funkcjami, więc nie byłem w stanie tego rozgryźć. Pomoc byłaby bardzo doceniana.

Obecnie używam itertools.chain.from_iterable do spłaszczenia buckets, ale jeśli ktoś ma szybszą sugestię, jestem pewien, że to również pomogłoby.

Oryginalnie miałem funkcję get_byte, która zwróciła jeden bajt numeru o numerze n, ale podkreślenie kodu dało mi ogromną poprawę prędkości, więc zrobiłem to.

Wszelkie inne uwagi dotyczące wdrożenia lub sposoby zwiększenia wydajności są również mile widziane. Chcę usłyszeć cokolwiek i wszystko, co masz.

Answer 1

Już sobie sprawę, że

for num in unsorted: 
    byte_at_offset = (num & byte_check) >> offset*8 
    buckets[byte_at_offset].append(num) 

gdzie większość czasu idzie - dobre ;-)

Istnieją dwa standardowe sztuczki dla przyspieszenia tego rodzaju rzeczy, zarówno mających do czynienia z ruchomymi niezmienników z pętli:

1. Oblicz "przesunięcie * 8" poza pętlą.Przechowuj go w zmiennej lokalnej. Zapisz mnożenie na iterację.
2. Dodaj bucketappender = [bucket.append for bucket in buckets] poza pętlą. Zapisuje wyszukiwanie metody na iterację.

Połącz je i pętla wygląda następująco:

for num in unsorted: 
    bucketappender[(num & byte_check) >> ofs8](num) 

Collapsing go do jednego rachunku również oszczędza parę lokalnym sklepie VRBL/sprowadzić opcodes za iteracji.

Ale na wyższym poziomie, standardowym sposobem na przyspieszenie sortowania radix jest użycie większego radaru. Co jest magicznego w 256? Nic, poza tym, jest wygodne do przenoszenia bitów. Ale podobnie jak 512, 1024, 2048 ... to klasyczny kompromis między czasem a przestrzenią.

PS: dla bardzo długich numerów,

(num >> offset*8) & 0xff 

będzie działał szybciej. Dzieje się tak, ponieważ twój num & byte_check wymaga czasu proporcjonalnego do log(num) - zwykle musi utworzyć liczbę całkowitą równą około num.

Answer 2

Można po prostu użyć jednego z istniejących implementacji C lub C++, takie Jako przykład, integer_sort z Boost.Sort lub u4_sort z usort. Zaskakująco łatwo jest wywołać natywny kod C lub C++ z Pythona, zobacz How to sort an array of integers faster than quicksort?

Całkowicie się denerwuję. Chociaż minęło ponad 2 lata, numpy still does not have radix sort. Poinformuję programistów NumPy, że mogą po prostu pobrać jedną z istniejących implementacji; licencjonowanie nie powinno stanowić problemu.

Answer 3

To jest stara nitka, ale natknąłem się na to, gdy szukałem radix sortowania tablicy liczb całkowitych dodatnich. Próbowałem sprawdzić, czy mogę zrobić coś lepszego niż już niegodziwie szybki timsort (czapki z głowy do ciebie ponownie, Tim Peters), który implementuje wbudowane i posortowane pythona! Albo nie rozumiem pewnych aspektów powyższego kodu, albo jeśli to zrobię, kod przedstawiony powyżej ma pewne problemy z IMHO.

1. Sortuje tylko bajty zaczynając od najwyższego bajtu elementu najmniejszego i kończąc na najwyższym bajcie największego elementu. Może to być w porządku w niektórych przypadkach specjalnych danych. Ogólnie jednak podejście to nie rozróżnia elementów, które różnią się pod względem niższych bitów. Na przykład:

   arr=[65535,65534] 
   radix_sort(arr) 
   

   produkuje zły wynik:

   [65535, 65534] 
   

2. Zakres używany do pętli na funkcji pomocnika nie jest poprawna. Mam na myśli to, że jeśli lower_byte i higher_byte są takie same, wykonanie funkcji pomocniczej jest całkowicie pomijane. BTW Musiałem zmienić xrange na zasięg w 2 miejscach.

3. Dzięki modyfikacjom dotyczącym powyższych 2 punktów, dostałem go do pracy. Ale zajmuje to 10-20 razy czasu budowy Pythona sortowane lub sortowania! Wiem, że timsort jest bardzo wydajny i wykorzystuje już posortowane przebiegi w danych. Ale starałem się sprawdzić, czy mogę wykorzystać wcześniejszą wiedzę, że moje dane to wszystkie dodatnie liczby całkowite, które mają pewną przewagę w moim sortowaniu. Dlaczego sortowanie radix robi tak źle w porównaniu do timsort? Rozmiary tablic, których używałem, są rzędu 80 000 elementów.Czy to dlatego, że implementacja timsorta oprócz jego wydajności algorytmicznej ma także inne zalety wynikające z możliwości wykorzystania bibliotek niskiego poziomu? Czy może czegoś brakuje mi całkowicie? Zmodyfikowany kod użyłem jest poniżej:

   import itertools 
   
   def radix_sort(unsorted): 
       "Fast implementation of radix sort for any size num." 
       maximum, minimum = max(unsorted), min(unsorted) 
   
       max_bits = maximum.bit_length() 
       highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 
   
   # min_bits = minimum.bit_length() 
   # lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 
   
       sorted_list = unsorted 
   # xrange changed to range, lowest_byte deleted from the arguments 
       for offset in range(highest_byte): 
        sorted_list = radix_sort_offset(sorted_list, offset) 
   
       return sorted_list 
   
   def radix_sort_offset(unsorted, offset): 
       "Helper function for radix sort, sorts each offset." 
       byte_check = (0xFF << offset*8) 
   
   # xrange changed to range 
       buckets = [[] for _ in range(256)] 
   
       for num in unsorted: 
        byte_at_offset = (num & byte_check) >> offset*8 
        buckets[byte_at_offset].append(num) 
   
       return list(itertools.chain.from_iterable(buckets))