3 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 1mo 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 1mo agoApparently linear search now beats hashmap if you have less than TWO HUNDRED elements. Crazy!
- afdbcreid 1mo agoBut when you compare native integers, not something more complicated, right?
- zbentley 1mo 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 1mo 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 1mo agoFor which key types, hashmap implementation, and hasher? Depending on these factors hashmaps performance can vary a lot.