Change 17685 by [EMAIL PROTECTED] on 2002/08/05 22:42:09
Subject: Re: mention of "use sort" botched in perlfunc? + PATCH
From: "John P. Linderman" <[EMAIL PROTECTED]>
Date: Sun, 21 Jul 2002 12:13:32 -0400 (17:13 BST)
Message-id: <[EMAIL PROTECTED]>
Affected files ...
.... //depot/perl/lib/sort.pm#9 edit
.... //depot/perl/lib/sort.t#8 edit
Differences ...
==== //depot/perl/lib/sort.pm#9 (text) ====
Index: perl/lib/sort.pm
--- perl/lib/sort.pm#8~16286~ Tue Apr 30 12:03:34 2002
+++ perl/lib/sort.pm Mon Aug 5 15:42:09 2002
@@ -1,6 +1,6 @@
package sort;
-our $VERSION = '1.01';
+our $VERSION = '1.02';
# Currently the hints for pp_sort are stored in the global variable
# $sort::hints. An improvement would be to store them in $^H{SORT} and have
@@ -33,6 +33,30 @@
$hints |= $sort::mergesort_bit;
} elsif ($_ eq 'stable') {
$hints |= $sort::stable_bit;
+ } elsif ($_ eq 'defaults') {
+ $hints = 0;
+ } else {
+ require Carp;
+ Carp::croak("sort: unknown subpragma '$_'");
+ }
+ }
+}
+
+sub unimport {
+ shift;
+ if (@_ == 0) {
+ require Carp;
+ Carp::croak("sort pragma requires arguments");
+ }
+ local $_;
+ no warnings 'uninitialized'; # bitops would warn
+ while ($_ = shift(@_)) {
+ if (/^_q(?:uick)?sort$/) {
+ $hints &= ~$sort::sort_bits;
+ } elsif ($_ eq '_mergesort') {
+ $hints &= ~$sort::sort_bits;
+ } elsif ($_ eq 'stable') {
+ $hints &= ~$sort::stable_bit;
} else {
require Carp;
Carp::croak("sort: unknown subpragma '$_'");
@@ -63,6 +87,8 @@
use sort 'stable'; # guarantee stability
use sort '_quicksort'; # use a quicksort algorithm
use sort '_mergesort'; # use a mergesort algorithm
+ use sort 'defaults'; # revert to default behavior
+ no sort 'stable'; # stability not important
use sort '_qsort'; # alias for quicksort
@@ -70,11 +96,11 @@
=head1 DESCRIPTION
-With the sort pragma you can control the behaviour of the builtin
-sort() function.
+With the C<sort> pragma you can control the behaviour of the builtin
+C<sort()> function.
In Perl versions 5.6 and earlier the quicksort algorithm was used to
-implement sort(), but in Perl 5.8 a mergesort algorithm was also made
+implement C<sort()>, but in Perl 5.8 a mergesort algorithm was also made
available, mainly to guarantee worst case O(N log N) behaviour:
the worst case of quicksort is O(N**2). In Perl 5.8 and later,
quicksort defends against quadratic behaviour by shuffling large
@@ -98,16 +124,78 @@
does fewer comparisons than quicksort, so it may be better when
complicated comparison routines are used. Mergesort also takes
advantage of pre-existing order, so it would be favored for using
-sort to merge several sorted arrays. On the other hand, quicksort
-is often faster for small arrays, and on platforms with small memory
-caches that are much faster than main memory. You can force the
+C<sort()> to merge several sorted arrays. On the other hand, quicksort
+is often faster for small arrays, and on arrays of a few distinct
+values, repeated many times. You can force the
choice of algorithm with this pragma, but this feels heavy-handed,
so the subpragmas beginning with a C<_> may not persist beyond Perl 5.8.
+The default algorithm is mergesort, which will be stable even if
+you do not explicitly demand it.
+But the stability of the default sort is a side-effect that could
+change in later versions. If stability is important, be sure to
+say so with a
+
+ use sort 'stable';
+
+The C<no sort> pragma doesn't
+I<forbid> what follows, it just leaves the choice open. Thus, after
+
+ no sort qw(_mergesort stable);
+
+a mergesort, which happens to be stable, will be employed anyway.
+Note that
+
+ no sort "_quicksort";
+ no sort "_mergesort";
+
+have exactly the same effect, leaving the choice of sort algorithm open.
=head1 CAVEATS
-This pragma is not lexically scoped : its effect is global to the program
-it appears in. This may change in future versions.
+This pragma is not lexically scoped: its effect is global to the program
+it appears in. That means the following will probably not do what you
+expect, because I<both> pragmas take effect at compile time, before
+I<either> C<sort()> happens.
+
+ { use sort "_quicksort";
+ print sort::current . "\n";
+ @a = sort @b;
+ }
+ { use sort "stable";
+ print sort::current . "\n";
+ @c = sort @d;
+ }
+ # prints:
+ # quicksort stable
+ # quicksort stable
+
+You can achieve the effect you probably wanted by using C<eval()>
+to defer the pragmas until run time. Use the quoted argument
+form of C<eval()>, I<not> the BLOCK form, as in
+
+ eval { use sort "_quicksort" }; # WRONG
+
+or the effect will still be at compile time.
+Reset to default options before selecting other subpragmas
+(in case somebody carelessly left them on) and after sorting,
+as a courtesy to others.
+
+ { eval 'use sort qw(defaults _quicksort)'; # force quicksort
+ eval 'no sort "stable"'; # stability not wanted
+ print sort::current . "\n";
+ @a = sort @b;
+ eval 'use sort "defaults"'; # clean up, for others
+ }
+ { eval 'use sort qw(defaults stable)'; # force stability
+ print sort::current . "\n";
+ @c = sort @d;
+ eval 'use sort "defaults"'; # clean up, for others
+ }
+ # prints:
+ # quicksort
+ # stable
+
+Scoping for this pragma may change in future versions.
=cut
==== //depot/perl/lib/sort.t#8 (text) ====
Index: perl/lib/sort.t
--- perl/lib/sort.t#7~16286~ Tue Apr 30 12:03:34 2002
+++ perl/lib/sort.t Mon Aug 5 15:42:09 2002
@@ -28,7 +28,8 @@
use Test::More tests => @TestSizes * 2 # sort() tests
* 4 # number of pragmas to test
+ 1 # extra test for qsort instability
- + 3; # tests for sort::current
+ + 3 # tests for sort::current
+ + 3; # tests for "defaults" and "no sort"
# Generate array of specified size for testing sort.
#
@@ -158,5 +159,25 @@
use sort qw(_qsort stable);
is(sort::current(), 'quicksort stable', 'sort::current for _qsort stable');
main(0);
+};
+die $@ if $@;
+
+# Tests added to check "defaults" subpragma, and "no sort"
+
+eval q{
+ no sort qw(_qsort);
+ is(sort::current(), 'stable', 'sort::current after no _qsort');
+};
+die $@ if $@;
+
+eval q{
+ use sort qw(defaults _qsort);
+ is(sort::current(), 'quicksort', 'sort::current after defaults _qsort');
+};
+die $@ if $@;
+
+eval q{
+ use sort qw(defaults stable);
+ is(sort::current(), 'stable', 'sort::current after defaults stable');
};
die $@ if $@;
End of Patch.
