PwnallthethingsFeb 16, 2023
Had to implement a sorting algorithm today for the first time in my entire career, so i guess finally learning about them decades ago paid off
Show threadPwnallthethingsFeb 16, 2023

Unfortunately since then, I've also learned about test-driven development, and forgotten everything I learned back then. So just went with

1. First implement a test routine "IsSorted(list)" to check the algorithm is right

Sort(list):
While(!IsSorted(list))
SwapRandomEntries(list);
return

Show threadPwnallthethingsFeb 16, 2023
Screw you computer science, computer go brrr.
Show threadSteve Bellovin
@Pwnallthethings The computational complexity of your solution is, umm, impressive…
Feb 16, 2023 at 3:51amWeb
Show threadPwnallthethingsFeb 16, 2023
@SteveBellovin but it works
Show threadSteve BellovinFeb 16, 2023
@Pwnallthethings And for reasonably small array sizes, it's not even too awful. Plus, you get your correctness test built-in. But for larger N—well, I wouldn't want to try that… (More seriously: as Kernighan has noted: first, get it right. Second, measure to find your real bottlenecks. Only then, optimize, and optimize in the right spots. In my formulation, there's no point to getting the wrong answer quickly.)
Show threadJohnMasheyFeb 16, 2023
@SteveBellovin @Pwnallthethings
And for *serious* sorting, Ordinal Technology's parallel nsort was already terrific in the 1990s on SGI multiprocessors (and others' as well):
2000 Paper by Ordinal's Chris Nyberg & Charles Koester & Microsoft's Jim Gray.
http://www.ordinal.com/NsortPara.pdf
Website: http://www.ordinal.com/
Show threadNicholas WeaverFeb 16, 2023
@SteveBellovin @Pwnallthethings
Relatedly, probably the most important concept we teach in the computer architecture class is Amdahl's law. "Only bother to optimize the bottlenecks", and programmer time matters too:
The runtime of your program is not just the runtime of your program, but the aggregate runtime of all invocations + the time it took you to write it in the first place.
Show threadPwnallthethingsFeb 16, 2023
@ncweaver @SteveBellovin 1000%. Which is why most libcs have weird aggressively hand-optimized memcpy routines, but qsort has stayed meh. Because qsort gets called almost never, and memcpy gets called so often in a normal run that even processor manufacturers come up with creative ways to do it faster.
Show threadCorey Rayburn YungFeb 16, 2023
@Pwnallthethings @SteveBellovin my high school computer science teacher used random sort as the baseline algorithm to compare other methods against it. Unfortunately for her, the first time she ran it, it beat all the other methods. Randomization is randomly better.
Show threadJames GarryFeb 16, 2023

@coreyrayburnyung @Pwnallthethings @SteveBellovin

And when quantum computing comes of age we'll just throw bits around randomly and rely on at least *one* reality getting it 'right'.

That'll be my excuse.

Show threadKris Sargent, MDFeb 16, 2023
@Pwnallthethings @SteveBellovin in the same sense as the monkeys, typewriters and the plays of Shakespeare... yes, it does.
Show threadWilliam HeroldFeb 16, 2023
@SteveBellovin @Pwnallthethings O(?)
Show threaddjmFeb 16, 2023
@willigula @SteveBellovin @Pwnallthethings O(My)
Show threadWilliam HeroldFeb 20, 2023
@djm @SteveBellovin @Pwnallthethings George Takei has entered the chat