in reply to Need a faster way to find matches

The secret is that there are only 63 bits and that any number with a certain bit set can not 'match' any number with that same bit set.

So all you need to do is get a list of all the elements with a bit set and compare them with all of the numbers with out that bit set.

By using a hash in place of the list we can do this pretty efficiently.

  1. Create the hash from the list.
  2. get a list of all the numbers with the 2**1 bit set.
  3. remove those numbers from the hash.
  4. compare them against the numbers in the hash
  5. repeat for 2**2 through 2**63
You do need to fix up the generated hash afterwards, as it will on have half of the keys in it.
use strict; use vars qw (@LongListOfIntegers %bighash %MatchedIntegers); my $x = 20; push( @LongListOfIntegers, int( rand( 2**8 ) ) ) while ( $x-- ); $bighash{$_} = 0 for @LongListOfIntegers; for my $bit (1..63) { my $n = 2 ** $bit; my @slist = grep( { ($_ & $n) } keys %bighash); delete $bighash{$_} for @slist; my $x = 0; for my $i (@slist) { for my $j (keys %bighash) { $MatchedIntegers{$i}{$j}++ if ( ( $i & $j ) == 1 ); $x++ if ( ( $i & $j) == 1 ); } } } normalize(\%MatchedIntegers); use Data::Dumper; print Dumper \%MatchedIntegers; sub normalize { my $hash = shift; for my $o (keys %{$hash}) { for my $i (keys %{$hash->{$o}}) { $hash->{$i}{$o}++; } } }
note: It is also easy to split the problem up into 63 problems and use POE or some such to run each on a separate processor -- if you have 63 processors on your computer.
-- gam3
A picture is worth a thousand words, but takes 200K.