Keep It Simple, Stupid PerlMonks

Re^3: Need a faster way to find matches

by kikuchiyo (Monk)
 on Jan 17, 2010 at 17:18 UTC ( #817881=note: print w/replies, xml ) Need Help??

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

If they are all odd numbers, then their LSB is always 1, isn't it?
Why don't you just drop that bit then, and test for the bitwise ANDs of the resulting numbers being 0?

```my @chopped_array = map { \$_ >> 1 } @original_array;
my %result;

foreach my \$i1 (0..\$#chopped_array) {
foreach my \$i2 (\$i1..\$#chopped_array) {
\$result{ \$original_array[\$i1] } = \$original_array[\$i2] unless
+\$chopped_array[\$i1] & \$chopped_array[\$i2];
}
}

This algorithm is still quadratic, though - you still need to do N^2/2 comparisons for an N-sized array.

But what if you build an auxiliary hash out of those lsb-shifted-off integers, then for every value simply check whether the bitwise negated value is present among the hash keys?

```my %hash = map { (\$_ >> 1) => 1 } @original_array;
my %result;
foreach (keys %hash) {
\$result{(\$_ << 1) + 1} = ~(\$_ << 1) if \$hash{ ~\$_ };
}
Or something like this.

Beware of bugs, as I have not tested the code above, nor have I proved it correct :)

Replies are listed 'Best First'.
Re^4: Need a faster way to find matches
by remzak (Acolyte) on Jan 17, 2010 at 18:19 UTC
I love the idea of going from N^2/2 to N. Unfortunately, the valid pairs are not the bitwise negated value; it could be that one, but also other values that don't have all the possible (negated) bits set.
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?
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.

Create A New User
Node Status?
node history
Node Type: note [id://817881]
help
Chatterbox?
 Discipulus SharePoint will insinuate in my \$workspace I think i'll need alot of patience.. [erix]: about perfide albion [erix]: I guess that should be Perfidious Albion

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2017-06-27 08:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (601 votes). Check out past polls.