Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

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.

In reply to Partition in to 63 parts by gam3
in thread Need a faster way to find matches by remzak

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (2)
As of 2022-05-18 02:37 GMT
Find Nodes?
    Voting Booth?
    Do you prefer to work remotely?

    Results (68 votes). Check out past polls.