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?
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?
Beware of bugs, as I have not tested the code above, nor have I proved it correct :)
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?
Or something like this.my %hash = map { ($_ >> 1) => 1 } @original_array; my %result; foreach (keys %hash) { $result{($_ << 1) + 1} = ~($_ << 1) if $hash{ ~$_ }; }
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 | |
by kikuchiyo (Hermit) on Jan 17, 2010 at 19:17 UTC | |
by remzak (Acolyte) on Jan 18, 2010 at 00:25 UTC | |
by kikuchiyo (Hermit) on Jan 18, 2010 at 10:01 UTC |
In Section
Seekers of Perl Wisdom