Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Need a faster way to find matches

by bobf (Monsignor)
on Jan 17, 2010 at 08:00 UTC ( #817833=note: print w/ replies, xml ) Need Help??


in reply to Need a faster way to find matches

I may be missing something here, but if you are only testing the least significant bit aren't you simply testing whether the integers are even or odd?

Since there are only two possible groups (even or odd), it seems overkill to use a hash to store all possible combinations of integers in each group. Why not store the odd numbers (since you want the least significant bit set) in an array, then compute the possible combinations afterwards? See Math::Combinatorics for one option.

Update: If you need the results in a hash, it could be populated while constructing the combinations of odd numbers. I suspect that most of the time (and memory) required for your routine is spent on the storage steps, not on the bitwise comparison itself.

Update 2: I misread the question, thinking that the comparison only included the last bit. As BrowserUK notes below, this is not correct. Apologies for the misunderstanding.


Comment on Re: Need a faster way to find matches
Re^2: Need a faster way to find matches
by CountZero (Bishop) on Jan 17, 2010 at 09:05 UTC
    Math::Combinatorics will not do the trick: it will give you all the permutations of an array or list, but cannot do nPk where n < k. Use Algorithm::Permute for that.

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

Re^2: Need a faster way to find matches
by BrowserUk (Pope) on Jan 17, 2010 at 10:30 UTC
    only least significant bit overlaps

    Is quite different to just odd or even:

    $x = 0b1111_1110_1101_1100_1011_1010_1001_1000_0111_0110_0101_0100_001 +1_0011;; $y = 0b0000_0001_0010_0011_0100_0101_0110_0111_1000_1001_1010_1011_110 +0_1101;; printf "%064b\n", $x & $y;; 0000000000000000000000000000000000000000000000000000000000000001

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Need a faster way to find matches
by remzak (Acolyte) on Jan 17, 2010 at 13:30 UTC
    BrowserUk gave a great example... I am really looking for the integers in the list that do not share any bits except the lsb.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://817833]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2014-08-31 07:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (294 votes), past polls