Closed jariji closed 1 year ago
Thanks for sharing! It's always fun to see new sorting algorithms :)
A quick test using rhsort's benchmarks indicates it's about 2x slower than Julia's default on its own benchmarks on my machine, which is still faster than almost all non-Julia sorting algorithms.
x@x dev % git clone https://github.com/mlochbaum/rhsort && cd rhsort
Cloning into 'rhsort'...
remote: Enumerating objects: 406, done.
remote: Counting objects: 100% (48/48), done.
remote: Compressing objects: 100% (40/40), done.
remote: Total 406 (delta 9), reused 39 (delta 8), pack-reused 358
Receiving objects: 100% (406/406), 242.29 KiB | 1.25 MiB/s, done.
Resolving deltas: 100% (227/227), done.
x@x rhsort % gcc bench.c -o bench && ./bench && git rev-parse HEAD
In file included from bench.c:80:
./rhsort.c:170:25: warning: while loop has empty body [-Wempty-body]
while (aux[--sz] == s); sz++;
^
./rhsort.c:170:25: note: put the semicolon on a separate line to silence this warning
1 warning generated.
Sorting random 4-byte integers: rhsort
Testing size 1000: best: 10.000 avg: 16.526 ns/v
Testing size 10000: best: 10.600 avg: 12.569 ns/v
Testing size 100000: best: 12.530 avg: 13.271 ns/v
Testing size 1000000: best: 16.825 avg: 18.294 ns/v
944ad9dc4b8f0d16dcdb471b9eaf99856c3fd0f0
x@x rhsort % julia -e 'using BenchmarkTools, Random, Printf, InteractiveUtils
for n in 10 .^ (3:6)
v = rand(Int32, n)
result = @benchmark sort($v) setup=(rand!($v)) evals=1 gctrial=false samples=3e7/n
@printf "Testing size %8i: best: %6.3f avg: %6.3f ns/v\n" n minimum(result.times)/n mean(result.times)/n
end
versioninfo()'
Testing size 1000: best: 5.125 avg: 7.125 ns/v
Testing size 10000: best: 4.546 avg: 5.722 ns/v
Testing size 100000: best: 4.622 avg: 5.174 ns/v
Testing size 1000000: best: 5.010 avg: 5.280 ns/v
Julia Version 1.9.1
Commit 147bdf428cd (2023-06-07 08:27 UTC)
Platform Info:
OS: macOS (arm64-apple-darwin22.4.0)
CPU: 8 × Apple M2
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-14.0.6 (ORCJIT, apple-m1)
Threads: 1 on 4 virtual cores
I was misusing rhsort. It is actually quite fast on its own benchmarks, however, it unfortunately does not support sorting 64-bit floating point numbers so I can't add it this this repo.
Just for interest - I found this sort that looks good for some applications. https://github.com/mlochbaum/rhsort