Data: Arrays
An array has a changeable length. A list does not. An array is something you can push or pop,
while a list is a set of values. Some people make the distinction that a list is a value while
an array is a variable. Subroutines are passed and return lists, you put things into list
context, you initialize arrays with lists, and you foreach() across a list. @
variables are arrays, anonymous arrays are arrays, arrays in scalar context behave like the
number of elements in them, subroutines access their arguments through the array @_,
and push/pop/shift only work on arrays.
As a side note, there's no such thing as a list in scalar context. When you say
you're using the comma operator in scalar context, so it uses the scalar comma operator.
There never was a list there at all! This causes the last value to be returned: 9.
The former is a scalar value; the latter an array slice, making it a list with one (scalar)
value. You should use $ when you want a scalar value (most of the time) and @ when you want a
list with one scalar value in it (very, very rarely; nearly never, in fact).
Sometimes it doesn't make a difference, but sometimes it does. For example, compare:
$good[0] = `some program that outputs several lines`;
|
|
with
@bad[0] = `same program that outputs several lines`;
|
|
The use warnings pragma and the -w flag will warn you about these
matters.
There are several possible ways, depending on whether the array is ordered and whether you
wish to preserve the ordering.
- a)
-
If @in is sorted, and you want @out to be sorted: (this assumes all true values in the
array)
$prev = "not equal to $in[0]";
@out = grep($_ ne $prev && ($prev = $_, 1), @in);
|
|
This is nice in that it doesn't use much extra memory, simulating uniq(1)'s behavior of
removing only adjacent duplicates. The ", 1" guarantees that the expression is
true (so that grep picks it up) even if the $_ is 0, "", or undef.
- b)
-
If you don't know whether @in is sorted:
undef %saw;
@out = grep(!$saw{$_}++, @in);
|
|
- c)
-
Like (b), but @in contains only small integers:
@out = grep(!$saw[$_]++, @in);
|
|
- d)
-
A way to do (b) without any loops or greps:
undef %saw;
@saw{@in} = ();
@out = sort keys %saw; # remove sort if undesired
|
|
- e)
-
Like (d), but @in contains only small positive integers:
undef @ary;
@ary[@in] = @in;
@out = grep {defined} @ary;
|
|
But perhaps you should have been using a hash all along, eh?
Hearing the word "in" is an indication that you probably should have used a
hash, not a list or array, to store your data. Hashes are designed to answer this question
quickly and efficiently. Arrays aren't.
That being said, there are several ways to approach this. If you are going to make this query
many times over arbitrary string values, the fastest way is probably to invert the original
array and maintain a hash whose keys are the first array's values.
@blues = qw/azure cerulean teal turquoise lapis-lazuli/;
%is_blue = ();
for (@blues) { $is_blue{$_} = 1 }
|
|
Now you can check whether $is_blue{$some_color}. It might have been a good idea to keep the
blues all in a hash in the first place.
If the values are all small integers, you could use a simple indexed array. This kind of an
array will take up less space:
@primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31);
@is_tiny_prime = ();
for (@primes) { $is_tiny_prime[$_] = 1 }
# or simply @istiny_prime[@primes] = (1) x @primes;
|
|
Now you check whether $is_tiny_prime[$some_number].
If the values in question are integers instead of strings, you can save quite a lot of space
by using bit strings instead:
@articles = ( 1..10, 150..2000, 2017 );
undef $read;
for (@articles) { vec($read,$_,1) = 1 }
|
|
Now check whether vec($read,$n,1) is true for some $n.
Please do not use
($is_there) = grep $_ eq $whatever, @array;
|
|
or worse yet
($is_there) = grep /$whatever/, @array;
|
|
These are slow (checks every element even if the first matches), inefficient (same reason),
and potentially buggy (what if there are regex characters in $whatever?). If you're only testing
once, then use:
$is_there = 0;
foreach $elt (@array) {
if ($elt eq $elt_to_find) {
$is_there = 1;
last;
}
}
if ($is_there) { ... }
|
|
Use a hash. Here's code to do both and more. It assumes that each element is unique in a
given array:
@union = @intersection = @difference = ();
%count = ();
foreach $element (@array1, @array2) { $count{$element}++ }
foreach $element (keys %count) {
push @union, $element;
push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element;
}
|
|
Note that this is the symmetric difference, that is, all elements in either A or in B
but not in both. Think of it as an xor operation.
The following code works for single-level arrays. It uses a stringwise comparison, and does
not distinguish defined versus undefined empty strings. Modify if you have other needs.
$are_equal = compare_arrays(\@frogs, \@toads);
sub compare_arrays {
my ($first, $second) = @_;
no warnings; # silence spurious -w undef complaints
return 0 unless @$first == @$second;
for (my $i = 0; $i < @$first; $i++) {
return 0 if $first->[$i] ne $second->[$i];
}
return 1;
}
|
|
For multilevel structures, you may wish to use an approach more like this one. It uses the
CPAN module FreezeThaw:
use FreezeThaw qw(cmpStr);
@a = @b = ( "this", "that", [ "more", "stuff" ] );
printf "a and b contain %s arrays\n",
cmpStr(\@a, \@b) == 0
? "the same"
: "different";
|
|
This approach also works for comparing hashes. Here we'll demonstrate two different answers:
use FreezeThaw qw(cmpStr cmpStrHard);
%a = %b = ( "this" => "that", "extra" => [ "more", "stuff" ] );
$a{EXTRA} = \%b;
$b{EXTRA} = \%a;
printf "a and b contain %s hashes\n",
cmpStr(\%a, \%b) == 0 ? "the same" : "different";
printf "a and b contain %s hashes\n",
cmpStrHard(\%a, \%b) == 0 ? "the same" : "different";
|
|
The first reports that both those the hashes contain the same data, while the second reports
that they do not. Which you prefer is left as an exercise to the reader.
You can use this if you care about the index:
for ($i= 0; $i < @array; $i++) {
if ($array[$i] eq "Waldo") {
$found_index = $i;
last;
}
}
|
|
Now $found_index has what you want.
In general, you usually don't need a linked list in Perl, since with regular arrays, you can
push and pop or shift and unshift at either end, or you can use splice to add and/or remove
arbitrary number of elements at arbitrary points. Both pop and shift are both O(1) operations on
Perl's dynamic arrays. In the absence of shifts and pops, push in general needs to reallocate on
the order every log(N) times, and unshift will need to copy pointers each time.
If you really, really wanted, you could use structures as described in perldsc or perltoot and do just what the
algorithm book tells you to do. For example, imagine a list node like this:
$node = {
VALUE => 42,
LINK => undef,
};
|
|
You could walk the list this way:
print "List: ";
for ($node = $head; $node; $node = $node->{LINK}) {
print $node->{VALUE}, " ";
}
print "\n";
|
|
You could add to the list this way:
my ($head, $tail);
$tail = append($head, 1); # grow a new head
for $value ( 2 .. 10 ) {
$tail = append($tail, $value);
}
sub append {
my($list, $value) = @_;
my $node = { VALUE => $value };
if ($list) {
$node->{LINK} = $list->{LINK};
$list->{LINK} = $node;
} else {
$_[0] = $node; # replace caller's version
}
return $node;
}
|
|
But again, Perl's built-in are virtually always good enough.
Circular lists could be handled in the traditional fashion with linked lists, or you could
just do something like this with an array:
unshift(@array, pop(@array)); # the last shall be first
push(@array, shift(@array)); # and vice versa
|
|
If you either have Perl 5.8.0 or later installed, or if you have Scalar-List-Utils 1.03 or
later installed, you can say:
use List::Util 'shuffle';
@shuffled = shuffle(@list);
|
|
If not, you can use a Fisher-Yates shuffle.
sub fisher_yates_shuffle {
my $deck = shift; # $deck is a reference to an array
my $i = @$deck;
while ($i--) {
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
}
}
# shuffle my mpeg collection
#
my @mpeg = <audio/*/*.mp3>;
fisher_yates_shuffle( \@mpeg ); # randomize @mpeg in place
print @mpeg;
|
|
Note that the above implementation shuffles an array in place, unlike the List::Util::shuffle()
which takes a list and returns a new shuffled list.
You've probably seen shuffling algorithms that work using splice, randomly picking another
element to swap the current element with
srand;
@new = ();
@old = 1 .. 10; # just a demo
while (@old) {
push(@new, splice(@old, rand @old, 1));
}
|
|
This is bad because splice is already O(N), and since you do it N times, you just invented a
quadratic algorithm; that is, O(N**2). This does not scale, although Perl is so efficient that
you probably won't notice this until you have rather largish arrays.
Use for/foreach:
for (@lines) {
s/foo/bar/; # change that word
y/XZ/ZX/; # swap those letters
}
|
|
Here's another; let's compute spherical volumes:
for (@volumes = @radii) { # @volumes has changed parts
$_ **= 3;
$_ *= (4/3) * 3.14159; # this will be constant folded
}
|
|
If you want to do the same thing to modify the values of the hash, you can use the values
function. As of Perl 5.6 the values are not copied, so if you modify $orbit (in this case), you
modify the value.
for $orbit ( values %orbits ) {
($orbit **= 3) *= (4/3) * 3.14159;
}
|
|
Prior to perl 5.6 values returned copies of the values, so older perl code often
contains constructions such as @orbits{keys %orbits} instead of values
%orbits where the hash is to be modified.
Use the rand() function (see perlfunc/rand):
# at the top of the program:
srand; # not needed for 5.004 and later
# then later on
$index = rand @array;
$element = $array[$index];
|
|
Make sure you only call srand once per program, if then. If you are calling it more
than once (such as before each call to rand), you're almost certainly doing something wrong.
Here's a little program that generates all permutations of all the words on each line of
input. The algorithm embodied in the permute() function should work on any list:
#!/usr/bin/perl -n
# tsc-permute: permute each word of input
permute([split], []);
sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] };
unless (@items) {
print "@perms\n";
} else {
my(@newitems,@newperms,$i);
foreach $i (0 .. $#items) {
@newitems = @items;
@newperms = @perms;
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}
|
|
Unfortunately, this algorithm is very inefficient. The Algorithm::Permute module from CPAN
runs at least an order of magnitude faster. If you don't have a C compiler (or a binary
distribution of Algorithm::Permute), then you can use List::Permutor which is written in pure
Perl, and is still several times faster than the algorithm above.
Supply a comparison function to sort() (described in perlfunc/sort):
@list = sort { $a <=> $b } @list;
|
|
The default sort function is cmp, string comparison, which would sort (1, 2, 10)
into (1, 10, 2). <=>, used above, is the numerical comparison
operator.
If you have a complicated function needed to pull out the part you want to sort on, then
don't do it inside the sort function. Pull it out first, because the sort BLOCK can be called
many times for the same element. Here's an example of how to pull out the first word after the
first number on each item, and then sort those words case-insensitively.
@idx = ();
for (@data) {
($item) = /\d+\s*(\S+)/;
push @idx, uc($item);
}
@sorted = @data[ sort { $idx[$a] cmp $idx[$b] } 0 .. $#idx ];
|
|
which could also be written this way, using a trick that's come to be known as the
Schwartzian Transform:
@sorted = map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [ $_, uc( (/\d+\s*(\S+)/)[0]) ] } @data;
|
|
If you need to sort on several fields, the following paradigm is useful.
@sorted = sort { field1($a) <=> field1($b) ||
field2($a) cmp field2($b) ||
field3($a) cmp field3($b)
} @data;
|
|
This can be conveniently combined with precalculation of keys as given above.
See the sort artitcle article in the "Far More Than You Ever Wanted To Know"
collection in http://www.cpan.org/olddoc/FMTEYEWTK.tgz for more about this approach.
See also the question below on sorting hashes.
Use pack() and unpack(), or else vec() and the bitwise operations.
For example, this sets $vec to have bit N set if $ints[N] was set:
$vec = '';
foreach(@ints) { vec($vec,$_,1) = 1 }
|
|
Here's how, given a vector in $vec, you can get those bits into your @ints array:
sub bitvec_to_list {
my $vec = shift;
my @ints;
# Find null-byte density then select best algorithm
if ($vec =~ tr/\0// / length $vec > 0.95) {
use integer;
my $i;
# This method is faster with mostly null-bytes
while($vec =~ /[^\0]/g ) {
$i = -9 + 8 * pos $vec;
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
push @ints, $i if vec($vec, ++$i, 1);
}
} else {
# This method is a fast general algorithm
use integer;
my $bits = unpack "b*", $vec;
push @ints, 0 if $bits =~ s/^(\d)// && $1;
push @ints, pos $bits while($bits =~ /1/g);
}
return \@ints;
}
|
|
This method gets faster the more sparse the bit vector is. (Courtesy of Tim Bunce and
Winfried Koenig.)
You can make the while loop a lot shorter with this suggestion from Benjamin Goldberg:
while($vec =~ /[^\0]+/g ) {
push @ints, grep vec($vec, $_, 1), $-[0] * 8 .. $+[0] * 8;
}
|
|
Or use the CPAN module Bit::Vector:
$vector = Bit::Vector->new($num_of_bits);
$vector->Index_List_Store(@ints);
@ints = $vector->Index_List_Read();
|
|
Bit::Vector provides efficient methods for bit vector, sets of small integers and "big
int" math.
Here's a more extensive illustration using vec():
# vec demo
$vector = "\xff\x0f\xef\xfe";
print "Ilya's string \\xff\\x0f\\xef\\xfe represents the number ",
unpack("N", $vector), "\n";
$is_set = vec($vector, 23, 1);
print "Its 23rd bit is ", $is_set ? "set" : "clear", ".\n";
pvec($vector);
set_vec(1,1,1);
set_vec(3,1,1);
set_vec(23,1,1);
set_vec(3,1,3);
set_vec(3,2,3);
set_vec(3,4,3);
set_vec(3,4,7);
set_vec(3,8,3);
set_vec(3,8,7);
set_vec(0,32,17);
set_vec(1,32,17);
sub set_vec {
my ($offset, $width, $value) = @_;
my $vector = '';
vec($vector, $offset, $width) = $value;
print "offset=$offset width=$width value=$value\n";
pvec($vector);
}
sub pvec {
my $vector = shift;
my $bits = unpack("b*", $vector);
my $i = 0;
my $BASE = 8;
print "vector length in bytes: ", length($vector), "\n";
@bytes = unpack("A8" x length($vector), $bits);
print "bits are: @bytes\n\n";
}
|
|
The short story is that you should probably only use defined on scalars or functions, not on
aggregates (arrays and hashes). See perlfunc/defined in the 5.004
release or later of Perl for more detail.
|
|
