Niedawno usłyszałem o Library sort i ponieważ muszę sprawić, by moi uczniowie pracowali nad Insertion sort (z którego biblioteka sortuje jest pochodną), postanowiłem zbudować dla nich ćwiczenie na ten nowy temat. Wspaniałą rzeczą jest to, że ten algorytm twierdzi, że ma złożoność O (n log n) (patrz tytuł Insertion Sort is O(n log n) lub tekst na stronie Wikipedia z powyższego linku).Empiryczna złożoność mojej implementacji "sortowania bibliotek" nie wydaje się pasować do niczego podobnego do O (n log n)
Jestem świadomy, że pomiary empiryczne nie zawsze są wiarygodne, ale starałem się zrobić co w mojej mocy i jestem trochę rozczarowany poniższą fabułą (niebieski to biblioteka, zielony to lokalny quicksort od Rosetta Code); osie pionowe to średni czas obliczony jako średnia wielu różnych prób; osie poziome są wielkością listy. Losowe listy o wielkości n mają całkowite elementy od 0 do 2n. Kształt krzywej nie wygląda tak jak coś związanego z O (n log n).
Oto mój kod (w tym części testowej); przegapiłem coś?
# -*- coding: utf8 -*-
def library_sort(l):
# Initialization
d = len(l)
k = [None]*(d<<1)
m = d.bit_length() # floor(log2(n) + 1)
for i in range(d): k[2*i+1] = l[i]
# main loop
a,b = 1,2
for i in range(m):
# Because multiplication by 2 occurs at the beginning of the loop,
# the first element will not be sorted at first pass, wich is wanted
# (because a single element does not need to be sorted)
a <<= 1
b <<= 1
for j in range(a,min(b,d+1)):
p = 2*j-1
s = k[p]
# Binary search
x, y = 0, p
while y-x > 1:
c = (x+y)>>1
if k[c] != None:
if k[c] < s: x = c
else: y = c
else:
e,f = c-1,c+1
while k[e] == None: e -= 1
while k[f] == None: f += 1
if k[e] > s: y = e
elif k[f] < s: x = f
else:
x, y = e, f
break
# Insertion
if y-x > 1: k[ (x+y)>>1 ] = s
else:
if k[x] != None:
if k[x] > s: y = x # case may occur for [2,1,0]
while s != None:
k[y], s = s, k[y]
y += 1
else: k[x] = s
k[p] = None
# Rebalancing
if b > d: break
if i < m-1:
s = p
while s >= 0:
if k[s] != None:
# In the following line, the order is very important
# because s and p may be equal in which case we want
# k[s] (which is k[p]) to remain unchanged
k[s], k[p] = None, k[s]
p -= 2
s -= 1
return [ x for x in k if x != None ]
def quicksort(l):
array = list(l)
_quicksort(array, 0, len(array) - 1)
return array
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)
import random, time
def test(f):
print "Testing", f.__name__,"..."
random.seed(42)
x = []
y = []
for i in [ 25, 50, 100, 200, 300, 500, 1000, 5000,
10000, 15000, 25000, 40000, 50000, 100000 ]:
n = 100000//i + 1
m = 2*i
x.append(i)
t = time.time()
for j in range(n):
f([ random.randrange(0,m) for _ in range(i) ])
y.append((time.time()-t)/n)
return x,y
import matplotlib.pyplot as plt
x1, y1 = test(library_sort)
x2, y2 = test(quicksort)
plt.plot(x1,y1)
plt.plot(x2,y2)
plt.show()
Edit: I obliczane więcej wartości, włącza się do tłumacza pypy w celu obliczenia trochę więcej w tym samym czasie; tutaj jest inna fabuła; Dodałem również krzywe odniesienia. Trudno jest być tego pewna, ale wciąż wygląda trochę bardziej jak O (n²) niż O (n log n) ...
Czas działania wynosi O (n log n) Średnio nie najgorszym przypadku. – chepner
Natychmiastowe przemyślenia - (1) wydaje się zaskakująco płaska od 50 000 do 100 000 punktów danych ;-), może jeszcze kilka koniecznych przypadków testowych, (2) asymptotycznie O (n log n), oczekiwane, może nadal wyglądać bardzo różnie w małych przypadkach (to opisuje granicę, gdy rozmiar staje się bardzo duży), może 100 000 jest wciąż trochę za małe. – Steve314
@chepner - dlaczego miałbyś oczekiwać losowego testu, aby pokazać najgorsze zachowanie? Gdy jeden z testów to 100 000 pozycji, wydaje się to mało prawdopodobne. – Steve314