|
 So
What's the Difference?
Randal L. Schwartz
A lot of common programming is dealing with things that change. Things do
indeed change, and sometimes we'd like to know how they changed.
For example, if we have a list of items:
@one = qw(a b c d e f g);
then later, we look at it again, and there's a different set of items:
@two = qw(b c e h i j);
How can we tell what's new, what's old, and what's gone? We could certainly
try to do it by brute force:
@one = qw(a b c d e f g);
@two = qw(b c e h i j);
foreach $one (@one) {
if (grep $one eq $_, @two) {
print "$one is in both old and new\n";
} else {
print "$one has been deleted\n";
}
}
foreach $two (@two) {
unless (grep $two eq $_, @one) {
print "$two has been added\n";
}
}
This in fact gives us an appropriate response:
a has been deleted
b is in both old and new
c is in both old and new
d has been deleted
e is in both old and new
f has been deleted
g has been deleted
h has been added
i has been added
j has been added
But this is incredibly inefficient. The computation time will rise in proportion
to the product of sizes of both the lists. This happens because every element
of one list is being compared to every element of the other list (twice, in fact).
The grep operator is a loop over each item, so we effectively have
nested loops, which should usually be a danger sign.
The perlfaq4 manpage approaches this subject, giving a solution of
something like:
@union = @intersection = @difference = ();
%count = ();
foreach $element (@one, @two) { $count{$element}++ }
foreach $element (keys %count) {
push @union, $element;
push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element;
}
with the caveat that we're assuming one item of each kind within each list.
|
