Re: Sorting in-place
On Mon, Aug 06, 2001 at 01:21:12PM +0300, Ilmari Karonen wrote:
so it will return the empty list in list context? Or one could just
simply write
return;
instead.
Yes, that's what I should have used. I sometimes get flagitis.
Anyhow, the point is you can handle the accidentaly use of
void-context sort as last-evaluated-expression problem with a
return. Still, I think it will cause confusion.
There's nothing stopping anyone from writing a Sort::Inplace XS module
that exports both a sort_inplace() function and exports on request a
sort() that sorts inplace in void context. You could even go so far
as to override CORE::GLOBAL::sort so everywhere has this new sort().
I encourage someone to do so.
About sort() in scalar context. It appears perl already optimizes
this away to simply return the size of the array. However, it's not
safe to change this to sort in-place. Consider:
my @stuff = ();
sub foo {
...do some calculations and things...
return sort @stuff;
}
so it would normally be used like this:
my @whatever = foo(...);
but it could also be called like this:
my $how_many = foo(...);
not realizing foo() calls sort(). If we made sort() in scalar context
sort @stuff in-place, it would change the behavior of that code.
@stuff would inadvertently get sorted.
--
Michael G. Schwern [EMAIL PROTECTED]http://www.pobox.com/~schwern/
Perl6 Quality Assurance [EMAIL PROTECTED] Kwalitee Is Job One
Skrewtape I've heard that semen tastes different depending on diet. Is that
true?
Skrewtape Hello?
Schwern Skrewtape: Hang on, I'm conducting research.
Re: Sorting in-place
On Mon, Jul 30, 2001 at 11:45:38PM +0200, Marc A. Lehmann wrote: I'm trying to think of common places where Csort @inplace might accidentally be used in list context, such as the end of a block, How about: [example that didn't work as advertized, later backed up by one that did] I don't understand where you are on this. Are you saying that the backward compatibility police might object? Why? Because someone might be using sort (unknowingly) in a scalar/void context and relying on side-effects? I don't think there's any backwards compatability problems at all here. And as far as accidental use in a list/scalar context: wouldn't that be a problem now anyways? I'm also thinking if there's any functionality in Perl that is analogous. ie. in one context it leaves its arguments alone, in another it modifies them. It looks very dangerously to me ;) This is the real issue (if there IS a real issue, and I don't believe there is). But the problem solved is similar to that of keys/values and each; and the smart range operators in later perls: avoiding having heaping piles of crap returned by an operator/function that can better be done in place. If we can do this without adding a keyword I don't see why not. This feels like the Right Thing to do. It really does. -- Clinton A. PierceTeach Yourself Perl in 24 Hours *and* [EMAIL PROTECTED]Perl Developer's Dictionary If you rush a Miracle Man, for details, see http://geeksalad.org you get rotten Miracles. --Miracle Max, The Princess Bride
Re: Sorting in-place
On Tue, Jul 31, 2001 at 03:50:56PM +0200, Marc A. Lehmann wrote:
however, if it did, then this would be a very common error. how do you
force void context currently? and list context? it's possible, of course,
but it's extreme action at-a-distance.
do {{EXPR; last}}
forces void context on EXPR.
do {() = EXPR}
forces list context on EXPR.
it's similar, yes, and only being able to iterate once over a hash even
in totally different modules by different authors is an extremely nasty
thing, even if it occurs rarely in practise (it bite me about three times
in the last 6 years)
If clashes with iteration is the worst thing that can happen if you share
hashes between different modules by different authors, I will change my
mind about the usefulness of lexical variables.
Abigail
Re: Sorting in-place
On Tue, Jul 31, 2001 at 09:17:33PM +0200, Abigail [EMAIL PROTECTED] wrote:
force void context currently? and list context? it's possible, of course,
but it's extreme action at-a-distance.
do {{EXPR; last}}
exactly what I mean ;)
If clashes with iteration is the worst thing that can happen if you share
hashes between different modules by different authors, I will change my
mind about the usefulness of lexical variables.
Well, sharing hashes with modules is quite common: each time you pass
a hash into a module you either have to *know* that the module author
doesn't iterate over it or take precautions. I don't know what worse
could happen, but at least it's very common and very ugly. For example,
WAIT uses hashes to iterate over documents. If, for debugging or just for
plain verboseness you print that hash somewhere else you get an endless
loop. The only way to find this bug is by looking at WAIT's sourcecode,
or by guessing that this can possibly happen. Guessing is a very bad
programming tool.
What *are* you arguing, that values() resetting each status or nested
eachs in difefrent modules depending on each other is natural??
--
-==- |
==-- _ |
---==---(_)__ __ __ Marc Lehmann +--
--==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] |e|
-=/_/_//_/\_,_/ /_/\_\ XX11-RIPE --+
The choice of a GNU generation |
|
Re: Sorting in-place
On Tue, Jul 31, 2001 at 12:34:16PM -0700, Paul [EMAIL PROTECTED] wrote:
do {{EXPR; last}}
forces void context on EXPR.
1) is the do{} necessary there?
Yes, because of the last. I think it's pretty unintuitive to having to
add the above uglyness around my last statement when I know it's the last
statement.
Wouldn't a block do by itself?
do {} *is* the block. A block inherits it's context. However, you can omit
the do for most standalone blocks.
i.e., wouldn't { EXPR } constitute void context?
It would have whatever context the block is in.
2) just for my own edification,
I assume this refers to Perl 5?
still, yes, perl5 + in-place-sort ;)
--
-==- |
==-- _ |
---==---(_)__ __ __ Marc Lehmann +--
--==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] |e|
-=/_/_//_/\_,_/ /_/\_\ XX11-RIPE --+
The choice of a GNU generation |
|
Re: Sorting in-place
On Tue, Jul 31, 2001 at 09:04:46PM +0200, Abigail [EMAIL PROTECTED] wrote: A reference *is* a scalar. And a scalar is blob of memory. With a At least *two* seperate blobs of memory (except for SVt_NULL). And it's not always possible to swap just pointers (although in the sort case it is). -- -==- | ==-- _ | ---==---(_)__ __ __ Marc Lehmann +-- --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] |e| -=/_/_//_/\_,_/ /_/\_\ XX11-RIPE --+ The choice of a GNU generation | |
Re: Sorting in-place
On Wed, 1 Aug 2001 00:24:50 +0200, Abigail wrote:
There's more than one block in do {{EXPR; last}}.
Argh!
Pretty obfuscated, that is.
--
Bart.
Re: Sorting in-place
On Wed, Aug 01, 2001 at 12:39:50AM +0200, Bart Lateur wrote:
On Wed, 1 Aug 2001 00:24:50 +0200, Abigail wrote:
There's more than one block in do {{EXPR; last}}.
Argh!
Pretty obfuscated, that is.
Straigth from perlsyn.
Abigail
Re: Sorting in-place
On Wed, Aug 01, 2001 at 02:44:12AM +0200, Marc A. Lehmann wrote: On Wed, Aug 01, 2001 at 02:13:53AM +0200, Abigail [EMAIL PROTECTED] wrote: Minor and irrelevant details. The principle, a nest of a bare block and a compound block to be able to use loop control is straight from perlsyn.pod. Not once, not twice, but three times. Not once. No matter how often you repeat it, it's not straight from the docs, it's not explained clearly. If it were explained clearly, why does perlsyn actually say that your example is wrong? Because of extraordinary clearness? Did you stop beating your wife? Perlsyn doesn't say my example is wrong. Anyway, there's no point discussing with you. Seldomly I've seen someone acting so stupid. Abigail
Re: Sorting in-place
On Wed, Jul 25, 2001 at 07:02:11PM -0500, Craig S.Cottingham wrote:
I guess the questions are: 1. why doesn't this work? and 2. can it be
made to work?
2. Yes, sort of.
#!/usr/bin/perl -w
use strict;
my @list = (1, 4, 2, 8, 5, 7, 3, 6, 0, 9);
my @sorted = sort { $a = $b } @list;
for (1..@list) {
my @dummy = sort {
($a,$b) = ($b,$a) if (($a = $b) 0);
0;
} @list;
}
local $, = ', ';
print Original: @list\n;
print Sorted: @sorted\n;
I believe that it produced the right results on the inputs you tested
it with. But can you proof your trick will always sort the array?
Hmm. Shuffling the contents of a list?
#!/usr/bin/perl -w
use strict;
my @list = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
local $, = ', ';
print Original: @list\n;
for (1..6) {
my @dummy = sort {
($a,$b) = ($b,$a) if ((rand(2) - 1) 0);
0;
} @list;
}
print Shuffled: @list\n;
I doubt very much that this is a fair shuffle. See, for a fair shuffle
each of the @list! possible permutations should have the same chance
of resulting. And, under the assumption 'rand' is perfect', I don't see
your shuffle doing that.
Abigail
Re: Sorting in-place (SOLVED? No, further mysteries!)
On Thu, Jul 26, 2001 at 10:47:05AM -0400, Clinton A . Pierce wrote: If someone can explain *this* to me, I could probably finish a patch for in-place sorting in Perl. But I'm lost as to why (or HOW) @r can be unwound like this well after the fact. This approach is never going to work. You idea is based on the fact that if Perl is going to compare $a and $b, and they are in the opposite order, Perl wants $a and $b to be swapped. That is not true. For instance, in the mergesort that is implemented in 5.7.x, in some passes (including, IIRC, the first pass) monotonic sequences (be them increasing or decreasing) are determined. If you would then swap pairs, Perl will think the entire array is already monotonic - and you will have a sort that runs in linear time! Abigail
Re: Sorting in-place (SOLVED? No, further mysteries!)
On 27 Jul 01, at 0:46, Abigail wrote: ...If you would then swap pairs, Perl will think the entire array is already monotonic - and you will have a sort that runs in linear time! And what's wrong with that? I tell my friends all the time that Perl is the best, and this would be clear evidence of its superiority over those other, pedestrian programming languages... /Bernie\ -- Bernie Cosell Roanoke Electronic Village mailto:[EMAIL PROTECTED] Roanoke, VA
Re: Sorting in-place (SOLVED? No, further mysteries!)
On Thu, Jul 26, 2001 at 08:45:17PM -0400, Bernie Cosell wrote: A tricky design decision is whether to go with a sort with better average performance in exchange for worse worst-case performance [e.g., quick sort and quickersort, that are O(N^2) worst case, if I remember long-ago comp science classes right, but are *usually* better than nlogn]. Another situation like this is a list-merge sort which is *fantastic* if the data is nearly sorted... No, they are not usually better than N log N. You can prove that in general you cannot sort faster than N log N. Period. Quicksort is expected (don't use the term 'average' here, that's too vague) O (N log N), but Theta (N^2) worst case. Only when you have restricted domains, you may be able to sort faster. For instance, sorting N integers in the range 1 .. U can be done in O (N + U) time and N strings from an alphabet of U letters and of length k can be done in O (N * k + U). (Note that sorting N strings of length k using traditional techniques takes O (N * log N * k), the fact that you don't see the 'k' usually comes that often 'k' is taken to be a constant - of course, if we take 'k' a constant, I can sort ASCII strings in O (N) time) Abigail
Re: Sorting in-place (SOLVED? No, further mysteries!)
On Wed, Jul 25, 2001 at 05:05:03PM -0700, Randal L. Schwartz wrote:
For this to work, the element indirected by $a would have to always be
to the left of the element indirected by $b, and that's probably not
true. In fact, we can see this:
I noticed that in a few of my tests and never really connected why
this happens. Thanks Randal.
So I decided to make a quick experimental hack on perl's source and
change sortcv_stacked a bit. (C source at the end of this message,
changes indicated in /**/'s). This is the comparison function that gets
called when you have a prototyped sort function.
So now when you have a prototyped sortsub:
sub foo ($$) {
}
The third argument passed is the relative position of the two
comparison values either 1 or -1. So here's the new sort function:
sub foo ($$) {
if ($_[0] $_[1] and $_[2] 1) {
($_[0],$_[1])=($_[1],$_[0]);
}
}
And calling it with:
for(0..20) { push(@r, int rand(50)) }
@s=sort foo @r;
Yeilds an @r that's properly re-ordered! An in-place sort? At least
that's what I thought when I said:
print join(',', @s), \n;
print join(',', @r), \n;
I got the correct results. Now the problem is that even though this
appears to work -- it doesn't. Saying:
for(0..20) { push(@r, int rand(50)) }
@s=sort foo @r;
print join(',', @r), \n; # Prints sorted
@s=();
print join(',', @r), \n; # Prints unsorted!
Yeilds the original unsorted list. WTF? It's as though the elements
of @r were masked by the elements of @s. It's not the patch. Without
the patch, the Prints sorted line above just Prints in weird order.
*scratching head*
Maybe this is why no-one's really looked at modifying $a and $b
within a sortsub. :)
If someone can explain *this* to me, I could probably finish a patch
for in-place sorting in Perl. But I'm lost as to why (or HOW) @r
can be unwound like this well after the fact.
-
C Source change from pp_ctl.c, sortcv_stacked(). I'm out of practice
hacking C, and the Perl source mystifies me most of the time. 5.7.0
if (AvMAX(av) 2) { /* Was 1 */
SV** ary = AvALLOC(av);
if (AvARRAY(av) != ary) {
AvMAX(av) += AvARRAY(av) - AvALLOC(av);
SvPVX(av) = (char*)ary;
}
if (AvMAX(av) 2) { /* was 1 */
AvMAX(av) = 2;/* was 1 */
Renew(ary,3,SV*); /* was 2 */
SvPVX(av) = (char*)ary;
}
}
AvFILLp(av) = 2; /* was 1 */
AvARRAY(av)[0] = a;
AvARRAY(av)[1] = b;
AvARRAY(av)[2] = newSViv(ab?1:-1); /* Relative positions */
--
Clinton A. PierceTeach Yourself Perl in 24 Hours *and*
[EMAIL PROTECTED]Perl Developer's Dictionary
If you rush a Miracle Man, for details, see http://geeksalad.org
you get rotten Miracles. --Miracle Max, The Princess Bride
Re: Sorting in-place
Clinton == Clinton A Pierce [EMAIL PROTECTED] writes:
Clinton@dummy=sort {
Clinton$r=$a cmp $b;
Clintonif ($r 0) {
Clinton($a,$b)=($b,$a);
Clinton$r=1;
Clinton}
Clinton$r;
Clinton} @list;
Clinton# Is @list sorted? Not quite...
Clinton Except this doesn't work. Oh, $a and $b get modified and they're swapped
Clinton at appropriate times, but the resulting mess in @list can hardly be called
Clinton proper ordering.
For this to work, the element indirected by $a would have to always be
to the left of the element indirected by $b, and that's probably not
true. In fact, we can see this:
@dummy = sort {
print $a $b\n;
$a = $b;
} 1..9;
4 5
5 6
3 5
2 5
1 5
5 7
5 8
5 9
7 6
8 7
9 8
2 1
3 2
4 3
See the last few? If you were to swap the 4/3 pair to put them
in order, you're actually taking them *out* of order.
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
[EMAIL PROTECTED] URL:http://www.stonehenge.com/merlyn/
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
