4 ms·
> So O(n) could be faster than O(log n) depending on the size of the data structure and interactions with RAM pre-fetch, etc. This has always been the case. Th
by SkiFire13 22d ago
> So O(n) could be faster than O(log n) depending on the size of the data structure and interactions with RAM pre-fetch, etc.
This has always been the case. The RAM effects only changed at which point the O(n) stops being faster than the O(log n) solution.
- inigyou 22d agoApparently linear search now beats hashmap if you have less than TWO HUNDRED elements. Crazy!
- afdbcreid 22d agoBut when you compare native integers, not something more complicated, right?
- zbentley 21d agoDepends. Are you searching for the complicated thing by identity, or in a system that caches identities and/or interns objects of the type you’re handling? All Of those can result in searches being word-based and thus vectorizable/cache-sympathetic more often.
- spockz 22d agoSo now the result of `new HashMap<>()` should be backed by an array for the first 200 elements or so? Potentially the size depending on the L1 size etc.
- SkiFire13 21d agoFor which key types, hashmap implementation, and hasher? Depending on these factors hashmaps performance can vary a lot.