perlfaq4.pod

来自「视频监控网络部分的协议ddns,的模块的实现代码,请大家大胆指正.」· POD 代码 · 共 2,029 行 · 第 1/5 页

matters.

=head2 How can I remove duplicate elements from a list or array?

(contributed by brian d foy)

Use a hash. When you think the words "unique" or "duplicated", think
"hash keys".

If you don't care about the order of the elements, you could just
create the hash then extract the keys. It's not important how you
create that hash: just that you use C<keys> to get the unique
elements.

	my %hash   = map { $_, 1 } @array;
	# or a hash slice: @hash{ @array } = ();
	# or a foreach: $hash{$_} = 1 foreach ( @array );

	my @unique = keys %hash;

If you want to use a module, try the C<uniq> function from
C<List::MoreUtils>. In list context it returns the unique elements,
preserving their order in the list. In scalar context, it returns the
number of unique elements.

	use List::MoreUtils qw(uniq);

	my @unique = uniq( 1, 2, 3, 4, 4, 5, 6, 5, 7 ); # 1,2,3,4,5,6,7
	my $unique = uniq( 1, 2, 3, 4, 4, 5, 6, 5, 7 ); # 7

You can also go through each element and skip the ones you've seen
before. Use a hash to keep track. The first time the loop sees an
element, that element has no key in C<%Seen>. The C<next> statement
creates the key and immediately uses its value, which is C<undef>, so
the loop continues to the C<push> and increments the value for that
key. The next time the loop sees that same element, its key exists in
the hash I<and> the value for that key is true (since it's not 0 or
C<undef>), so the next skips that iteration and the loop goes to the
next element.

	my @unique = ();
	my %seen   = ();

	foreach my $elem ( @array )
		{
		next if $seen{ $elem }++;
		push @unique, $elem;
		}

You can write this more briefly using a grep, which does the
same thing.

	my %seen = ();
	my @unique = grep { ! $seen{ $_ }++ } @array;

=head2 How can I tell whether a certain element is contained in a list or array?

(portions of this answer contributed by Anno Siegel)

Hearing the word "in" is an I<in>dication 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 C<$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 C<vec($read,$n,1)> is true for some C<$n>.

These methods guarantee fast individual tests but require a re-organization
of the original list or array.  They only pay off if you have to test
multiple values against the same array.

If you are testing only once, the standard module C<List::Util> exports
the function C<first> for this purpose.  It works by stopping once it
finds the element. It's written in C for speed, and its Perl equivalent
looks like this subroutine:

	sub first (&@) {
		my $code = shift;
		foreach (@_) {
			return $_ if &{$code}();
		}
		undef;
	}

If speed is of little concern, the common idiom uses grep in scalar context
(which returns the number of items that passed its condition) to traverse the
entire list. This does have the benefit of telling you how many matches it
found, though.

	my $is_there = grep $_ eq $whatever, @array;

If you want to actually extract the matching elements, simply use grep in
list context.

	my @matches = grep $_ eq $whatever, @array;

=head2 How do I compute the difference of two arrays?  How do I compute the intersection of two arrays?

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 I<symmetric difference>, that is, all elements
in either A or in B but not in both.  Think of it as an xor operation.

=head2 How do I test whether two arrays or hashes are equal?

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 C<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.

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

To find the first array element which satisfies a condition, you can
use the C<first()> function in the C<List::Util> module, which comes
with Perl 5.8. This example finds the first element that contains
"Perl".

	use List::Util qw(first);

	my $element = first { /Perl/ } @array;

If you cannot use C<List::Util>, you can make your own loop to do the
same thing.  Once you find the element, you stop the loop with last.

	my $found;
	foreach ( @array ) {
		if( /Perl/ ) { $found = $_; last }
		}

If you want the array index, you can iterate through the indices
and check the array element at each index until you find one
that satisfies the condition.

	my( $found, $index ) = ( undef, -1 );
	for( $i = 0; $i < @array; $i++ ) {
		if( $array[$i] =~ /Perl/ ) {
			$found = $array[$i];
			$index = $i;
			last;
			}
		}

=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 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

You can also use C<Tie::Cycle>:

	use Tie::Cycle;

	tie my $cycle, 'Tie::Cycle', [ qw( FFFFFF 000000 FFFF00 ) ];

	print $cycle; # FFFFFF
	print $cycle; # 000000
	print $cycle; # FFFF00

=head2 How do I shuffle an array randomly?

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 C<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.

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

Use C<for>/C<foreach>:

	for (@lines) {
		s/foo/bar/;	# change that word
		tr/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
		}

which can also be done with C<map()> which is made to transform
one list into another:

	@volumes = map {$_ ** 3 * (4/3) * 3.14159} @radii;

If you want to do the same thing to modify the values of the
hash, you can use the C<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 C<values> returned copies of the values,
so older perl code often contains constructions such as
C<@orbits{keys %orbits}> instead of C<values %orbits> where
the hash is to be modified.

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

Use the C<rand()> function (see L<perlfunc/rand>):

	$index   = rand @array;
	$element = $array[$index];

Or, simply:

	my $element = $array[ rand @array ];

=head2 How do I permute N elements of a list?
X<List::Permuter> X<permute> X<Algorithm::Loops> X<Knuth>
X<The Art of Computer Programming> X<Fischer-Krause>

Use the C<List::Permutor> module on CPAN. If the list is actually an
array, try the C<Algorithm::Permute> module (also on CPAN). It's
written in XS code and is very efficient:

	use Algorithm::Permute;

	my @array = 'a'..'d';
	my $p_iterator = Algorithm::Permute->new ( \@array );

	while (my @perm = $p_iterator->next) {
	   print "next permutation: (@perm)\n";
		}

For even faster execution, you could do:

	use Algorithm::Permute;

	my @array = 'a'..'d';

	Algorithm::Permute::permute {
		print "next permutation: (@array)\n";
		} @array;