3 ms·
This seems like a clumsy way to make a simpler and more generic point: any key/value data structure (at least one that relies on inspecting the key in its entir
by ajross 17y ago
This seems like a clumsy way to make a simpler and more generic point: any key/value data structure (at least one that relies on inspecting the key in its entirety) will scale as O(NlogN) at very large sizes. The reason is that the size of a key needed to identify a unique entry in a table of size M is at least log2(M) bits long. So the primitive operations on the keys is bounded by log2(M) and is not constant.
This is the same reason that "radix sort" (http://en.wikipedia.org/wiki/Radix_sort http://en.wikipedia.org/wiki/Radix_sort) isn't a linear operation even though it doesn't seem to have a log(N) dependence on the input set. The number of radix buckets scales as log(N).
That said, of course, this doesn't mean much in practice, where primitive operations on keys live in L1 cache and the pointer indirections require DRAM cycles.
- lemire 17y agoMy post was specifically about vectorization. In which case, I do claim that it matters.