Adventures in Nerdsnipery | Hacker News Reader

Adventures in Nerdsnipery

burntpizza.github.io

64 pointsluu19 comments

The problem statement doesn't forbid duplicates. Let's assume K=1. Seems to me that both solutions from the post would return 2 for 7,7,8 and 1 for 7,8,8.

While either an answer of 1 or 2 could be justified by some definition of "pair", I can't think of a reasonable definition that would allow inconsistent return values for these two examples.

You could add a dublicate counter. Once out find a pair, let j increase until numbers[j] != numbers[j+1] and count how many duplicates you encounter. Add this number to pairs everytime you find one. Once you increase j set the duplicate counter back to one.

If we know that our HashSet is going to be containing u32s, couldn't we make a simple hash function that just takes the u32 and returns it? If our hashes are at least 32 bit, this would both guarantee there are no hash collisions, and be super fast.

Heck, if we dived into the guts of the HashSet implementation, we could even remove any collision checks, because we'd know they can't happen.

You could go even a step further and ditch the hash table altogether, and just use a 2^32 bit set. “Only” takes up half a gigabyte of memory.

For u32, the easy solution is to mmap enough space to hold a bitvector (4 billion/8b) then let sparse files do the rest for large (>32k entries) gaps. You'd then sum in wordlength blocks at k offset and popcnt. I'd be surprised if this wasn't the best behavior you could get trivially today. Depending on the processor you might win with SIMD or multithreading but you'd have to make the trade between them well unless you were really low on memory.

Herp, forgot duplicates. Sizing the entry correctly (logN) solves the issue and makes SIMD more compelling unless logN is << word size (or dupes are forbidden).

Which is actually an interesting case: what if the number of values is really small, say 8?

Shouldn't the time constraint be around O(n²) for the sorted approach, as you are iterating through the sorted array in a nested loop, resulting in (N - K)/2 *N lookups of pairs? Or am I missing something?

The value of j never decreases, is bounded above by numbers.len(), and increments each time through the inner loop. This means the inner loop can run a maximum of numbers.len() times.

Consider me sniped. My first thought was hashing mod k. Then when you create your hashmap you just check for collisions as you go and then test that they're k apart as opposed to 2k,3k etc. Then you don't have to scan through the hashmap again. It seems like if the parameters described in the problem are uniformly distributed, ie k is generally pretty big and you don't have a huge list of numbers then this initial filter would get you really close.

I had this thought too.

If you check N+K and N-K you only need to scan the numbers once.

The theoretically fastest implementation would probably use a bitmap, you'd only need 125 megabytes. (you'd dereference the offset and check the appropriate bit with a mask). It would be interesting to see if this is faster or slower. I'm going to go try it out.

Surely you only need to check N+K? Because if (N1,N2) satisfies N+K, then (N2,N1) must satisfy N-K?

You can also stop when you hit Nmax-K... might save a few lookups when K is large.

If you're computing the hash-table ahead of time you only need to do n+k.

If you're setting the value in the hash table as you check it (as you would in a single pass), you have to do n-k as well.

This is because the number you are currently adding didn't exist in the array when you checked n+k for the previous numbers.

You might get some milage out of partitioning on k, make k hashtables, for n, hash n/k into the n%k table. then just look for adjacency. doesn't improve the worst case at all, k=1, or all n's fall in the same bucket, but in the average (maybe? no idea about the actual data) case it would help with collisions, or reducing the size of the sorted arrays. Also, it becomes embarrassingly parallel. A trivial next step is one thread per hashtable.

Of course, all that overhead might be a big waste of time.

I might be wrong but that looks like O(n^2) in the worst case, namely when the input is some permutation of (a+k, a+2k,...,a+nk).

You could also efficiently sieve down the list of candidates with a Bloom filter.

Toss all the numbers into a Bloom filter, then scan through them again and cull any number, i, for which neither i-k nor i+k are present in the filter.

Then run through the (now reduced) remainder with one of the deterministic methods described in the post to get the final answer.

Not sure if it'll actually be faster, but it could be worth a try.

It won't be faster, but it would save on memory if you're short on that.

When you perform quicksort/radix sort you can identify the range of each partition as you go. You could then use this to inform your search, e.g. there's no point in searching within an interval of width <K.

So ... I read a well presented, and pretty, argument about stuff I don't really understand but can appreciate. I also appreciate this is on your personal blog so can be as noddy as you like.

Why not, when presenting an argument, be a little more formal and descriptive? You took the trouble to strike out text to show working. There is no need to go the full passive voice bollocks but a little more context might be handy.

HN attracts people from many disciplines and not all of us are DevOps kool kids who dream in Rust. A little more context might help us to really get to grips with your post.

The post doesn't appear to be making any arguments.

Reply on news.ycombinator.com