4 ms·
A fun trivia point that I have never seen anyone exploit, for many cases a linear search with a sentinel value can outperform a binary search. It is amusing to
by taeric 10y ago
A fun trivia point that I have never seen anyone exploit, for many cases a linear search with a sentinel value can outperform a binary search. It is amusing to see the lengths people go through to optimize collections that will never be more than 1k in size, only to actually be working against the things computers are really good at.
- skolos 10y agoNever heard of the linear search with a sentinel value so needed to look it up. Here is a link in case anyone wants to learn what it is: http://www.delorie.com/gnu/docs/avl/libavl_26.html http://www.delorie.com/gnu/docs/avl/libavl_26.html
- renox 10y agoAndrei Alexandrescu describe the usage of this kind of search to speed up quicksort in his 'Fastware' (fun) video: https://www.youtube.com/watch?v=AxnotgLql0k https://www.youtube.com/watch?v=AxnotgLql0k Discussed here: https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/ https://www.reddit.com/r/programming/comments/4jlkhv/accu_20...
- ludwigschubert 10y agoComputer science curricula usually contain an introductory algorithms and data structures class, but these don't usually put focus on topics like cache locality or branch prediction. Do you agree? And if so, would that—at least partially—explain your observation?
- taeric 10y agoI honestly don't know. I should call out that my number of 1k is probably wrong. I wouldn't be surprised if it is too high. Though, it will probably depend a lot on caching. Basically, it is a hard thing where being wrong flat out doesn't matter the vast majority of the time. I think education does folks a disservice by asking "what is the fastest" or "which one should you choose" in many scenarios. Instead, we want people to be able to reason about all of the choices more holistically, which is not an easy task.
- Analemma_ 10y agoMy undergraduate algorithms course did point out that memory hierarchies and branch predictors laugh at big-O notation, and that you should always (as Roboprog said) measure measure measure instead of just assuming a particular algo is best. It was one little piece of material in a course with a lot of ground to cover though, so it's hard to say how well it stuck with the class...
- kazinator 10y agoThis is covered in digital design and computer architecture courses. But kind of in isolation from data structures and algorithms.
- Roboprog 10y agoInteresting. Yeah, performance tuning is a deep well to fall into :-) Measure, measure, measure. How (memory) expensive is the element-matches check (can the array bound or address of final element stay in a register)? How often does the search fall off the end, vs finding something, perhaps in a list sorted in most often used order? Alternately, would a trie be better than an array search? (Depends on key length, set element count, usage patterns...)
- chadaustin 10y agoKinda. Paul Khuong goes into depth here. https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ https://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimin...