perlfaq4.html

《Perl 5教程》及《perl常问问题集》

<P>

<DL>
<DT><STRONG><A NAME="item_a">a) If @in is sorted, and you want @out to be sorted:

</A></STRONG><DD>
<PRE>    $prev = 'nonesuch';
    @out = grep($_ ne $prev &amp;&amp; ($prev = $_), @in);
</PRE>

<P>

This is nice in that it doesn't use much extra memory, simulating
<CODE>uniq(1)'s</CODE> behavior of removing only adjacent duplicates.


<P>

<DT><STRONG><A NAME="item_b">b) If you don't know whether @in is sorted:

</A></STRONG><DD>
<PRE>    undef %saw;
    @out = grep(!$saw{$_}++, @in);
</PRE>

<P>

<DT><STRONG><A NAME="item_c">c) Like (b), but @in contains only small integers:

</A></STRONG><DD>
<PRE>    @out = grep(!$saw[$_]++, @in);
</PRE>

<P>

<DT><STRONG><A NAME="item_d">d) A way to do (b) without any loops or greps:

</A></STRONG><DD>
<PRE>    undef %saw;
    @saw{@in} = ();
    @out = sort keys %saw;  # remove sort if undesired
</PRE>

<P>

<DT><STRONG><A NAME="item_e">e) Like (d), but @in contains only small positive integers:

</A></STRONG><DD>
<PRE>    undef @ary;
    @ary[@in] = @in;
    @out = @ary;
</PRE>

<P>

</DL>
<P>
<HR>
<H3><A NAME="How_can_I_tell_whether_an_array_">How can I tell whether an array contains a certain element?

</A></H3>
There are several ways to approach this. If you are going to make this
query many times and the values are arbitrary strings, the fastest way is
probably to invert the original array and keep an associative array lying
about whose keys are the first array's values.


<P>

<PRE>    @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
    undef %is_blue;
    for (@blues) { $is_blue{$_} = 1 }
</PRE>

<P>

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.


<P>

If the values are all small integers, you could use a simple indexed array.
This kind of an array will take up less space:


<P>

<PRE>    @primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31);
    undef @is_tiny_prime;
    for (@primes) { $is_tiny_prime[$_] = 1; }
</PRE>

<P>

Now you check whether $is_tiny_prime[$some_number].


<P>

If the values in question are integers instead of strings, you can save
quite a lot of space by using bit strings instead:


<P>

<PRE>    @articles = ( 1..10, 150..2000, 2017 );
    undef $read;
    grep (vec($read,$_,1) = 1, @articles);
</PRE>

<P>

Now check whether <CODE>vec($read,$n,1)</CODE> is true for some <CODE>$n</CODE>.


<P>

Please do not use


<P>

<PRE>    $is_there = grep $_ eq $whatever, @array;
</PRE>

<P>

or worse yet


<P>

<PRE>    $is_there = grep /$whatever/, @array;
</PRE>

<P>

These are slow (checks every element even if the first matches),
inefficient (same reason), and potentially buggy (what if there are regexp
characters in $whatever?).


<P>

<P>
<HR>
<H3><A NAME="How_do_I_compute_the_difference_">How do I compute the difference of two arrays?  How do I compute the intersection of two arrays?

</A></H3>
Use a hash. Here's code to do both and more. It assumes that each element
is unique in a given array:


<P>

<PRE>    @union = @intersection = @difference = ();
    %count = ();
    foreach $element (@array1, @array2) { $count{$element}++ }
    foreach $element (keys %count) {
        push @union, $element;
        push @{ $count{$element} &gt; 1 ? \@intersection : \@difference }, $element;
    }
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_find_the_first_array_el">How do I find the first array element for which a condition is true?

</A></H3>
You can use this if you care about the index:


<P>

<PRE>    for ($i=0; $i &lt; @array; $i++) {
        if ($array[$i] eq &quot;Waldo&quot;) {
            $found_index = $i;
            last;
        }
    }
</PRE>

<P>

Now <CODE>$found_index</CODE> has what you want.


<P>

<P>
<HR>
<H3><A NAME="How_do_I_handle_linked_lists_">How do I handle linked lists?

</A></H3>
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.


<P>

If you really, really wanted, you could use structures as described in
<A HREF="../../tppmsgs/msgs0.htm#64" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perldsc.html">the perldsc manpage</A> or <A HREF="../../tppmsgs/msgs0.htm#57" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perltoot.html">the perltoot manpage</A> and do just what the algorithm book tells you to do.


<P>

<P>
<HR>
<H3><A NAME="How_do_I_handle_circular_lists_">How do I handle circular lists?

</A></H3>
Circular lists could be handled in the traditional fashion with linked
lists, or you could just do something like this with an array:


<P>

<PRE>    unshift(@array, pop(@array));  # the last shall be first
    push(@array, shift(@array));   # and vice versa
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_shuffle_an_array_random">How do I shuffle an array randomly?

</A></H3>
Here's a shuffling algorithm which works its way through the list, randomly
picking another element to swap the current element with:


<P>

<PRE>    srand;
    @new = ();
    @old = 1 .. 10;  # just a demo
    while (@old) {
        push(@new, splice(@old, rand @old, 1));
    }
</PRE>

<P>

For large arrays, this avoids a lot of the reshuffling:


<P>

<PRE>    srand;
    @new = ();
    @old = 1 .. 10000;  # just a demo
    for( @old ){
        my $r = rand @new+1;
        push(@new,$new[$r]);
        $new[$r] = $_;
    }
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_process_modify_each_ele">How do I process/modify each element of an array?

</A></H3>
Use <CODE>for</CODE>/<CODE>foreach</CODE>:


<P>

<PRE>    for (@lines) {
        s/foo/bar/;
        tr[a-z][A-Z];
    }
</PRE>

<P>

Here's another; let's compute spherical volumes:


<P>

<PRE>    for (@radii) {
        $_ **= 3;
        $_ *= (4/3) * 3.14159;  # this will be constant folded
    }
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_select_a_random_element">How do I select a random element from an array?

</A></H3>
Use the <CODE>rand()</CODE> function (see <A HREF="../../tppmsgs/msgs0.htm#68" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perlfunc.html#rand">rand</A>):


<P>

<PRE>    srand;                      # not needed for 5.004 and later
    $index   = rand @array;
    $element = $array[$index];
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_permute_N_elements_of_a">How do I permute N elements of a list?

</A></H3>
Here's a little program that generates all permutations of all the words on
each line of input. The algorithm embodied in the <CODE>permut()</CODE>
function should work on any list:


<P>

<PRE>    #!/usr/bin/perl -n
    # permute - [e-mail]
    permut([split], []);
    sub permut {
        my @head = @{ $_[0] };
        my @tail = @{ $_[1] };
        unless (@head) {
            # stop recursing when there are no elements in the head
            print &quot;@tail\n&quot;;
        } else {
            # for all elements in @head, move one from @head to @tail
            # and call permut() on the new @head and @tail
            my(@newhead,@newtail,$i);
            foreach $i (0 .. $#head) {
                @newhead = @head;
                @newtail = @tail;
                unshift(@newtail, splice(@newhead, $i, 1));
                permut([@newhead], [@newtail]);
            }
        }
    }
</PRE>

<P>

<P>
<HR>
<H3><A NAME="How_do_I_sort_an_array_by_anyth">How do I sort an array by (anything)?

</A></H3>
Supply a comparison function to <CODE>sort()</CODE> (described in <A HREF="../../tppmsgs/msgs0.htm#68" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perlfunc.html#sort">sort</A>):


<P>

<PRE>    @list = sort { $a &lt;=&gt; $b } @list;
</PRE>

<P>

The default sort function is cmp, string comparison, which would sort <CODE>(1, 2, 10)</CODE> into <CODE>(1, 10, 2)</CODE>.  <CODE>&lt;=&gt;</CODE>, used above, is the numerical comparison operator.


<P>

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 
<FONT SIZE=-1>BLOCK</FONT> 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.



<P>

<PRE>    @idx = ();
    for (@data) {
        ($item) = /\d+\s*(\S+)/;
        push @idx, uc($item);
    }
    @sorted = @data[ sort { $idx[$a] cmp $idx[$b] } 0 .. $#idx ];
</PRE>

<P>

Which could also be written this way, using a trick that's come to be known
as the Schwartzian Transform:


<P>

<PRE>    @sorted = map  { $_-&gt;[0] }
              sort { $a-&gt;[1] cmp $b-&gt;[1] }
              map  { [ $_, uc((/\d+\s*(\S+)/ )[0] ] } @data;
</PRE>

<P>

If you need to sort on several fields, the following paradigm is useful.


<P>

<PRE>    @sorted = sort { field1($a) &lt;=&gt; field1($b) ||
                     field2($a) cmp field2($b) ||
                     field3($a) cmp field3($b)
                   }     @data;
</PRE>

<P>

This can be conveniently combined with precalculation of keys as given
above.


<P>

See <A
HREF="../../tppmsgs/msgs1.htm#136" tppabs="http://www.perl.com/CPAN/doc/FMTEYEWTK/sort.html">http://www.perl.com/CPAN/doc/FMTEYEWTK/sort.html</A>
for more about this approach.


<P>

See also the question below on sorting hashes.


<P>

<P>
<HR>
<H3><A NAME="How_do_I_manipulate_arrays_of_bi">How do I manipulate arrays of bits?

</A></H3>
Use <CODE>pack()</CODE> and <CODE>unpack(),</CODE> or else
<CODE>vec()</CODE> and the bitwise operations.


<P>

For example, this sets <CODE>$vec</CODE> to have bit 
<FONT SIZE=-1>N</FONT> set if $ints[N] was set:


<P>

<PRE>    $vec = '';
    foreach(@ints) { vec($vec,$_,1) = 1 }
</PRE>

<P>

And here's how, given a vector in $vec, you can get those bits into your
<CODE>@ints</CODE> array:


<P>

<PRE>    sub bitvec_to_list {
        my $vec = shift;
        my @ints;
        # Find null-byte density then select best algorithm
        if ($vec =~ tr/\0// / length $vec &gt; 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 &quot;b*&quot;, $vec;
            push @ints, 0 if $bits =~ s/^(\d)// &amp;&amp; $1;
            push @ints, pos $bits while($bits =~ /1/g);
        }
        return \@ints;
    }
</PRE>

<P>

This method gets faster the more sparse the bit vector is. (Courtesy of Tim
Bunce and Winfried Koenig.)


<P>

<P>
<HR>
<H3><A NAME="Why_does_defined_return_true_o">Why does defined() return true on empty arrays and hashes?

</A></H3>
See <A HREF="../../tppmsgs/msgs0.htm#68" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perlfunc.html#defined">defined</A> in the 5.004 release or later of Perl.


<P>

<P>
<HR>
<H2><A NAME="Data_Hashes_Associative_Arrays">Data: Hashes (Associative Arrays)

</A></H2>
<P>
<HR>
<H3><A NAME="How_do_I_process_an_entire_hash_">How do I process an entire hash?

</A></H3>
Use the <CODE>each()</CODE> function (see <A HREF="../../tppmsgs/msgs0.htm#68" tppabs="http://www.perl.org/CPAN/doc/manual/html/pod/perlfunc.html#each">each</A>) if you don't care whether it's sorted:


<P>

<PRE>    while (($key,$value) = each %hash) {
        print &quot;$key = $value\n&quot;;
    }
</PRE>

<P>

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


<P>

<P>
<HR>
<H3><A NAME="What_happens_if_I_add_or_remove_">What happens if I add or remove keys from a hash while iterating over it?

</A></H3>
Don't do that.


<P>

<P>