3 ms·
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,
by 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 agoSurely 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 agoIf 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 agoYou 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.