Perl Cd Bookshelf [Electronic resources] نسخه متنی

4.13. Finding the First List Element That Passes a Test

4.13.1. Problem

You want the first element in
the list (or its index) that passes a test. Alternatively, you want
to know whether any element passes the test. The test can be simple
identity ("Is this element in the list?")[7] or more complex ("I
have a list of Employee objects, sorted from highest salary to
lowest. Which manager has the highest salary?"). Simple cases
normally require only the value of the element, but when the array
itself will be altered, you probably need to know the index number of
the first matching element.

[7]But why
didn''t you use a hash then?

4.13.2. Solution

To find a
matching value, use foreach to loop over every
element, and call last as soon as you find a
match:

my ($match, $found, $item);
foreach $item (@array) {
if (CRITERION) {
$match = $item;  # must save
$found = 1;
last;
}
}
if ($found) {
## do something with $match
} else {
## unfound
}

To find a matching index, use for to loop a
variable over every array index, and call last as
soon as you find a match:

my ($i, $match_idx);
for ($i = 0; $i < @array; $i++) {
if (CRITERION) {
$match_idx = $i;    # save the index
last;
}
}
if (defined $match_idx) {
## found in $array[$match_idx]
} else {
## unfound
}

The List::Util module, shipped standard with Perl as of v5.8 but
available on CPAN for earlier versions, provides an even easier
approach:

use List::Util qw(first);
$match = first { CRITERION } @list

4.13.3. Discussion

Lacking (until recently) a built-in mechanism to do this, we must
write our own code to go through the list and test each element. We
use foreach and for, and call
last to ensure that we stop as soon as we find a
match. Before we use last to stop looking, though,
we save the value or index.

A common approach is to try to use grep here. But
grep always tests all elements and finds all
matches, so it''s inefficient if you want only the first match.
However, grep might still be faster. That''s
because there will be less source code if you use
grep rather than writing your own loop. That means
fewer internal Perl operations, and it is these that in practice
often dominate runtimes.

Beyond a certain size of your data set, a loop that terminates early
will still be faster—assuming it has the chance to do so.
Empirical evidence suggests that for will be
faster as long as you can exit before the first two-thirds of the
list has been examined. It''s worthwhile to know how to do that.

We have to set $match when we want the value of
the first matching element. We can''t just test
$item at the end of the loop, because
foreach automatically local izes
the iterator variable and thereby prevents us from accessing the
final loop value after the loop ends. See Recipe 4.5.

Here''s an example. Assume that @all_emps holds a
list of Employee objects, sorted in descending order by salary. We
wish to find the highest paid engineer, who will be the first
engineer in the array. We only want to print the engineer''s name, so
we want the value, not the index.

foreach $employee (@all_emps) {
if ( $employee->category( ) eq ''engineer'' ) {
$top_engr = $employee;
last;
}
}
print "Highest paid engineer is: ", $highest_engineer->name( ), "\n";

When we''re searching and want only the index, we can save some code
by remembering that $i will not be an acceptable
array index if we don''t find a match. This mainly saves us code
space, as not doing an assignment doesn''t really win much compared to
the time spent testing list elements. It''s more obscure, because it
tests if ($i < @ARRAY) to check whether we
found a match, instead of the more obvious defined
test in the previous solution.

for ($i = 0; $i < @ARRAY; $i++) {
last if CRITERION;
}
if ($i < @ARRAY) {
## found and $i is the index
} else {
## not found
}

The
first function from List::Util encapsulates the
logic from an entire loop into a convenient, easy-to-use function. It
acts just like a short-circuiting form of the built-in
grep function that stops as soon as a match is
found. While running, each list element is in a localized
$_ variable. For example:

$first_odd = first { $_ % 2 =  = 1 } @ARRAY;

Or rewriting the previous employee loop:

$top_engr = first { $_->category( ) eq ''engineer'' } @all_emps;

4.13.4. See Also

The "For Loops," "Foreach Loops," and "Loop Control" sections of
perlsyn(1) and Chapter 4 of
Programming Perl; the grep
function in perlfunc(1) and Chapter 29 of
Programming Perl