Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^5: Need a faster way to find matches

by kikuchiyo (Pilgrim)
on Jan 17, 2010 at 19:17 UTC ( #817887=note: print w/replies, xml ) Need Help??

in reply to Re^4: Need a faster way to find matches
in thread Need a faster way to find matches

I don't understand then.

You stated the condition for a match as ($A & $B) == 1 where $A and $B are (64-bit, unsigned) integers.
Let $As = $A >> 1 and $Bs = $B >> 1.
Isn't then the original condition equivalent to ($As & $Bs) == 0 ?

For a given $A (and $As), what other $B (and $Bs) does satisfy that condition than $Bs = ~$As?

Replies are listed 'Best First'.
Re^6: Need a faster way to find matches
by remzak (Acolyte) on Jan 18, 2010 at 00:25 UTC
    I ended up using your idea of shifting off the least significant bit (saved some time doing !($i1 & $i2) instead of ($i1 & $i2) == 1).

    The criteria to be in the list is complex (and I don't want to go off-topic). The numbers are highly constrained, yet once they make it to the list, I need to find all pairs of numbers which do not share any common bits (after getting rid of the one shared lsb). Below is an example of a valid pair. The bit-wise complement may or may not exist in the list.

    #all values have been right shifted to get rid of lsb $i1 = 0b1010_0100; $i2 = 0b0100_1000; #the above two numbers are a valid pair. # yet my list may not contain either ~$i1 or ~$i2 $i1_bits_reversed = 0b0101_1011; $i2_bits_reversed = 0b1011_0111 # the above two numbers are not a valid pair,
    Does that example, clarify why the bitwise negation isn't a quick trick? I may be missing your approach altogether.
      Yes, I see it now.

      I must have misunderstood your condition "do not share any common bits" to mean ~($i1 XOR $i2) instead of $i1 & $i2. For example, the two numbers in the first example do "share" common bits in the sense that both bits are 0. In this case the only valid value for a given $i1 would be ~$i1 and nothing else.

      However, if the condition is $i1 & $i2 == 0, then you're right, there are several possible $i2's.

      Still, you may be still better off generating the list of possible values for every existing element of the array and check those instead of blindly doing all comparisons.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://817887]
[LanX]: Oh I see, userDict should have been declared in n outer scope ...
[LanX]: an
[LanX]: strange python accepts this?
[LanX]: no previous userDict?

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (13)
As of 2018-03-20 18:17 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (257 votes). Check out past polls.