Re:What to use instead of std::set [pdf]
by Analemma_ on Thursday August 25, 2016 @01:08PM
(#12360654)
My 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...
I 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.
Do you agree? And if so, would that—at least partially—explain your observation?