Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does sorting help efficiency of grep in Perl

Tags:

grep

perl

I'm looking for some specifics about how Perl's grep function works. I'm doing this:

if ( grep{ $foo == $_ } @bar ) {
  some code;
}

Suppose @bar is large (hundreds of thousands of elements). With my data, if I sort @bar, values of $foo are more likely to appear near the beginning of the array than near the end. I'm wondering if this will help performance.

Put differently, with the above code, does grep move sequentially through @bar checking whether $foo == $_ and then immediately exit once any value has been found to be true? Or would it actually check every element of @bar before returning a value?

like image 385
itzy Avatar asked Mar 19 '13 18:03

itzy


1 Answers

grep does not short-circuit, so ordering of elements does not matter.

While List::MoreUtils's first does short-circuit, the whole list must be placed on the stack before it's called.

This will be best:

for (@bar) {
   if ($foo == $_) {
      some code;
      last;
   }
}

Updated: I originally iterated over the indexes since that uses O(1) memory, but so does for (@bar) (as opposed to for (LIST) in general) as ysth reminded me.

like image 54
ikegami Avatar answered Oct 22 '22 09:10

ikegami