scandum

10 ms·

31.
by scandum 4y ago
Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood. While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions i
32.
by scandum 4y ago
Quadsort's author here. This is the first time I've heard quadsort being called esoteric. It isn't much more complex than Timsort. It is however challenging to port ~1000 lines of code that can be tedious to debug. If you mak
33.
by scandum 4y ago
Blitsort is a hybrid quicksort, see title. It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort
34.
by scandum 4y ago
Quadsort, fluxsort, blitsort, and crumsort all qualify depending on your needs. skasort_cpy is pretty good on 32 bit integers if you give it n auxiliary memory. rhsort is very good and likely the best for 31 bit integers, but a bit rough ar
35.
by scandum 4y ago
>A nitpick, but my name is Orson Peters I actually knew that, not sure what went wrong in my brain. >I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine. You'll stil
36.
by scandum 4y ago
I'm not that interested as I'd prefer to count each move and prove it that way, but perhaps Peter (orlp) is interested?
37.
by scandum 4y ago
Isn't that what Rust is all about?
38.
by scandum 4y ago
Hard to answer. I think the main thing is that there are a lot of stumbling blocks, things that most people overlook, yet logical once you have it explained. Occasionally one is discovered and solved, and it can lead to a brief domino effec
39.
by scandum 4y ago
It's possible to implement a 64 item stack so you can call it O(1) and in-place. But that's such an effort in futility that I refuse to do so. So it's theoretically and practically in-place, but not technically.
40.
by scandum 4y ago
Hoi Peter, >I have a similar conjecture for glidesort but I'll have to do some thinking to see if I can prove it. It probably is technically O(n (log n)^2) moves, but I suspect that when the rotations are fast enough (trinity /
41.
by scandum 4y ago
It should be O(n log n) comparisons and technically O(n (log n)^2) moves. The moves are reduced by a relatively large constant however, and blitsort might qualify as O(n log n) moves when given sqrt(n) aux. In your Youtube presentation you
42.
Blitsort: A fast, in-place stable hybrid merge/quick sort(github.com)
202 points by scandum 4y ago|88 comments
43.
by scandum 5y ago
Main reasons for not benching against pdqsort: 1. stability 2. worse performance on long doubles, and I don't know why 3. A variety of hard to explain performance differences. 4. pdqsort does better on generic data, which can be very i
44.
by scandum 5y ago
The graph is with //#define cmp(a,b) ( (a) > (b)) in quadsort.h uncommented. Looking forward to your next spin.
45.
by scandum 5y ago
You can uncomment //#define cmp(a,b) (*(a) > *(b)) in quadsort.h for primitive inline comparisons.
46.
by scandum 5y ago
I get the impression you wrote your response rather hastily. Here's a bench of fluxsort vs pdqsort on strings: | Name | Items | Type | Best | Average | Compares | Samples | Distribution | | --------- | -----
47.
by scandum 5y ago
I updated the README slightly, it's mentioned twice now. :) As for performance considerations, blitsort's performance on integers is indicative of its performance on strings, while this isn't the case for pdqsort. I haven&#x2
48.
by scandum 5y ago
Correct, if you uncomment //#define cmp(a,b) (*(a) > *(b)) in blitsort.h it'll run about 25% faster. Probably still slower than a native C++ implementation since it'll evaluate to (a > b) > 0 rather than
49.
by scandum 5y ago
It is, those numbers are less favorable than they are on my own machine. The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.
50.
by scandum 5y ago
Hard to say which would be faster, I've made a mental note to benchmark sorting 16 byte long doubles through pointers as well as directly. I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h fil
51.
by scandum 5y ago
Given how fast pdq is there's indeed no reason not to adopt it. Probably the usual 'not invented here' mindset.
52.
by scandum 5y ago
Well, blitsort's performance is exceptional in the sense that it's 15% faster than the next fastest stable in-place sort. As for stability, it's useful when you need to sort a table with an integer index. So it might be of va
53.
by scandum 5y ago
Blitsort can sort strings, but something like a 12 byte data structure would require an array with pointer references to sort. As for the degradation against std:stable_sort: 5% slower at 1 million, 10% slower at 10 million, 20% slower at 1
54.
by scandum 5y ago
pdqsort isn't stable and still suffers from killer inputs. Not sure how well this will paste: Name | Items | Type | Best | Average | Loops | Samples | Distribution -------- | -------- | ---- | -------- | -----
55.
by scandum 5y ago
Might be worth noting that it's faster than quicksort, std::stable_sort, and timsort.
56.
by scandum 6y ago
It broke my heart, but I got rid of the quirky mars condition.
57.
I hacked together a truecolor Matrix Rain emulator for VT100 terminals(youtube.com)
1 points by scandum 6y ago|0 comments
58.
Wolfsort: An ultra-fast hybrid radix sort algorithm(github.com)
102 points by scandum 6y ago|27 comments
59.
Binary Search: A new implementation that is up to 25% faster(github.com)
171 points by scandum 6y ago|54 comments
60.
by scandum 7y ago
OneWeb will be worse than fiberoptics while Starlink will be better than fiberoptics. This suggests OneWeb is pretty much doomed to fail.

More ›