Re:Efficient Immutable Collections [pdf]
by amelius on Monday August 14, 2017 @02:33AM
(#15006918)
Nice results, but in the old days, algorithms improved on other algorithms in the big-O sense.
[ Parent
| on HN ]
Re:Efficient Immutable Collections [pdf]
by Johnny_Brahms on Monday August 14, 2017 @06:54AM
(#15007774)
If asymptotic performance was everything, we would all be using Fibonacci heaps.
In reality other things matter.
Re:Efficient Immutable Collections [pdf]
by kristianp on Monday August 14, 2017 @03:20AM
(#15007072)
A lot more low-hanging fruit in the old days.
Right, which is why nobody ever used qsort. Or, wait. It's been widely used for a long time...
Well, I didn't say "worst case".
If qsort only provided a constant ratio time improvement over bubble sort in the average case, then it wouldn't have been so popular.
Actually, big-O complexity by definition is determined based on the worst case. https://stackoverflow.com/questions/3230122/big-oh-vs-big-th...
Sure, you can point to algorithms that nobody experienced ever uses. But if you e.g. compare qsort usage with heapsort usage, people use qsort because of it's better constant factors, even though the worst case complexity is worse.