News for hackers. Stuff that matters.
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.
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.
Re:Efficient Immutable Collections [pdf] by anarazel on Monday August 14, 2017 @04:03AM (#15007203)
Right, which is why nobody ever used qsort. Or, wait. It's been widely used for a long time...
Re:Efficient Immutable Collections [pdf] by amelius on Monday August 14, 2017 @04:14AM (#15007232)
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.

Re:Efficient Immutable Collections [pdf] by kcorbitt on Monday August 14, 2017 @12:36PM (#15010015)
Actually, big-O complexity by definition is determined based on the worst case. https://stackoverflow.com/questions/3230122/big-oh-vs-big-th...
Re:Efficient Immutable Collections [pdf] by anarazel on Monday August 14, 2017 @02:34PM (#15011214)
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.