Another graph:
- I used Python 3.13.0
- The quicksort is Tim’s original
isorted_sorteddoesn’t fulfill the condition to “release returned values as soon as possible”.- Neither does
isorted_merge, but that’s terribly slow anyway, just included for fun for its brevity.
Code
from time import perf_counter as time
from itertools import *
from heapq import heapify, heappop, merge
from random import seed, random, randrange
from operator import itemgetter, is_not
def isorted_sorted(xs):
return iter(sorted(xs))
def isorted_heap_unstable(xs):
heap = list(xs)
heapify(heap)
return map(heappop, repeat(heap, len(heap)))
def isorted_heap_unstable_gen(xs):
heap = list(xs)
heapify(heap)
while heap:
yield heappop(heap)
def isorted_heap_stable(xs):
heap = list(zip(xs, count()))
heapify(heap)
return map(itemgetter(0), map(heappop, repeat(heap, len(heap))))
def isorted_heap_stable_gen(xs):
heap = list(zip(xs, count()))
heapify(heap)
while heap:
yield heappop(heap)[0]
def isorted_merge(xs):
return merge(*zip(xs))
def isorted_merge_batches_20(arr):
def batches():
for batch in batched(arr, 20):
batch = sorted(batch)
batch.reverse()
yield map(
list.pop,
repeat(batch, len(batch))
)
return merge(*batches())
def isorted_merge_batches_1000(arr):
def batches():
for batch in batched(arr, 1000):
batch = sorted(batch)
batch.reverse()
yield map(
list.pop,
repeat(batch, len(batch))
)
return merge(*batches())
def medianof3(x, y, z):
if y < x:
x, y = y, x
if z < y:
return x if z < x else z
else:
return y
def isorted_quicksort_stable(xs):
from random import sample
stack = [(False, list(xs))]
while stack:
alleq, xs = stack.pop()
if alleq:
yield from xs
continue
if len(xs) < 20:
yield from sorted(xs)
continue
lt = []
eq = []
gt = []
pivs = sample(xs, 9)
pivot = medianof3(medianof3(*pivs[0:3]),
medianof3(*pivs[3:6]),
medianof3(*pivs[6:9]))
for x in xs:
if x < pivot:
target = lt
elif x is pivot or x == pivot:
target = eq
else:
target = gt
target.append(x)
stack.append((False, gt))
stack.append((True, eq))
stack.append((False, lt))
funcs = [
isorted_sorted,
isorted_heap_unstable,
# isorted_heap_unstable_gen,
isorted_heap_stable,
# isorted_heap_stable_gen,
isorted_merge,
isorted_merge_batches_20,
isorted_merge_batches_1000,
isorted_quicksort_stable,
]
############################################################
# Correctness
############################################################
def correctness():
xs = [[randrange(10**4)] for _ in range(10**5)]
expect = sorted(xs)
for f in funcs:
result = list(f(iter(xs)))
if result != expect:
raise Exception(f'{f.__name__} failed to sort')
elif 'unstable' not in f.__name__ and any(map(is_not, result, expect)):
raise Exception(f'{f.__name__} is unstable and not declared as such')
correctness()
############################################################
# Speed
############################################################
# Assign None to rerun
times = {'isorted_sorted': [23.02, 23.04, 23.06, 23.07, 23.08, 23.09, 23.11, 23.13, 23.14, 23.15, 23.16, 23.17, 23.19, 23.2, 23.21, 23.22, 23.23, 23.25, 23.26, 23.27, 23.28, 23.3, 23.31, 23.32, 23.33, 23.34, 23.35, 23.37, 23.39, 23.4, 23.41, 23.43, 23.44, 23.45, 23.46, 23.48, 23.49, 23.5, 23.51, 23.52, 23.53, 23.55, 23.56, 23.57, 23.59, 23.61, 23.62, 23.64, 23.65, 23.66, 23.67, 23.68, 23.69, 23.71, 23.72, 23.73, 23.74, 23.75, 23.76, 23.78, 23.79, 23.8, 23.81, 23.84, 23.85, 23.86, 23.88, 23.89, 23.9, 23.91, 23.92, 23.93, 23.94, 23.95, 23.97, 23.98, 24.0, 24.01, 24.02, 24.03, 24.04, 24.06, 24.07, 24.08, 24.09, 24.11, 24.12, 24.14, 24.15, 24.16, 24.17, 24.18, 24.19, 24.21, 24.22, 24.23, 24.24, 24.25, 24.26, 24.27, 24.28], 'isorted_heap_unstable': [4.96, 5.79, 6.62, 7.39, 8.13, 8.84, 9.56, 10.23, 10.97, 11.64, 12.32, 13.0, 13.69, 14.52, 15.23, 15.93, 16.77, 17.54, 18.42, 19.17, 19.91, 20.69, 21.52, 22.41, 23.2, 24.01, 24.73, 25.41, 26.29, 27.07, 27.8, 28.57, 29.28, 29.94, 30.77, 31.45, 32.1, 32.75, 33.38, 34.05, 34.81, 35.46, 36.2, 36.91, 37.58, 38.18, 38.77, 39.37, 39.94, 40.54, 41.1, 41.78, 42.37, 42.94, 43.52, 44.1, 44.68, 45.23, 45.79, 46.39, 46.96, 47.57, 48.12, 48.75, 49.38, 49.97, 50.61, 51.43, 52.07, 52.68, 53.22, 53.78, 54.36, 54.91, 55.47, 55.97, 56.46, 56.95, 57.47, 58.03, 58.58, 59.06, 59.53, 59.99, 60.5, 60.94, 61.36, 61.75, 62.12, 62.5, 62.86, 63.22, 63.6, 63.96, 64.32, 64.7, 65.1, 65.64, 66.16, 66.67, 67.03], 'isorted_heap_stable': [31.04, 33.97, 36.48, 39.13, 41.77, 44.41, 47.07, 49.73, 52.28, 54.91, 57.39, 59.74, 62.1, 64.56, 66.91, 69.28, 71.58, 73.95, 76.35, 78.72, 81.26, 83.7, 86.13, 88.76, 91.22, 93.73, 96.18, 99.24, 101.77, 104.34, 106.84, 109.34, 111.76, 114.21, 116.76, 119.37, 121.88, 124.33, 126.57, 129.0, 131.4, 133.84, 136.18, 138.47, 140.69, 143.1, 145.34, 147.55, 149.86, 152.15, 154.34, 156.6, 158.87, 161.27, 163.52, 165.7, 167.88, 170.03, 172.14, 174.19, 176.23, 178.4, 180.66, 182.89, 184.96, 187.02, 189.01, 191.04, 192.89, 194.86, 196.88, 199.03, 201.18, 203.22, 205.24, 207.32, 209.19, 211.02, 212.8, 214.57, 216.4, 218.05, 219.76, 221.37, 222.96, 224.5, 225.99, 227.4, 228.86, 230.28, 231.51, 232.72, 233.83, 235.03, 236.21, 237.23, 238.18, 239.05, 239.83, 240.56, 241.17], 'isorted_merge': [6.14, 117.88, 122.89, 127.74, 133.11, 138.52, 143.89, 148.92, 153.79, 158.49, 163.48, 168.51, 173.37, 178.34, 183.27, 188.21, 193.12, 197.98, 202.93, 207.8, 212.7, 217.67, 222.37, 227.36, 232.52, 237.73, 242.8, 247.7, 252.52, 257.52, 262.3, 267.1, 271.8, 276.79, 281.85, 286.99, 292.68, 297.6, 302.8, 308.0, 312.99, 317.94, 323.03, 327.68, 332.2, 337.3, 342.59, 347.65, 352.54, 357.66, 362.78, 367.58, 372.37, 377.17, 381.85, 386.64, 391.29, 396.14, 400.95, 405.57, 410.07, 414.47, 418.74, 423.13, 427.59, 432.3, 437.03, 442.22, 446.91, 451.46, 456.07, 460.51, 464.75, 468.88, 472.85, 477.0, 481.16, 485.24, 489.73, 493.95, 498.02, 502.12, 506.14, 510.03, 513.91, 517.65, 521.42, 525.27, 528.97, 532.61, 536.07, 539.46, 542.99, 546.31, 549.5, 552.52, 555.31, 557.96, 560.44, 562.34, 564.05], 'isorted_merge_batches_20': [18.17, 23.06, 24.47, 25.88, 27.22, 28.53, 29.97, 31.57, 33.01, 34.4, 36.07, 37.49, 38.91, 40.25, 41.55, 42.85, 44.26, 45.68, 47.09, 48.57, 50.04, 51.61, 53.15, 54.68, 56.2, 57.88, 59.67, 61.27, 63.19, 64.94, 66.7, 68.57, 70.3, 72.04, 73.64, 75.14, 76.62, 78.2, 79.78, 81.28, 82.77, 84.35, 85.92, 87.68, 89.23, 90.65, 92.09, 93.48, 94.98, 96.42, 97.92, 99.45, 100.93, 102.45, 103.94, 105.5, 107.09, 108.58, 109.99, 111.37, 113.33, 115.02, 116.52, 118.26, 119.82, 121.32, 122.86, 124.43, 126.0, 127.52, 129.05, 130.54, 132.43, 134.19, 135.73, 137.28, 139.08, 140.66, 142.2, 143.75, 145.18, 146.65, 148.32, 149.86, 151.49, 153.19, 155.04, 156.9, 158.63, 160.49, 162.41, 164.21, 166.03, 167.77, 169.57, 171.48, 173.3, 174.98, 176.46, 177.87, 179.32], 'isorted_merge_batches_1000': [13.54, 14.32, 15.05, 15.69, 16.32, 17.05, 17.64, 18.29, 18.9, 19.5, 20.11, 20.69, 21.28, 21.91, 22.48, 23.05, 23.62, 24.22, 24.96, 25.55, 26.14, 26.78, 27.36, 27.93, 28.52, 29.12, 29.88, 30.46, 31.04, 31.63, 32.25, 32.85, 33.45, 34.04, 34.64, 35.31, 35.9, 36.56, 37.28, 37.92, 38.51, 39.19, 39.86, 40.49, 41.1, 41.85, 42.5, 43.14, 43.71, 44.36, 45.03, 45.64, 46.23, 46.97, 47.58, 48.17, 48.8, 49.39, 50.01, 50.59, 51.19, 51.81, 52.39, 52.96, 53.59, 54.19, 54.77, 55.44, 56.16, 56.87, 57.47, 58.07, 58.68, 59.26, 59.84, 60.47, 61.05, 61.68, 62.3, 62.88, 63.53, 64.1, 64.67, 65.28, 65.9, 66.57, 67.22, 67.83, 68.43, 69.01, 69.58, 70.2, 70.79, 71.37, 72.05, 72.75, 73.35, 74.02, 74.63, 75.38, 76.12], 'isorted_quicksort_stable': [0.23, 22.01, 23.96, 25.16, 26.49, 27.55, 28.71, 30.23, 31.33, 34.16, 35.14, 36.58, 37.66, 38.78, 41.19, 42.5, 43.51, 44.6, 45.93, 49.66, 50.7, 51.76, 53.23, 54.53, 55.48, 56.93, 58.01, 60.28, 61.33, 62.29, 63.56, 68.35, 69.37, 70.29, 71.55, 73.32, 74.68, 75.73, 76.92, 80.76, 81.84, 82.9, 84.49, 85.71, 86.83, 90.76, 91.88, 93.61, 94.59, 95.89, 97.04, 98.94, 100.68, 101.63, 102.98, 103.93, 104.91, 115.58, 116.77, 117.92, 119.44, 120.5, 122.5, 123.42, 124.79, 125.67, 127.99, 129.07, 130.42, 131.46, 133.23, 134.29, 135.28, 137.65, 138.6, 139.75, 141.5, 142.56, 143.84, 145.05, 147.68, 148.86, 150.95, 152.6, 153.92, 155.08, 156.31, 159.99, 161.1, 162.4, 163.54, 164.63, 166.15, 167.14, 169.53, 170.69, 172.32, 174.17, 175.47, 176.55, 177.59]}
def benchmark():
seed(1000)
xs = [random() for _ in range(10**5)]
times = {f: [1e999] for f in funcs}
for _ in range(10):
for f in funcs:
ixs = iter(xs)
t0 = time()
it = f(ixs)
ts = [time() - t0]
for _ in range(100):
next(islice(it, 1000, 0), None)
ts.append(time() - t0)
times[f] = min(times[f], ts, key=lambda ts: ts[-1])
return {f.__name__: [round(t * 1e3, 2) for t in ts] for f, ts in times.items()}
if not times:
times = benchmark()
print(times)
############################################################
# Plot
############################################################
import matplotlib.pyplot as plt
x = range(101)
for name, y in times.items():
plt.plot(x, y, label=name)
plt.ylim(0, 200)
plt.title('isorting [random() for _ in range(10**5)]', weight='bold')
plt.xlabel('percent iterated', weight='bold')
plt.ylabel('time in milliseconds', weight='bold')
plt.legend(loc='upper left')
plt.savefig('isorted.png', dpi=200)