Hacker News new | past | comments | ask | show | jobs | submit login

Update: The author is always using a collection of 1,000,000 entries. The horizontal axis is the number of lookups, into a collection of 1,000,000 entries, e.g. always ~ 20 entries in the tree. So the x-axis is logrithmic, but the y axis is linear and we expect the graph to be linear.

Original comment: Good question. The x-axis is logrithmic, the y axis is linear. Without cache effects, std::map and lower_bound should take logrithmic time, so should be a straight line on the graph. Also, unordered_map should be constant time, independent of size. So its either cache effects (including swapping / thrashing), or there's some other overhead that's dominating the whole thing, and the author isn't measuring what they think.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: