HN Gopher Feed (2017-06-29) - page 2 of 10
Adventures in Nerdsnipery
33 points by luuhttps://burntpizza.github.io/2017/06/27/pairs-adventures-in-nerd...
librexpr - 47 minutes 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.
TTPrograms - 2 hours 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 - 1 hours 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 - 1 hours 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 - 1 hours 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
jsnell - 21 minutes 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.