5 ms·

Adventures in Nerdsnipery

64 points by luu 9y ago

TTPrograms 9y ago
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.
- ohyes 9y ago
  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.
  - dithering 9y ago
    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.
    - ohyes 9y ago
      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.
  - jfoutz 9y ago
    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.
- nandemo 9y ago
  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).
librexpr 9y ago
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.
- fred256 9y ago
  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.
jsnell 9y ago
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.
- 0xB504 9y ago
  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.
0xB504 9y ago
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?
- panic 9y ago
  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.
gerdesj 9y ago
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.
- lgas 9y ago
  The post doesn't appear to be making any arguments.
a_e_k 9y ago
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.
- SamReidHughes 9y ago
  It won't be faster, but it would save on memory if you're short on that.
debatem1 9y ago
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.
- debatem1 9y ago
  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?
eutectic 9y ago
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.

64 points by luu 9y ago

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.

ohyes 9y ago
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.
- dithering 9y ago
  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.
  - ohyes 9y ago
    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.
- jfoutz 9y ago
  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.
nandemo 9y ago
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).

librexpr 9y ago

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.

fred256 9y ago
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.

jsnell 9y ago

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.

0xB504 9y ago
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.

0xB504 9y ago

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?

panic 9y ago
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.

gerdesj 9y ago

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.

lgas 9y ago
The post doesn't appear to be making any arguments.

a_e_k 9y ago

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.

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

debatem1 9y ago

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.

debatem1 9y ago
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?

eutectic 9y ago

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.