perlfaq4.pod

MSYS在windows下模拟了一个类unix的终端

    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.

=head2 How do I find the first array element for which a condition is true?

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 C<$found_index> has what you want.

=head2 How do I handle linked lists?

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
L<perldsc> or L<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.

=head2 How do I handle circular lists?

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

=head2 How do I shuffle an array randomly?

Use this:

    # fisher_yates_shuffle( \@array ) : 
    # generate a random permutation of @array in place
    sub fisher_yates_shuffle {
        my $array = shift;
        my $i;
        for ($i = @$array; --$i; ) {
            my $j = int rand ($i+1);
            @$array[$i,$j] = @$array[$j,$i];
        }
    }

    fisher_yates_shuffle( \@array );    # permutes @array in place

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.

=head2 How do I process/modify each element of an array?

Use C<for>/C<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 may not use the C<values> function, oddly enough.  You need a slice:

    for $orbit ( @orbits{keys %orbits} ) {
	($orbit **= 3) *= (4/3) * 3.14159; 
    }

=head2 How do I select a random element from an array?

Use the rand() function (see L<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 I<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.

=head2 How do I permute N elements of a list?

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]);
	    }
	}
    }

=head2 How do I sort an array by (anything)?

Supply a comparison function to sort() (described in L<perlfunc/sort>):

    @list = sort { $a <=> $b } @list;

The default sort function is cmp, string comparison, which would
sort C<(1, 2, 10)> into C<(1, 10, 2)>.  C<< <=> >>, 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 http://www.perl.com/CPAN/doc/FMTEYEWTK/sort.html for more about
this approach.

See also the question below on sorting hashes.

=head2 How do I manipulate arrays of bits?

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 }

And 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.)

Here's a demo on how to use 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";
    } 

=head2 Why does defined() return true on empty arrays and hashes?

The short story is that you should probably only use defined on scalars or
functions, not on aggregates (arrays and hashes).  See L<perlfunc/defined>
in the 5.004 release or later of Perl for more detail.

=head1 Data: Hashes (Associative Arrays)

=head2 How do I process an entire hash?

Use the each() function (see L<perlfunc/each>) if you don't care
whether it's sorted:

    while ( ($key, $value) = each %hash) {
	print "$key = $value\n";
    }

If you want it sorted, you'll have to use foreach() on the result of
sorting the keys as shown in an earlier question.

=head2 What happens if I add or remove keys from a hash while iterating over it?

Don't do that. :-)

[lwall] In Perl 4, you were not allowed to modify a hash at all while
iterating over it.  In Perl 5 you can delete from it, but you still
can't add to it, because that might cause a doubling of the hash table,
in which half the entries get copied up to the new top half of the
table, at which point you've totally bamboozled the iterator code.
Even if the table doesn't double, there's no telling whether your new
entry will be inserted before or after the current iterator position.

Either treasure up your changes and make them after the iterator finishes
or use keys to fetch all the old keys at once, and iterate over the list
of keys.

=head2 How do I look up a hash element by value?

Create a reverse hash:

    %by_value = reverse %by_key;
    $key = $by_value{$value};