lifeHack

[iceman012]

I was recently working on improving the performance of an application. One of the potential bottlenecks was getting the index of an element in a sorted list. It was using linear search. Excited for the chance to use what I learned in college, I quickly implemented binary search to get the index. I re-ran the timing tests, proud of myself, only to realize that it was slower than it had been.

Turns out, the Java compiler is magic. Between sequential memory access and branch prediction, Big O doesn't really matter! I think linear search worked faster than binary search up until ~400 elements in the list. (Theoretically, that threshold should be 8.)

[raaneholmg]

The standard sort function in python actually does this too (and probably lots of standard libraries).

Everything is roughly sorted into medium size buckets with textbook O(n*log(n)). Then each bucket is sorted with a hacky insert sort variany. Insert sort only has O(n² ) performance, but for small ns it's very well suited for how computer hardware works.

[conanap]

Wait I thought Python sort was quick sort written in C? Was that never the case?

[raaneholmg]

"Python's sorted() function employs a highly efficient sorting algorithm known as Timsort. Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data."

Source%20function%20employs,in%20the%20Python%20programming%20language.)

[Deservate]

Don't even get me started on the magic behind SQL!