in reply to Need a faster way to find matches

Two comments:
  1. Your test is wrong: it does not check at all whether the least significant bit is set. Consider:
    • print 3 & 5; => 1
    • print 7 & 5; => 5
    In both of these tests the arguments have their LSB set, yet only the first test results in "1".

    The following tests the LSB of a variable: $value & 1

  2. Your inner loop is too long: if you know that both A and B have their significant bits set, then also B and A have their significant bits set By employing this symmetry you can eliminate half of your tests.
Update: Are you sure you want to have a hash with all the pairs of elements with the LSB set? This will quickly grow to enormous numbers: Assuming your integers are equally divided over odd and even numbers, the number of pairwise permutations will be 2000! (the factorial of 2000) which is larger than 10**499. Even if you can generate 1 million pairs per second, the program will run for more than 10**486 years.

Updated Update: Actually I was wrong: The number of permutations of subsets k drawn from a set of size n is n!/(n-k)! only, or in this case 2000! / 1998! or 2 000 * 1 999 = 3 998 000. Still a big number, but doable.

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

Replies are listed 'Best First'.
Re^2: Need a faster way to find matches
by remzak (Acolyte) on Jan 17, 2010 at 16:21 UTC
    CountZero, I did a poor job of explaining the test. BrowserUk realized what I intended. The list of integers is very specific, and was constructed meeting a rigid set of criteria; it is a pre-filtered list, the only known characteristic is that they are all odd numbers. The algorithm to build the list is quite fast (considering the large number of lines of code), and if the input parameters change the length of this list of integers will shrink or grow. Having said that, the list ranges in size from 10 elements (not as problem) to around 4,000 elements (my problem).
[reply]
      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];
    }
}

      [download]

      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{ ~$_ }; 
}

      [download]
      Or something like this.

      Beware of bugs, as I have not tested the code above, nor have I proved it correct :)
[reply]
[d/l]
[select]
        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.
[reply]

In Section Seekers of Perl Wisdom