Najszybszy sposób sortowania w języku Python

Question

Jaki jest najszybszy sposób sortowania tablicy całkowitej liczby całkowitej większej niż 0 i mniejszej niż 100000 w języku Python? Ale nie używając wbudowanych funkcji, takich jak sortowanie.

Poszukuję możliwości połączenia 2 funkcji sportowych w zależności od rozmiaru wejściowego.

Answer 1

Jeśli jesteś zainteresowany asymptotycznej czasie, to sortowanie przez zliczanie lub sortowanie pozycyjne zapewnić dobrą wydajność.

Jednakże, jeśli jesteś zainteresowany ścianie zegar czasu trzeba będzie porównać wydajność między różnymi algorytmami przy użyciu Twój szczególności dane ustawia, jak wykonać różne algorytmy odmiennie z różnych zbiorów danych. W tym przypadku, jego zawsze warto spróbować quicksort:

def qsort(inlist): 
    if inlist == []: 
     return [] 
    else: 
     pivot = inlist[0] 
     lesser = qsort([x for x in inlist[1:] if x < pivot]) 
     greater = qsort([x for x in inlist[1:] if x >= pivot]) 
     return lesser + [pivot] + greater 

Źródło: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python

Answer 2

Ponieważ znasz zakres liczb, możesz użyć wartości Counting Sort, która będzie liniowa w czasie.

Answer 3

Wbudowane funkcje są najlepsze, ale ponieważ nie można ich używać rzucić okiem na to:

http://en.wikipedia.org/wiki/Quicksort

Answer 4

Wczesne wersje Pythona wykorzystywane hybrydę samplesort (wariant quicksort z dużej liczebności próby) oraz binarny Sortowanie przez wstawianie jako wbudowany -w algorytmie sortowania. To okazało się nieco niestabilne. S0, od python 2.3 dalej używa algorytmu adaptive mergesort.

Zamówienie mergesort (średnio) = O(nlogn). Order of mergesort (worst) = O(nlogn). Ale Zakon szybkiego sortowania (najgorsze) = n * 2

jeśli używa list=[ .............. ]

list.sort() wykorzystuje mergesort algorithm.

Dla porównania sortowania algorytm można przeczytać wiki

Dla porównania szczegółów comp

Answer 5

Możemy użyć sortowania według słownika, aby zminimalizować dodatkowe wykorzystanie przestrzeni i kee p również niski czas pracy. Sortowanie zliczania jest znacznie wolniejsze w przypadku małych rozmiarów tablicy wejściowej ze względu na koszty implementacji Pythona i C. Sortowanie liczników zaczyna wyprzedzać sortowanie regularne, gdy rozmiar tablicy (COUNT) wynosi około 1 miliona.

Jeśli naprawdę potrzebujesz dużych przyspieszeń dla mniejszych rozmiarów wejść, zaimplementuj sortowanie zliczania w C i wywołaj je z Pythona.

(Naprawiono błąd, który Aaron (+1) pomógł złapać ...) Pyton tylko realizacja poniżej porównuje 2 podejść ...

import random 
import time 

COUNT = 3000000 

array = [random.randint(1,100000) for i in range(COUNT)] 
random.shuffle(array) 

array1 = array[:] 

start = time.time() 
array1.sort() 
end = time.time() 
time1 = (end-start) 
print 'Time to sort = ', time1*1000, 'ms' 

array2 = array[:] 

start = time.time() 
ardict = {} 
for a in array2: 
    try: 
     ardict[a] += 1 
    except: 
     ardict[a] = 1 

indx = 0 
for a in sorted(ardict.keys()): 
    b = ardict[a] 
    array2[indx:indx+b] = [a for i in xrange(b)] 
    indx += b 

end = time.time() 
time2 = (end-start) 
print 'Time to count sort = ', time2*1000, 'ms' 

print 'Ratio =', time2/time1 

Answer 6

sortowanie pozycyjne teoretycznie działa w czasie liniowym (czas sortowania rośnie w przybliżeniu wprost proporcjonalnie do rozmiaru tablicy), ale w praktyce Quicksort jest prawdopodobnie bardziej odpowiedni, chyba że sortujesz absolutnie masywne tablice.

Jeśli chcesz przyspieszyć pracę szybciej, możesz użyć sortowania wstawiania], gdy rozmiar tablicy staje się mały.

Pomocne może być również zrozumienie pojęć złożoności algorytmicznej i zapisu Big-O.

Answer 7

def sort(l): 
    p = 0 
    while(p<len(l)-1): 
     if(l[p]>l[p+1]): 
      l[p],l[p+1] = l[p+1],l[p] 
      if(not(p==0)): 
       p = p-1 
     else: 
      p += 1 
    return l 

to algorytm, który stworzyłem, ale jest naprawdę szybki. po prostu sortuj (l) l będącą listą, którą chcesz posortować.

Answer 8

@fmark Niektóre testy porównawcze implementacji Pythona Merge-sort pisałem przeciwko pythonowi quicksorts od http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python i od najwyższej odpowiedzi.

1. Rozmiar listy i wielkości liczb w liście nieistotnego

merge sort wygrywa, jednak używa wbudowanego int(), aby piętrze

import numpy as np 
x = list(np.random.rand(100)) 


# TEST 1, merge_sort 
def merge(l, p, q, r): 
    n1 = q - p + 1 
    n2 = r - q 
    left = l[p : p + n1] 
    right = l[q + 1 : q + 1 + n2] 

    i = 0 
    j = 0 
    k = p 
    while k < r + 1: 
     if i == n1: 
      l[k] = right[j] 
      j += 1 
     elif j == n2: 
      l[k] = left[i] 
      i += 1 
     elif left[i] <= right[j]: 
      l[k] = left[i] 
      i += 1 
     else: 
      l[k] = right[j] 
      j += 1 
     k += 1 

def _merge_sort(l, p, r): 
    if p < r: 
     q = int((p + r)/2) 
     _merge_sort(l, p, q) 
     _merge_sort(l, q+1, r) 
     merge(l, p, q, r) 

def merge_sort(l): 
    _merge_sort(l, 0, len(l)-1) 

# TEST 2 
def quicksort(array): 
    _quicksort(array, 0, len(array) - 1) 

def _quicksort(array, start, stop): 
    if stop - start > 0: 
     pivot, left, right = array[start], start, stop 
     while left <= right: 
      while array[left] < pivot: 
       left += 1 
      while array[right] > pivot: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -= 1 
     _quicksort(array, start, right) 
     _quicksort(array, left, stop) 

# TEST 3 
def qsort(inlist): 
    if inlist == []: 
     return [] 
    else: 
     pivot = inlist[0] 
     lesser = qsort([x for x in inlist[1:] if x < pivot]) 
     greater = qsort([x for x in inlist[1:] if x >= pivot]) 
     return lesser + [pivot] + greater 

def test1(): 
    merge_sort(x) 

def test2(): 
    quicksort(x) 

def test3(): 
    qsort(x) 

if __name__ == '__main__': 
    import timeit 
    print('merge_sort:', timeit.timeit("test1()", setup="from __main__ import test1, x;", number=10000)) 
    print('quicksort:', timeit.timeit("test2()", setup="from __main__ import test2, x;", number=10000)) 
    print('qsort:', timeit.timeit("test3()", setup="from __main__ import test3, x;", number=10000)) 

Answer 9

mogę być trochę późno show, ale istnieje ciekawy artykuł, który porównuje różne rodzaje pod adresem https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash

Jednym z głównych powodów jest to, że podczas sortowania domyślnego es świetnie możemy zrobić trochę lepiej dzięki skompilowanej wersji quicksort. Wymaga to pakietu Numba.

Oto link do repo GitHub: https://github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb