Overall seems like a great book. The hashing chapter is a bit half baked though. It claims without reservation that deletions simply cannot be efficiently implemented with linear probing. But there are at least two two efficient to do this (lazy deletions or just fix up the hash table), and both are worthwhile for students to know.
1/100 is too large of a cutoff imo. If you have a class of 96 students, there's a decent chance that an innocent student gets flagged for no reason. I hope he lets the student on the bubble off the hook.
One thing I'm confused about: Did the author try vectorizing the linear search implementation? (Of course, it is possible that even if they did not, the compiler did.) I would imagine that vectorization is behind the advice to use linear searches on small arrays.
> I would imagine that vectorization is behind the advice to use linear searches on small arrays.
I always thought a core part is that searching linearly is simply very cache efficient due to easy prefetching of linear data and that this is simply faster when you don’t have to search too much. Of course, that and vectorisation together is even better.
That said, I would expect the overhead of vectorization to dominate at smaller sizes, and the fact that linear search is... well... linear to dominate at larger sizes. There might be a sweet spot for a few dozen elements where it would be the best, but I think it'd be rather niche (and strictly limited to floats/integers).
Regarding cache effects of linear search, this entire article is under the assumption your data is in-cache, if not your results will vary (wildly).
One important caveat: it is widely believed that randomization does make a big difference for data structures problems. For example hash tables (which use random hash functions) take O(1) time per operation, but it is conjectured that no deterministic data structure can match this.
There are also problems in online algorithms where randomization provably changes what is possible, for example the "cup game problem." (https://arxiv.org/abs/1904.02861)
Finally, although randomized primality testing (1970s) is often credited as the start of randomized algorithms as a field, it's worth noting that hash tables (1954) and quick sort (1961) were much earlier.
are hash functions considered random? considering they are deterministic in their inputs and outputs. With randomised primality testing, you could use a true random number (based on e.g. nuclear decay) every time, and get the same correctness guarantees. With a hash table, you could never retrieve anything if you always used a true random number as a key every time.
I think it would be fair to say that it's a kind of funny trie-hash-table hybrid. What's neat though is that it manages to achieve better space bounds than either a trie or a hash table would on their own.
I didn't invent the algorithmic idea --- it's basically a simplification of a data structure that was published in ICALP 2003 [1]. As far as I know, the idea of combining hash tables and tries in this kind of way (despite being incredibly simple!) doesn't appear in either the theoretical or experimental literature prior to that.
I'd be interested in any other earlier sources that people might have.
Unless I'm misreading, the question as stated in the blog post never says there is only one duplicate (there might be many!), so in that sense I think his answer may be wrong. A more robust solution is just to have an array of n counters and just count how many times each item appears.
Also it was 2004 and 64 bit machines weren't common. If I remember correctly you had only 2 GB available under Windows XP and if you wanted more, 3 GB to be more precise, you had to boot with a special parameter.
32-bit machines generally 64-bit arithmetic of some sort; for example "long long" in C is mandated by the standard to be of a width greater than or equal to 64 bits.
Yeah, 64 bit integers were available under gcc on Linux, but the memory issue remained. The array had to fit in 2 GB, unless of course the problem stated otherwise, for example the numbers were read from a file.
There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those...
Also, since we are sorting integers, I'd also be interested to know how well a modern implementation of radix sort can be made.
:)
Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap.
We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the paper.
I previously also worked on radix sort: https://arxiv.org/abs/1008.2849
Interestingly, that 12 year old result on dual-socket/8 cores is only about twice as fast as a single AVX-512 core today.
