Re^2: Need a faster way to find matches

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.

Comment on Re^2: Need a faster way to find matches Download Code

Replies are listed 'Best First'.
Re^3: Need a faster way to find matches by remzak (Acolyte) on Jan 17, 2010 at 19:29 UTC
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]
Re^3: Need a faster way to find matches by repellent (Priest) on Jan 18, 2010 at 04:12 UTC
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]
Re^4: Need a faster way to find matches by remzak (Acolyte) on Jan 18, 2010 at 21:18 UTC
I tried your suggestion; on my (windows) version of perl, using the array slice is (much) faster. Still, thanks for the suggestion.	[reply]


Think about Loose Coupling
	PerlMonks