Solving “Two Sum” in C with a tiny hash table

https://nullprogram.com/blog/2023/06/26/

by ingve • 3 years ago

115 45 3 years ago

nullprogram.com

badtension• 3 years ago

I 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• 3 years ago

All you need is a mumrmur hash function to create a hash table. That is something that people should copy.

tialaramex6• 3 years ago

This (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.

tromp4• 3 years ago

Sorting 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• 3 years ago

The 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).

tromp4• 3 years ago

You can use radix sort which is linear for fixed width ints.

jjgreen• 3 years ago

O(n log n + n) = O(n log n)

tromp4• 3 years ago

Although 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• 3 years ago

Even 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• 3 years ago

What's log base 2 of a million or a billion?

nkurz• 3 years ago

I think it's a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version. You'd have to keep an additional mapping from the sorted to original positions. And are we counting the sorting and space for the maps as free? Or do we have to account for them somehow?

Mostly, I just don't like the problem specification. What does it actually mean to "solve it efficiently"? How many times are we going to be searching each input array? How much memory do we have available? What tradeoff between memory and computation is allowable? How much does a comparison cost us versus accessing memory? Are all targets equally likely?

Assuming as theoretical computer scientists tend to do that we can ignore all constant time operations, that access to memory is free, that an unknown but fixed amount memory is available, and that we'll be searching the same array forever ruins the problem for me. Fill in the numbers and we can talk about what's optimal, but the "spherical cow" approach does nothing for me.

tromp4• 3 years ago

I think it's a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version.

Good point.

You'd have to keep an additional mapping from the sorted to original positions.

It's simpler to just find the two numbers in the original unsorted array.

raverbashing• 3 years ago

You'd have to keep an additional mapping from the sorted to original positions.

2*O(n) is still O(n)

tialaramex6• 3 years ago

For the specifics, as someone else observed, walking nums to find the values we've discovered and identify their indices is very affordable, it's N operations, and if we can't afford N we're in trouble since we definitely need to do at least N comparisons.

To your general point, sure, one thing that's nice (but takes a colossal effort) about Advent of Code is that it has specific inputs for players, and they have specific answers, so although it's usual for participants to write code which could (you hope) solve the problem in the abstract, the actual test is whether you solved the input you actually had. Sometimes not all conceivable inputs are even tractable (and some people find this situation frustrating if it happens) only the inputs given to real players may be suitable.

For this exercise the provided Go solution gets to handwave a bunch of problems. For example, Go's "map" hash table allocates whenever it wants to and has amortized table growth on top. That can really add up for a problem like this.

If I attacked it in Rust I would make HashMap::with_capacity(nums.len()) which does a single allocation up front, I might not need all this space if I exit early, but it won't hurt. I don't know if there's even a way to write that in Go.

marginalia_nu• 3 years ago

For an input array of values I[], create an array A = [ 0 ... n ] so that n = len(I). Sort the indices in A based on their corresponding value in I. Now A is the mapping, A[n] is the index in I of the n+1:th largest value, and you can binary search in the same way, by comparing I[A[i]].

This is strictly more space efficient than a hash table. You're not going to win any awards for being cache efficient, but then again, when the competition is a damn hash table it's not too bad ;P

ape4• 3 years ago

It seems like it could be a "waste" to make a hash or sorted list only to throw throw it away after one use. Depending on what's required.

floor_• 3 years ago

Just a warning that this is secretly a GO article for those who are GO-intolerant.

chongli• 3 years ago

Yes. 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• 3 years ago

... I'm sure there is some C code there. In fact most code is in C.

codetrotter• 3 years ago

Well, at least it’s not Rust am I right fellas? Hahahah

(I like Rust.)

mananaysiempre• 3 years ago

Linear 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/03cd8a7b0e47f2141a1dbdad9f... via https://lukasatkinson.de/2018/interface-dispatch/

Xeoncross• 3 years ago

I'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.

taeric2• 3 years ago

I 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.)

Const-me4• 3 years ago

Given 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/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.

attractivechaos2• 3 years ago

std::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

Const-me4• 3 years ago

Adding `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.

creata• 3 years ago

Can someone explain why std::unordered_map has to be slow?

I vaguely remember that it's because it isn't allowed to invalidate references when inserting elements.

_a_a_a_2• 3 years ago

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.

Sounds reasonable

for a small N of 10000

Ah, now that is not what I would call a small N

Solving “Two Sum” in C with a tiny hash table

Related Stories