Я создал алгоритм сортировки на Python 3. Этот алгоритм сортировки является модифицированным оптимизированным медиана из 3 быстрых сортировок, с сетевая сортировка для списков размером до 16 и для поиска медианы. Я пробовал использовать подход O (N) для поиска медианы, но сортировка обычно была быстрее.
Могу я получить совет, как это сделать быстрее?
Кроме того, может ли кто-нибудь связать алгоритмы быстрой сортировки? Я хочу сравнить их с моими и посмотреть, есть ли более быстрые, и если да, то как я могу улучшить свои. Первые 1000 строк — это сортировка сети (я сделал программу для автоматической генерации кода для сортировки сети, я не сумасшедший), а последние 20 строк — это проверка ее скорости. На моем ноутбуке он сортирует 100 000 случайных чисел примерно за 0,192 секунд и 1000000 случайных чисел примерно за 2,754 секунд. (Обратите внимание, что время python не является точным на 100%. Я использовал несколько тестов и нашел среднее значение.)
Я сравнил свой код с mergesort, heapsort, другими quicksort, timsort и radix sort, но ни один из них, похоже, не близок к тому, чтобы превзойти мой код. Однако это, вероятно, связано с тем, что они были взяты из сайтов с инструкциями и не были оптимизированы. К сожалению, большинство людей, которым важен алгоритм быстрой сортировки, похоже, пишут его на Java, C или C ++, с которыми я не могу сравнивать. Итак, я был бы признателен за любые другие оптимизированные алгоритмы сортировки или даже за предложения к моему исходному коду.
#importing
import math
import random
import time
#this is the sorting network (scroll a bunch, this is like 1000 lines)
def sorting_network(lst):
l = len(lst)
if l < 9:
if l < 5:
if l < 3:
if not l or l == 1:
return lst
else:
a = lst[0]
b = lst[1]
if a > b:
a, b = b, a
return [a, b]
else:
if l == 3:
a = lst[0]
b = lst[1]
c = lst[2]
if a > b:
a, b = b, a
if b > c:
b, c = c, b
if a > b:
a, b = b, a
return [a, b, c]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
if a > b:
a, b = b, a
if c > d:
c, d = d, c
if a > c:
a, c = c, a
if b > d:
b, d = d, b
if b > c:
b, c = c, b
return [a, b, c, d]
else:
if l < 7:
if l == 5:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
if a > d:
a, d = d, a
if b > e:
b, e = e, b
if a > b:
a, b = b, a
if c > e:
c, e = e, c
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if c > d:
c, d = d, c
return [a, b, c, d, e]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
if a > f:
a, f = f, a
if b > d:
b, d = d, b
if c > e:
c, e = e, c
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if a > d:
a, d = d, a
if c > f:
c, f = f, c
if a > b:
a, b = b, a
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if b > c:
b, c = c, b
if d > e:
d, e = e, d
return [a, b, c, d, e, f]
else:
if l == 7:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
if a > b:
a, b = a, b
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if a > c:
a, c = c, a
if b > e:
b, e = e, b
if d > g:
d, g = g, d
if a > b:
a, b = b, a
if c > f:
c, f = f, c
if d > e:
d, e = e, d
if b > c:
b, c = c, b
if e > g:
e, g = g, e
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if f > g:
f, g = g, f
return [a, b, c, d, e, f, g]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
if a > c:
a, c = c, a
if b > d:
b, d = d, b
if e > g:
e, g = g, e
if f > h:
f, h = h, f
if a > e:
a, e = e, a
if b > f:
b, f = f, b
if c > g:
c, g = g, c
if d > h:
d, h = h, d
if a > b:
a, b = b, a
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if c > e:
c, e = e, c
if d > f:
d, f = f, d
if b > e:
b, e = e, b
if d > g:
d, g = g, d
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if f > g:
f, g = g, f
return [a, b, c, d, e, f, g, h]
else:
if l < 13:
if l < 11:
if l == 9:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
if a > d:
a, d = d, a
if b > h:
b, h = h, b
if c > f:
c, f = f, c
if e > i:
e, i = i, e
if a > h:
a, h = h, a
if c > e:
c, e = e, c
if d > i:
d, i = i, d
if f > g:
f, g = g, f
if a > c:
a, c = c, a
if b > d:
b, d = d, b
if e > f:
e, f = f, e
if h > i:
h, i = i, h
if b > e:
b, e = e, b
if d > g:
d, g = g, d
if f > h:
f, h = h, f
if a > b:
a, b = b, a
if c > e:
c, e = e, c
if d > f:
d, f = f, d
if g > i:
g, i = i, g
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if f > g:
f, g = g, f
return [a, b, c, d, e, f, g, h, i]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
if a > i:
a, i = i, a
if b > j:
b, j = j, b
if c > h:
c, h = h, c
if d > f:
d, f = f, d
if e > g:
e, g = g, e
if a > c:
a, c = c, a
if b > e:
b, e = e, b
if f > i:
f, i = i, f
if h > j:
h, j = j, h
if a > d:
a, d = d, a
if c > e:
c, e = e, c
if f > h:
f, h = h, f
if g > j:
g, j = j, g
if a > b:
a, b = b, a
if d > g:
d, g = g, d
if i > j:
i, j = j, i
if b > f:
b, f = f, b
if c > d:
c, d = d, c
if e > i:
e, i = i, e
if g > h:
g, h = h, g
if b > c:
b, c = c, b
if d > f:
d, f = f, d
if e > g:
e, g = g, e
if h > i:
h, i = i, h
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if d > e:
d, e = e, d
if f > g:
f, g = g, f
return [a, b, c, d, e, f, g, h, i, j]
else:
if l == 11:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
if b > g:
b, g = g, b
if c > e:
c, e = e, c
if d > h:
d, h = h, d
if f > i:
f, i = i, f
if a > b:
a, b = b, a
if d > f:
d, f = f, d
if e > k:
e, k = k, e
if g > j:
g, j = j, g
if h > i:
h, i = i, h
if b > d:
b, d = d, b
if c > f:
c, f = f, c
if e > h:
e, h = h, e
if i > k:
i, k = k, i
if a > e:
a, e = e, a
if b > c:
b, c = c, b
if d > h:
d, h = h, d
if f > j:
f, j = j, f
if g > i:
g, i = i, g
if a > b:
a, b = b, a
if c > g:
c, g = g, c
if e > f:
e, f = f, e
if h > i:
h, i = i, h
if j > k:
j, k = k, j
if c > e:
c, e = e, c
if d > g:
d, g = g, d
if f > h:
f, h = h, f
if i > j:
i, j = j, i
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
return [a, b, c, d, e, f, g, h, i, j, k]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
l = lst[11]
if b > h:
b, h = h, b
if c > g:
c, g = g, c
if d > l:
d, l = l, d
if e > k:
e, k = k, e
if f > j:
f, j = j, f
if a > b:
a, b = b, a
if c > f:
c, f = f, c
if d > e:
d, e = e, d
if g > j:
g, j = j, g
if h > i:
h, i = i, h
if k > l:
k, l = l, k
if a > c:
a, c = c, a
if b > g:
b, g = g, b
if f > k:
f, k = k, f
if j > l:
j, l = l, j
if a > d:
a, d = d, a
if b > c:
b, c = c, b
if e > g:
e, g = g, e
if f > h:
f, h = h, f
if i > l:
i, l = l, i
if j > k:
j, k = k, j
if b > e:
b, e = e, b
if d > f:
d, f = f, d
if g > i:
g, i = i, g
if h > k:
h, k = k, h
if b > d:
b, d = d, b
if c > f:
c, f = f, c
if g > j:
g, j = j, g
if i > k:
i, k = k, i
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if i > j:
i, j = j, i
if e > g:
e, g = g, e
if f > h:
f, h = h, f
if d > e:
d, e = e, d
if f > g:
f, g = g, f
if h > i:
h, i = i, h
return [a, b, c, d, e, f, g, h, i, k, l]
else:
if l < 15:
if l == 13:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
l = lst[11]
m = lst[12]
if a > m:
a, m = m, a
if b > k:
b, k = k, b
if c > j:
c, j = j, c
if d > h:
d, h = h, d
if f > l:
f, l = l, f
if g > i:
g, i = i, g
if b > g:
b, g = g, b
if c > d:
c, d = d, c
if e > l:
e, l = l, e
if h > j:
h, j = j, h
if i > k:
i, k = k, i
if a > e:
a, e = e, a
if b > c:
b, c = c, b
if d > g:
d, g = g, d
if h > i:
h, i = i, h
if j > k:
j, k = k, j
if l > m:
l, m = m, l
if e > g:
e, g = g, e
if f > j:
f, j = j, f
if i > l:
i, l = l, i
if k > m:
k, m = m, k
if a > f:
a, f = f, a
if d > i:
d, i = i, d
if e > h:
e, h = h, e
if g > l:
g, l = l, g
if j > k:
j, k = k, j
if a > b:
a, b = b, a
if c > f:
c, f = f, c
if g > j:
g, j = j, g
if h > i:
h, i = i, h
if k > l:
k, l = l, k
if b > d:
b, d = d, b
if c > e:
c, e = e, c
if f > g:
f, g = g, f
if j > k:
j, k = k, j
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if f > h:
f, h = h, f
if g > i:
g, i = i, g
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if i > j:
i, j = j, i
if d > e:
d, e = e, d
if f > g:
f, g = g, f
return [a, b, c, d, e, f, g, h, i, j, k, l, m]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
l = lst[11]
m = lst[12]
n = lst[13]
if a > g:
a, g = g, a
if b > l:
b, l = l, b
if c > m:
c, m = m, c
if d > k:
d, k = k, d
if e > f:
e, f = f, e
if h > n:
h, n = n, h
if i > j:
i, j = j, i
if b > c:
b, c = c, b
if d > h:
d, h = h, d
if e > i:
e, i = i, e
if f > j:
f, j = j, f
if g > k:
g, k = k, g
if l > m:
l, m = m, l
if a > e:
a, e = e, a
if b > d:
b, d = d, b
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if j > n:
j, n = n, j
if k > m:
k, m = m, k
if a > b:
a, b = b, a
if c > j:
c, j = j, c
if d > h:
d, h = h, d
if e > l:
e, l = l, e
if g > k:
g, k = k, g
if m > n:
m, n = n, m
if c > f:
c, f = f, c
if e > h:
e, h = h, e
if g > j:
g, j = j, g
if i > l:
i, l = l, i
if b > c:
b, c = c, b
if d > e:
d, e = e, d
if g > h:
g, h = h, g
if j > k:
j, k = k, j
if l > m:
l, m = m, l
if b > d:
b, d = d, b
if c > e:
c, e = e, c
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if j > l:
j, l = l, j
if k > m:
k, m = m, k
if c > d:
c, d = d, c
if e > h:
e, h = h, e
if g > j:
g, j = j, g
if k > l:
k, l = l, k
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if i > j:
i, j = j, i
if d > e:
d, e = e, d
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if j > k:
j, k = k, j
return [a, b, c, d, e, f, g, h, i, j, k, l, m, n]
else:
if l == 15:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
l = lst[11]
m = lst[12]
n = lst[13]
o = lst[14]
if b > c:
b, c = c, b
if d > k:
d, k = k, d
if e > o:
e, o = o, e
if f > i:
f, i = i, f
if g > n:
g, n = n, g
if h > m:
h, m = m, h
if j > l:
j, l = l, j
if a > o:
a, o = o, a
if b > f:
b, f = f, b
if c > i:
c, i = i, c
if d > h:
d, h = h, d
if g > j:
g, j = j, g
if k > m:
k, m = m, k
if l > n:
l, n = n, l
if a > h:
a, h = h, a
if b > g:
b, g = g, b
if c > j:
c, j = j, c
if e > k:
e, k = k, e
if f > l:
f, l = l, f
if i > n:
i, n = n, i
if m > o:
m, o = o, m
if a > g:
a, g = g, a
if c > e:
c, e = e, c
if d > f:
d, f = f, d
if h > l:
h, l = l, h
if i > k:
i, k = k, i
if j > m:
j, m = m, j
if n > o:
n, o = o, n
if a > d:
a, d = d, a
if b > c:
b, c = c, b
if e > h:
e, h = h, e
if f > j:
f, j = j, f
if g > i:
g, i = i, g
if k > l:
k, l = l, k
if m > n:
m, n = n, m
if a > b:
a, b = b, a
if c > d:
c, d = d, c
if e > g:
e, g = g, e
if h > j:
h, j = j, h
if k > m:
k, m = m, k
if l > n:
l, n = n, l
if b > c:
b, c = c, b
if d > f:
d, f = f, d
if i > k:
i, k = k, i
if l > m:
l, m = m, l
if d > e:
d, e = e, d
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if j > k:
j, k = k, j
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > h:
g, h = h, g
if i > j:
i, j = j, i
if k > l:
k, l = l, k
if f > g:
f, g = g, f
if h > i:
h, i = i, h
return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o]
else:
a = lst[0]
b = lst[1]
c = lst[2]
d = lst[3]
e = lst[4]
f = lst[5]
g = lst[6]
h = lst[7]
i = lst[8]
j = lst[9]
k = lst[10]
l = lst[11]
m = lst[12]
n = lst[13]
o = lst[14]
p = lst[15]
if a > n:
a, n = n, a
if b > m:
b, m = m, b
if c > p:
c, p = p, c
if d > o:
d, o = o, d
if e > i:
e, i = i, e
if f > g:
f, g = g, f
if h > l:
h, l = l, h
if j > k:
j, k = k, j
if a > f:
a, f = f, a
if b > h:
b, h = h, b
if c > j:
c, j = j, c
if d > e:
d, e = e, d
if g > n:
g, n = n, g
if i > o:
i, o = o, i
if k > p:
k, p = p, k
if l > m:
l, m = m, l
if a > b:
a, b = b, a
if c > d:
c, d = d, c
if e > f:
e, f = f, e
if g > i:
g, i = i, g
if h > j:
h, j = j, h
if k > l:
k, l = l, k
if m > n:
m, n = n, m
if o > p:
o, p = p, o
if a > c:
a, c = c, a
if b > d:
b, d = d, b
if e > k:
e, k = k, e
if f > l:
f, l = l, f
if g > h:
g, h = h, g
if i > j:
i, j = j, i
if m > o:
m, o = o, m
if n > p:
n, p = p, n
if b > c:
b, c = c, b
if d > m:
d, m = m, d
if e > g:
e, g = g, e
if f > h:
f, h = h, f
if i > k:
i, k = k, i
if j > l:
j, l = l, j
if n > o:
n, o = o, n
if b > e:
b, e = e, b
if c > g:
c, g = g, c
if f > i:
f, i = i, f
if h > k:
h, k = k, h
if j > n:
j, n = n, j
if l > o:
l, o = o, l
if c > e:
c, e = e, c
if d > g:
d, g = g, d
if j > m:
j, m = m, j
if l > n:
l, n = n, l
if d > f:
d, f = f, d
if g > i:
g, i = i, g
if h > j:
h, j = j, h
if k > m:
k, m = m, k
if d > e:
d, e = e, d
if f > g:
f, g = g, f
if h > i:
h, i = i, h
if j > k:
j, k = k, j
if l > m:
l, m = m, l
if g > h:
g, h = h, g
if i > j:
i, j = j, i
return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p]
#and this is the quicksort algorithm!
def swiftsort(lst):
l = len(lst)
if l < 17:
return sorting_network(lst)
elif l < 128:
a = lst[0]
b = lst[l // 2]
c = lst[-1]
if a <= b <= c or c <= b <= a:
split = b
elif b <= c <= a or a <= c <= b:
split = c
else:
split = a
elif l < 8192:
a = [lst[0], lst[l // 8], lst[2 * l // 8], lst[3 * l // 8], lst[4 * l // 8], lst[5 * l // 8], lst[6 * l // 8], lst[7 * l // 8], lst[-1]]
split = sorting_network(lst)[4]
else:
a = [lst[0]]
for x in range(1, 32):
a.append(lst[x * l // 32])
a.append(lst[-1])
split = swiftsort(a)[16]
lst1 = []
lst2 = []
mid = []
for x in lst:
if x < split:
lst1.append(x)
elif x == split:
mid.append(x)
else:
lst2.append(x)
return swiftsort(lst1) + mid + swiftsort(lst2)
#This is for testing the time of my algorithm.
length = 100000
runs = 60
test_list = [random.randint(1, length) for _ in range(length)]
t = 0
for _ in range(runs):
start = time.time()
sort = swiftsort(test_list)
end = time.time()
t += end - start
print(t / runs)
1 ответ
(Это начинается с мнений о том, как раздел и сетевая сортировка представленный Sola Sky закодирован.
Я собираюсь перейти к комментариям по поводу требований к ресурсам — не задерживайте дыхание.)
В своем вопросе вы указываете контекст: что почему.
Сделай так в коде! Python понял это правильно, предоставив строки документации, механизм документации, который делает маловероятным отделение кода от документации. (Это даже доступно для самоанализ.) Вы можете захотеть переименовать sorting_network() после написания его docstring.
Строки документации в Руководство по стилю кода Python, о котором вы, кажется, знаете.
Он содержит полезные советы, такие как комментарии не нужны и фактически отвлекают, если в них говорится об очевидных —#importing это не комментарий.math в настоящее время не используется.
(random и time «просто» используются в тесте — подробнее об этом позже.)
sorting_network(lst):
Я заметил, что ты не используешь Типовые подсказки.
В «дереве решений» нет необходимости else после return. Одно из преимуществ отказа — меньшее количество отступов в коде.
Я хотел бы прочитать в коде о типе сети сравнения, которую строит ваш генератор — я не пытался понять это, без комментариев об использовании сетей оптимальной глубины или компараторов (/ сравнений?) Здесь. Моя IDE «считает» 60 для len 16 — самый известный, который я нахожу.
(and this is the quicksort algorithm! Чтобы разделить волосы, я ожидаю быстрая сортировка Сортировать на месте (и, надеюсь, с дополнительным пространством, в котором преобладает размер ввода). Я бы использовал сортировка разделов.)swiftsort(lst):return—else, опять таки
«Привычно», быстрая сортировка кодируется выбор оси и перегородка исключено.
«Между сравнениями» очень хорошо читается —split = b if a <= b == b <= c else c if b <= c == c <= a else a повторяет одно сравнение вместо потенциально четырех.
Предпочитаю for в понимании перечисления элементов или добавления их в цикл:[lst[l_ * i // 8] for i in range(9) for l_ in (l - 1,)]
(Второй for просто вводит l_ знак равноl-1) «рядный»)
«Предел 8192» выглядит несколько произвольно — как насчет того, чтобы использовать на один элемент меньше, чем количество битов в lпредставление?
samples = (int.bit_length(l) // 2) * 2 - 1
samples = [lst[(l - 1) * i // (samples - 1)] for i in range(samples)]
pivot = sorted(samples)[len(samples)//2]
(Я мог написать (int.bit_length(l)&~1) — могу я это прочитать? Ты? Программист обслуживания?) (Не более 16 позиций, swiftsort()/sorting_network() выглядят выигрышно. Не уверен, что сразу выше.)
(О, послушайте, вы тоже могли бы избавиться от «сравнения 128».)
Пока lst это так себе имя для начала, lst1/lst2 просто не делай: я бы предпочел before&after над preceding&following для краткости и более smaller/bigger для того, чтобы не интерпретировать порядок (который вы можете захотеть переопределить с помощью таких механизмов, как дополнительный компаратор или reverse пометить как sorted()).
В языках, предоставляющих для этого более короткий синтаксис, я мог бы предпочесть эквивалент(before if x < split else mid if x == split else after).append(x) Чтобы подчеркнуть, что разница заключается в выборе последовательности, а не в операции над ней или параметром.
В «сортировке по производственной силе» я бы попытался избежать наихудшего потребления ресурсов: рекурсивно на более коротком из before&after, повторите с другим. С трехсторонней перегородкой не выглядит проще.
С кодом Python в файлах есть именованные модули: имя модуля — это имя файла «без конечного .py«. Модуль, который запускается для выполнения интерпретатором Python, имеет имя "__main__" во время исполнения. Это позволяет хранить короткие тесты или тесты производительности в коде, предназначенном для использования в библиотечном стиле:
# This is for testing the time of my algorithm.
if __name__== '__main__':
import random # place "non-library imports" here
# some test code
Оценка ожидаемого использования ресурсов в целом и сроков, микротестирование в частности — это интересные банки червей.
Позвольте мне просто упомянуть время и Cython.
И что больший размер проблемы, которую вы выбрали, помещается в кэш (L3) современных процессоров общего назначения.