in reply to Need a faster way to find matches

  1. You can save a small amount by removing a level of scope: 
    foreach my $i1 (@LongListOfIntegers) {
    ($i1 & $_)==1 and undef $MatchedIntegers{$i1}{$_} 
         foreach @LongListOfIntegers;
}

    [download]
  2. A little more by use integer; 
    foreach my $i1 (@LongListOfIntegers) {
    use integer;
    ($i1 & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
         foreach @LongListOfIntegers;
}

    [download]
  3. And if the values are evenly distributed, potentially save 75% of the runtime, by pre-filtering out any even values: 
    @LongListOfIntegers = grep $_ &1, @LongListOfIntegers;
foreach my $i1 (@LongListOfIntegers) {
    use integer;
    ($i1 & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
         foreach @LongListOfIntegers;
}

    [download]

Beyond that, any kind of categorisation of the values by the bits they have set (other than the LSB) will take far longer to set up.

It even seems unlikely that you could save much time by moving this into (Inline)C, given you want a hash as the result. To be honest 2 seconds for 16 million comparisons doesn't seem too bad.

Update: There's probably no need to have results for $x & $y and $y & $x in the hash, and even if there is, there's no need to test both. So, 

@LongListOfIntegers = grep $_ &1, @LongListOfIntegers;

foreach my $i1 ( 0 .. $#LongListOfIntegers) {
    use integer;
    my $v = $LongListOfIntegers[ $i1 ];
    ($v & $_) == 1 and undef $MatchedIntegers{$i1}{$_} 
        foreach @LongListOfIntegers[ $i1+1 .. $#LongListOfIntegers ];
}

[download]

Will save a bit more, though not as much as you'd think.

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.
"I'd rather go naked than blow up my ass"

Replies are listed 'Best First'.
Re^2: Need a faster way to find matches
by remzak (Acolyte) on Jan 17, 2010 at 17:44 UTC
    Ok, using BrowserUk's suggestions we improved the speed by 25.5 percent.

    I am not a perl whiz, and do not know how to "remove a level of scope" in the syntax below.

    "use integer" helps, and more so (i think) when I moved it outside of the loop.

    the "grep $_ &1, @LongListOfIntegers" doesn't do anything since I know the values are all odd.

    The last idea provided the most savings. I do need both values as keys in the hash, since I am using this as a lookup in subsequent steps. 

    {
  use integer;
  foreach my $i1 ( 0 .. $#LongListOfIntegers) {
    my $v = $LongListOfIntegers[ $i1 ];
    foreach (@LongListOfIntegers[ $i1+1 .. $#LongListOfIntegers]) {
      if (($v & $_) == 1) {
        $MatchedIntegers{$v}{$_}=();
        $MatchedIntegers{$_}{$v}=();
      }
    }
  }
}

    [download]
    Thanks. Now I am going to investigate kikuchiyo's comments.
[reply]
[d/l]
      One last improvement... by moving the inner loop of the above code into the code where I build the qualified list of integers, I was able to take the problem from N^2/2 to N^2/4.

      At first the list is small, only once the list is done is it N long. By doing the checks as I add numbers I am performing 1/4 the number of comparisons.

[reply]
      Doing without the array slice may improve it:
      {
  use integer;
  for my $i1 (0 .. $#LongListOfIntegers) {
    for my $i2 ($i1+1 .. $#LongListOfIntegers) {
      my $v = $LongListOfIntegers[$i1];
      my $w = $LongListOfIntegers[$i2];

      unless ($v & $w & ~1) {
        $MatchedIntegers{$v}{$w} = 1;
        $MatchedIntegers{$w}{$v} = 1;
      }
    }
  }
}

      [download]
[reply]
[d/l]
        I tried your suggestion; on my (windows) version of perl, using the array slice is (much) faster. Still, thanks for the suggestion.
[reply]

In Section Seekers of Perl Wisdom