6 ms·
Solving “Two Sum” in C with a tiny hash table
- floor_ 3y agoJust a warning that this is secretly a GO article for those who are GO-intolerant.
- chongli 3y agoYes. There’s not a single line of C code in it. It’s practically a bait-and-switch. Edit: you’re right. There is C code intermixed with Go. It’s tricky to tell apart on a skim. Need to read carefully
- o1y32 3y ago... I'm sure there is some C code there. In fact most code is in C.
- codetrotter 3y agoWell, at least it’s not Rust am I right fellas? Hahahah (I like Rust.)
- badtension 3y agoI was really hoping for something more creative than the traditional hashmap approach. Still pretty cool, I wish I was that confident with rolling my own data structures.
- abhishekjha 3y agoAll you need is a mumrmur hash function to create a hash table. That is something that people should copy.
- tialaramex 3y agoThis (a hash table) is a basic vocabulary type, and it's only barely understandable that C doesn't provide one given when it was invented. The hash table which people are likely to knock together this way in C isn't very good, which makes sense - but if the C library provided one then the effort to do it well only needs to happen once. This isn't like say, Bloom filters where most people don't need one. It's like sort, which I notice C does provide in its standard library.
- camel-cdr 3y ago> but if the C library provided one then the effort to do it well only needs to happen once. It would've happened only once, but in 1987, and then we would've stuck with it, because every body relies on the exact behavior. Just look at `rand()`, it's basically unusable.
- teo_zero 3y ago> Just look at `rand()`, it's basically unusable. It does have some limitations you must be aware of, but "unusable"?
- jandrese 3y agoIt's not technically C stdlib, but POSIX.1 is the next best thing: https://linux.die.net/man/3/hcreate https://linux.die.net/man/3/hcreate That said, the implementation leaves a lot to be desired.
- tromp 3y agoSorting provides a alternative solution: sort the array, and then traverse a linear path over pairs of indices from (0,n-1) to (n-1,0) whose sum straddles the target: int main() { /* read in and sort array a */ int i=0,j=N-1, sum; while ((sum = a[i] + a[j]) != tgt) { if (sum < tgt) i++; else j--; } printf("%d %d\n", i, j); }
- colejohnson66 3y agoThe hashmap solution here is ideally O(n) as you only iterate once (assuming O(1) lookups and inserts in the map). A sort/search method, even using quicksort would be O(n*logn).
- tromp 3y agoYou can use radix sort which is linear for fixed width ints.
- jjgreen 3y agoO(n log n + n) = O(n log n)
- tromp 3y agoAlthough hashmaps are O(n) in practice, they can be worse than O(n log n) on some rare inputs that cause lots of hash collisions. Several sorting algorithms such as mergesort and heapsort are guaranteed O(n log n).
- enedil 3y agoEven it it was O(1) not amortized, it's not possible to beat the sorting in actual execution time for reasonable inputs (less than 10B elements probably)
- topposter32 3y agoWhat's log base 2 of a million or a billion?
- nkurz 3y ago
- mananaysiempre 3y agoLinear probing for a hash table that you’re not going to delete things from. Textbooks usually tell you to prefer other probing patterns unless you need deletion (and e.g. Go interface casts use quadratic probing[1]). Or is it still advantageous for some reason? (Locality?) [1] https://github.com/golang/go/blob/03cd8a7b0e47f2141a1dbdad9fdce175942d5515/src/runtime/iface.go#L95-L118 https://github.com/golang/go/blob/03cd8a7b0e47f2141a1dbdad9f... via https://lukasatkinson.de/2018/interface-dispatch/ https://lukasatkinson.de/2018/interface-dispatch/
- Xeoncross 3y agoI'm sure my next interview to require I know this "optimum solution". Jokes aside, I'm very glad to see another article using more than a single language to showcase something. Chances are much higher I can read one language well, or parts of both.
- deleted 3y ago[deleted]
- taeric 3y agoI used to use this as an interview question. I passed people more for being able to talk about different tradeoffs than any optimum solution, though. Gave a yes vote to more than a few that messed up and had bugs. (Granted, most of the bugs were in extending this to the "3 sum" idea.)
- deleted 3y ago[deleted]
- Const-me 3y agoGiven the constraints, the proposed implementation is not efficient at all. Here’s a quick benchmark to compare two implementations: https://gist.github.com/Const-me/265b8a3e89f17f4268d34d64771ef0ab https://gist.github.com/Const-me/265b8a3e89f17f4268d34d64771... In theory, the hash map is O(n), and std::sort approach is O(n*log(n)) And yet when measured on my computer, std::sort is more than twice as fast. Specifically, for hash map my program prints 3574736 (best of 10 tries), for std::sort only 1695712. My CPU base frequency is 3.8 GHz, so these numbers measured with RDTSC translate to 941 and 446 microseconds, respectively. I’m using a CPU with AMD Zen 3 cores, and compiled that code for AVX2 ISA, with Visual Studio 2022.
- attractivechaos 3y agostd::unordered_map is notoriously slow, several times slower than a fast hashmap implementation like Google's absl or Martin's robin-hood-hashing [1]. In addition, your implementation lets the hashmap grow from a small size. As you know the total length, you could preallocate the hash table and avoid rehashing. As typical hash table implementations double the capacity during rehashing, preallocating the buckets should be about twice as fast if we don't consider the cache and the complex mechanism behind the STL allocator. That said, std::sort is not the fastest sort implementation, either. It is hard to say which is faster for a small N of 10000. Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. [1]: https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing
- Const-me 3y agoAdding `map.reserve( vec.size() );` indeed helped, but still slower than sorting these entries. Specifically, the time for the hash map is 740 μs this way. I think the main reason for the observed behavior is memory management. The sorted vector takes under 80kb of RAM, allocated with a single malloc() call, and the entire vector fits in L2 cache which is very fast to access. OTOH, without advanced shenanigans like custom allocators, the hash map needs 1 malloc() call per entry. On a general note, I noticed that when the data being handled fits in the faster in-core caches, dense buffers pretty often perform best, despite these theoretical big O-s. Even if this means spending some extra time to sort the data.