[P5P] Re: Short circuiting sort

On approximately 6/25/2004 4:28 AM, came the following characters from
the keyboard of John P. Linderman, and is responded to by "the other
Linderman" who remembers encountering this one in a former position at a
former subsidiary of this one's corporation:
So in terms of N items in the array and M items desired...

One trivial way to take advantage of the hint is to recall that the
lowly N-squared bubble sort (and variations) produces one high (or low)
value per pass, and that for small M and large N, that M*N is smaller
than N lg N.

And after we have the bubble sort implementation working, optimizing
to N lg M is easy enough to do by using a binary search to find the
insertion point in the short list. The short list is sorted.

Algorithm:

slice off first M elements into @Short[0..M-1]:
@Short[0..M-1] = @Long[0..M-1];

sort @Short in place and stable (insertion? M is small)

For each $Elm (@Long[M..N-1]) {

#ifdef SIMPLE_BUBBLE

# this approach is easy to write and understand
# and for small M there are few additional comparisons
my ShortPosition = M-1
while(comparison($Elm, $Short[ShortPosition]) < 0){
$Short[ShortPosition + 1] = $Short[ShortPosition];
$Short[ShortPosition--] = $Elm;
}

#elsif
# we do fewer comparisions to locate where
# the Elm goes, and then slide the rest of
# short down.

next unless comparison($Elm, $Short[M-1]) < 0;
LowerBound = 0
UpperBound = M-2
# we want to find the highest index in Short that
# gives us a negative comparison against the
# new element, and insert the new element before it.

while(LowerBound < UpperBound){
Guess = LowerBound + floor((UpperBound - LowerBound) / 2)
if (comparison($Elm, $Short[Guess]) < 0){
# Element goes before Guess
UpperBound = Guess
}else{
# Element goes on or after Guess
LowerBound = Guess
};
}
# Guess, LB, and UB are all the same now.
# (LB=0 is correct for M==1, FWTW )
# and we want to insert the new element before
# the determined location by shifting everything
# down and then assigning.

Pos = M ;
While (Pos-- > LowerBound){
Short[Pos] = Short[Pos - 1]
}

Short[LowerBound] = $Elm



#endif


}


The worst cases for both, a descending list, are N*M or N * Lg M
comparisons and N*M element shiftings. One might be able to
save a few element shiftings by optimizing a mergesort to throw
away results we don't care about, but in situations other than
descending lists, knowing what the bar for entry into the short
list is, as it lowers, in a single pass, will (I expect), save
many comparisons: with a butchered mergesort, we're going to
be throwing away unnecessarily sorted sequences.

Assigning to $Short[M] can be easily optimized out too.

With regard to yesterday's post in which I'm thinking aloud,

Considering bubbling or inserting the new, smaller element, based
on expected average-case number of comparisons required, I think that
bubbling will be better for M less than or equal to five.

The reason is, binary search _always_ has to do lg(M-1) comparisons
while bubbling can do anywhere from one to M-1 comparisons because
bubbling stops when the new element has done like a mature executive and
risen to the point where it can't rise any further, an expected number
of (M-1)/2 comparisons.

(M-1)/2 is equal to lg2(M-1) at M=5.

On approximately 6/29/2004 3:10 PM, came the following characters from
the keyboard of david nicol:
I'm not sure what you are calculating here? The cost of inserting the
data into the short list? I'm not sure that is the most interesting
part of the task. Since M is small, whether entries are placed by
bubble or insertion sort is somewhat ho-hum. In fact, depending on how
you generate the M elements, it may be that there is no work to sort
them... they might get handed to you sorted. On the other hand, maybe
I'm missing a key unstated assumption that would make me understand what
you are talking about.

So I find the task of obtaining the correct M elements from the N
elements to be the more interesting task. Depending on where the M
elements are stored.... if already in a "temporary array", then they
could be sorted "in place", and after M passes of the bubble sort, the
first (or last, depending on how it is coded) M entries are sorted.
This takes (N-1) + ... + (N-M) comparison/swap operations. If you sort
the whole array, M approaches N, and the complete cost of sorting is
O(N**2/2) IIRC. But after M passes, the short array is just a slice of
the partially sorted large array. If it is not already in a temporary
array, there might be a copy cost to put it in a temporary array, unless
the result is to be stored replacing the original array, in which case
we can do the same in-place sort.

With something like a heap sort, the highest/lowest elements can also be
generated in order. It being 25 years or more since I last analyzed the
costs of heap sort, I'm not going to attempt to regurgitate them in
this email. IIRC the heap sort is a better sort choice than quicksort
if you only want a few of the top/bottom few entries.... IIRC both are
o(N lg N), but for complete sorting, quicksort has a lower coefficient
than heapsort.

I'm not sure offhand how many result elements are at the crossover
between where bubble sort is best and heapsort becomes best, but I
believe both of those will generate entries in sorted order faster than
sorting the whole array to throw away most of the results.

As an alternative to the copy cost above, I posit an algorithm I'll call
scan-select (maybe someone has a name for it) where the original data
isn't modified, but on the first pass you go through all N entries and
look for the highest/lowest number, and keep track of where it was, and
select it. Then on each subsequent scan you go through all the data
that hasn't already been selected, and look for the highest/lowest
number, and select it, until you have accumulated M entries. This would
have a similar cost to the bubble sort, but higher overhead to avoid
previously selected entries. So that higher overhead has to be traded
off against the cost of a copy + partial bubble sort or a copy + partial
heap sort.

G'day Glenn / P5P,

Glenn Linderman wrote:
This sounds just like Selection Sort to me, although stopping after you
have the required number of elements. It's O(N^2), although in this
case it would be O(N*M).

In the case where M approaches N, Selection Sort will be a very poor
choice, and we'd be better off using an O(N*logN) sort and then
returning only the wanted elements.

Many of the more efficient sorts (eg, Quicksort and Mergesort) use a
divide-and-conquer approach. I would propose that a good solution is to
use a modified version of one of these sorts. Allow the algorithm to
divide, but only conquer each segment if it could possibly contain
elements that we care about in the output list.

Let's use Quicksort with an array of N=100 elements, and we desire the
smallest M=10 elements.

* Quicksort starts by choosing a pivot, an dividing elements
into greater than or less than this pivot. On average,
this will break our array in half (50/50). Since we know
that we're only interested in M=10 smallest elements, we can
drop the top 50 elements immediately.

* Next pass we choose another pivot, and repeat. On average
this will split the array in half again (25/25). Again,
we can dump the top 25 elements.

* Rinse, repeat. Next step we get 12/13 on average, dump the
top.

* Next pass we end up dividing into two parts, both which will
(on average) contain elements for our final list. We
keep all the elements and continue to sort until done, and
scoop up the required M=10 elements.

The big advantage of this is that it discards on average half of the
elements in the array each pass, until we're only dealing with elements
that are candidates for our final array. This is *very* fast.

The downside is that quicksort has pathological cases when it performs
very poorly, such as sorting an already sorted list. In this case we
don't get to discard any elements at all (except our pivots), and
performance plummets. This is why Perl doesn't use quicksort any more
to implement sort().

I haven't thought about any other sorting algorithms yet. I agree that
heapsort is definitely worth examining as an efficient way to gathering
only the first sorted M elements, as at each stage the next element is
known (the root), and there are only two choices for the next element
(the immediate children of the root).

Cheers,

Paul

In article <40E2774F.1070106@perltraining.com.au>,
Paul Fenwick <pjf@perltraining.com.au> writes:
Mergesort works well too if you cut off runs at M.
you start with N/M groups of M elements, each sort in O(MlogM), so that
gives (NlogM).
Then you need to combine N/M runs, which is (N/M-1) combines, in which each
can stop after collecting M elements => O(N).
So the sum is still O(NlogM)

And since the plain sort already is mergesort, i think that would be
the best choice since it will e.g. have the same stability properties,
and the partial sort smoothly extends to the full sort.

G'day Ton/P5P,

Ton Hospel wrote:
You're absolutely right. Quicksort throws away unnecessary elements at
the start (except in pathological cases). Mergesort throws them away at
the end (once runs start to become bigger than M). Both of them become
much faster by having M < N.

In the end, I would expect the complexity to be the same.
I'm inclined to agree here. If regular sort is simply a special case of
truncated sort, then it avoids the unpalatable idea of having to
maintain two separate sorts in Perl. This is a good thing.

The question still remains as to what should happen when sort is called
in a scalar context. Does it return the smallest value, the sortedness
value, or play nethack? ;)

Cheers,

Paul

There is a linear algorithm possible, although that will not sort the M
elements. It is possible to find the Mth element of a set of N elements in
O (N) time (albeit with a heavy constant). Given the Mth element, finding
the first M elements requires another, single, pass over the entire set.

In practise however, I'd use a heap with M elements. Pass once over the
entire set, and for each element, if it's less than the largest element
in the heap, swap it with the largest, and heapify the heap. This will
be O (N log M) worst case, and O (N) if the set is already sorted.


Abigail

On approximately 6/30/2004 6:11 AM, came the following characters from
the keyboard of Ton Hospel:
Thanks for describing how one would do this with a modified merge sort.
I agree that there would be some benefits to using merge sort, because
of perl already using mergesort, but I'm uncertain that any of the code
could be reused, without slowing down the "full sort", which wouldn't be
a brilliant thing to do.

Although I recall that O(N lg N) heapsort had a high coefficient, which
is what makes quicksort generally outperform heapsort, and IIRC
mergesort also generally outperforms heapsort for doing complete sorts,
the description above sounds like it would also have a fairly high
coefficient...especially for extremely small M.

For M == 1, it is pretty clear that a selection sort couldn't be
outperformed.

I'm not sure how big M has to get, before M passes of bubble sort
outperform selection sort.

And I have no clue how big M has to get before M passes of bubble sort
are less efficient than either heapsort or mergesort, or which would be
the next contender.

And I also have no clue how big M has to get before sorting the whole
array is more efficient than some number of passes heapsort or mergesort
(due to extra work to determine early stopping points).

Indeed not. Slowing down the general case to benefit a special case isn't
going to get in. And I've see no evidence to counter my intuition that this
case of top M is anything but rare.

Does the peephole optimiser currently have any way to optimise

@a = reverse sort @b

into

@a = sort {$b cmp $a} $b;

but without the explicit sort comparison?

Nicholas Clark

Shouldn't be too difficult.

There's some reverse-handling code in pp_sort which I took
to be responding to a hint that

reverse sort ...

has been encountered:


if (PL_op->op_private & OPpSORT_REVERSE) {
SV **p = sorting_av ? AvARRAY(av) : ORIGMARK+1;
SV **q = p+max-1;
while (p < q) {
SV *tmp = *p;
*p++ = *q;
*q-- = tmp;
}
}

No, that's for optimising away the sort block in

@x = sort {$b cmp $a } @y;

On approximately 6/30/2004 11:58 AM, came the following characters from
the keyboard of Nicholas Clark:
I've certainly written plenty of "selection" loops to determine the
smallest or largest item in a group. That's "top 1".

Having it in C code instead of perl code would certainly be faster.
"Top M", if done correctly, could produce "top 1" in an efficient manner.

There are certainly lots of "Top 10" lists that float around the
internet, but I don't think they are done by sorting LOL But programs
like "top", and a variety of statistical analyses will report the "top
M" regions by sales, the "top M" salesmen, etc. Perhaps the full
ranking is desired, but often not.

So if I can think of a couple uses off the top of my head, it could be
that it is not as rare as you think. Or maybe it is.

I can also imagine code like

while ( sort @array )
{
...
last if ... ;
...
}

for large @array, I speculate that it might often be more efficient to
use an incremental sort than to do a full sort, and only use a fraction
of the results. Of course, it depends on the likelihood of using a
small fraction, so probably in cases like this a user hint should
determine whether to use a full sort, or an incremental sort.

And perhaps "incrementalsort" would be a good explicit name to give to
it... it would be the explicit user hint to use bubble or heapsort or
whatever might be best (based on the size of the array).

And how does this fit into the "top M" discussion? Well, if
incrementalsort were available, the user could explicitly select it when
want desiring 1 or M elements from an array, and code something like:

$smallest = incrementalsort @array;
$largest = reverse incrementalsort @array;
( $smallest, $nextsmallest ) = incrementalsort @array;
@smallest_seven[ 0 .. 6 ] = incrementalsort @array;
@top_ton[ 0 .. 9 ] = reverse incrementalsort @array;

Dave says it shouldn't be too difficult, and it sounds useful. Similar
optimizations should be done for "reverse incrementalsort" also :) (per
the above examples)

Here's a question for you: does perl's optimizer use bubble sort (or a
variant) for sorting arrays of sufficiently small size, or does it use
mergesort for everything? For small N, bubble sort is faster than
mergesort... A related question is, what is the underlying sort
technique used by perl's mergesort for sorting a single run?

use Lazy::Sort;
{
tie my @Lazy => Lazy::Sort => sub($$){$_[0] cmp $_[1]} => @Array;
local *_;
while(defined ($_ = shift @Lazy)){
...
last if ...
}
...
}

I'm about to post Lazy::Sort to p5p, enough of it to do that at least,
encourage me to CPANify it and I expect I will. A better interface
would be good though.

Does not the combining involve more comparisons?

In article <1089335013.1041.182.camel@plaza.davidnicol.com>,
david nicol <davidnicol@pay2send.com> writes:
Sure, but I accounted for them. N/M combines each collecting M elements
from 2 runs of M => M compares per combine => O(N) compares, which then
gets subsumed in the O(N log M) we already had from the first step

On approximately 7/9/2004 7:19 AM, came the following characters from
the keyboard of Ton Hospel:
I appreciated as interesting the idea that a "top N sort" might
appropriately be different than the "incremental sort of unknown result
elements".

To get a feeling for how different, it would be interesting to compare
the costs of obtaining each element in turn for the incremental sort,
vs. the costs of obtaining the top N.

And we've only seen a discussion of discarding elements (and
corresponding costs) applied to merge sort, not to other possible
sorts... perhaps the others don't lend themselves to discarding elements
as well as merge sort does.

But then unless the total cost of obtaining the top N elements in
significantly less for a top N sort than for the incremental sort,
perhaps only the incremental sort need be implemented.

I look forward to David's Sort::Lazy module; perhaps it would be a
suitable framework for investigating some of these sort characteristics
empirically? And also providing a framework for implementing and
measuring both the theoretical costs O(N,M) and actual costs (for
particular data sets).

On approximately 6/30/2004 1:18 AM, came the following characters from
the keyboard of Paul Fenwick:
Thanks for knowing the name.

Another possible way of saving the copy cost is to intergrate the copy
into the first pass of the sort, when all the data has to be examined
once anyway, and it could be moved (and possibly reordered) at the same
time. This would probably require a customized bit of code for the
first pass, whereas subsequent passes would operate in place.
Because of the pathological cases, it is probably better not to choose
Quicksort for obtaining just a few elements either. But thanks for
describing the technique one could use for it, and possibly for some
other sorts as well.
Yes, it was because Heapsort is also O(N lg N), as well as having
producing a sorted element on each pass, that made me think it might
work effectively for this scenario, hopefully being more efficient than
bubble sort as M increases. Of course, as M approaches N, it is
probably more efficient to just sort the array with an efficient O(N lg
N) sort algorithm, and extract the needed elements... and it also seems
likely that as M approaches N, that it is less likely that there'll be a
hint as to how many elements are needed, unless the coder uses a large
slice to contrive the hint, knowing about the optimization. And for
small enough N, one should use the bubble sort anyway, so even if M is
close to N, using the hint could be worthwhile.

I am wondering if I was somehow unclear in my proposed algorithm,
archived at

http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html

which describes both bubble and inserting to place new elements in the
short list. I believe the algorithm there to be worst case N*M for
bubble and N lg M for insertion placement mechanisms. Expected case for
random data should be the sum of:

M lg M # sort the first M elements

N - M # the comparison of each element to the current
gatekeeper element

# a term that represents the base two log of M-1 multiplied
by the probability that an element will compare left of the
gatekeeper element, which itself gets adjusted left as the
long array is traversed. The probability of an element
belonging leftward from the gatekeeper falls to M/N for the
last element considered, from some larger amount that
represents the probability of $Large[$M] sorting leftward of
the rightmost element in a @Short = sort @Large[0..(M-1)].
My grasp of combinatorics is currently not up to describing
that term. And that's without considering the effect of
stability in preventing placements of elements that are
merely equivalent to the gatekeeper instead of leftward
of it.






Important points:

* One pass over all elements in long array, comparing each to
the "gatekeeper" element which is the leftmost element in the
short array.

* Additional comparisons are only required to determine placement of
an element that belongs left of the gatekeeper.

* We are only concerned with optimizing away unncessary sorting when
M is smaller than N.

* we only consider comparisons as the metric.

After the short circuiting sort optimization is in place a hint about
when the comparison function is cheap enough that we should care about
all the data shifting required for insertion sorts and reoptimize short
circuited sorts back to full sorts for sufficiently large M and
sufficiently small N-M

On approximately 7/5/2004 5:33 PM, came the following characters from
the keyboard of david nicol:
The algorithm seemed clear enough to me, but I couldn't figure out why
you were interested in dealing with the short list.... if the bubble or
heap sort on the long list returns data in sorted order, which it
should, then

push @short_list, &next_elem_from_incremental_sort();

should be adequate and optimal for putting data into the short list.
This is sufficiently trivial that additional or alternative algorithms
are not particularly interesting to me.

The interesting part of the job is figuring out how to pull the sorted
data out of the long list without doing a complete sort, and without
paying inordinate overhead needed by some fast sort algorithms, which
are definitely worthwhile when sorting the whole list, but are not
nearly as worthwhile when only needing a few elements.

G'day David / Glenn / P5P,

david nicol wrote:
Thanks for re-raising this. I had gained interest in the conversation
part-way and failed to catch-up on my background reading. I appreciate
the enlightenment, and especially appreciate the extra explanation you
provided in the post which I'm replying to.

I'll make sure that I re-read it and the other posts related to it. I
would have done so already, but I'm currently pre-coffee and swamped
with end-of-financial-year paperwork. ;(

Cheerio,

Paul

That is what I was trying to figure out, and I would like peer review
on my result of bubble for five or less and heap for six or more. M=5
is the judgement call, giving always two (after the unavoidable initial
comparison) in insertion mode whereas bubble gives an expected two with
random data.


.

I don't hold out much hope for heap. It's still a log M deep tree,
and now there are *two* comparisons at each level to sift elements
up and down. Better, I believe, to stick with a simple insertion
sort (which is stable, too). With binary search, you're never
stuck with more than N log M comparisons, which is where the real
action is... the N * M moves can be tolerated more readily.

If you want to be adventurous, you can keep track of where the new
elements are inserted... if they tend to be inserted near the end
(or not inserted at all), you can risk a comparison with the last
element (or two) before doing the binary search. For mostly
ordered data, you'd get O(N) behavior on both comparisons and moves,
which as good as you can do. For data in reverse order, you'd
settle in on the binary search and stay there, and for random data,
I suspect you'd start out doing binary, then maybe switch to linear
towards the end, as the maximal elements find their way into the
list. No doubt depends on how you keep track of how many recent
instertions go where. -- jpl

FWIW.

I think this is not unusual nor are top N. The only thing is the later is
IMO more often written like

@array=(sort @foo)[0..9];

And not like

($one,$two,$three)=sort @foo;

As for anything more than a few elements the latter style is a real pain.
Dunno if this is an important consideration but I thought I'd point it out.

So I would say that this optimization is a worthy endeavour. But that's just
me.

BTW, I suspect that this stuff isnt done much in modules but is done a lot
in application code. At least that's where I do it.

Cheers and thanks for the interesting reading and debate,
Yves

On approximately 7/1/2004 3:02 AM, came the following characters from
the keyboard of Orton, Yves:
That is another type of source for "hint", and thanks for pointing out
the technique.

I meant to reply to the porters at large earlier, but succeeded in only
contacting a couple people. Heap sort is going to double the number
of comparisons realtive to a binary search, since it has to do two
compares at each level of the log M tree. It saves moves, but moves
are cheap, and comparisons are dear, so I don't see heap sort ever
being the winner. You can get N log M comparisons from the binary
search you have at
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html
and N * M moves, which will beat the wholesale sorts for small enough M.
But the wholesale merge sort does a nice job on orderly data, and will
beat the specialized sort if there are fewer than log M runs, for example.
I can imagine keeping track of where insertions happen, and biasing the
initial guess-point for the binary search when it appears the data are
non-random. That could make comparisons look more like N than like N log M
for orderly data. -- jpl

Right. The questions are, given N and M, when do we want to collect
runs?


I imagine run-collecting as the first step in "lazy sort" which might be
a special case of another kind of sort, I'm not sure. "Nicol's Lazy
Sort" (so I'm bold) goes like this:

1: gather runs, in a stable way.
Takes up to 2N comparisons:

sub Lazy::Sort::TIEARRAY{
my $pack = shift;
my $compare = shift;
my @Ary = @_;
my @Runs;
my $Run;
$Runs[$Run=0] = [0];
for $index (1..$#Ary){
if ( &$compare( $Ary[$index], $Ary[$$Runs[$Run][0]]) < 1){
unshift @{$Runs[$Run]}, $index;
next;
}else{
if ( &$compare(
$Ary[$index],
$Ary[$$Runs[$Run][$#{$Runs[$Run]}]]) >= 0){
push @{$Runs[$Run]}, $index;
}else{
$Runs[++$Run] = [$index];
}
}
bless [$compare,\@Ary, \@Runs], 'Lazy::Sort';
};


more comparisons if we keep stability by bubbling equal elements
in from the front, so we don't. A run of equals will get pushed.


2: compare leftmost of all runs to find leftmost and shift it
off, takes R (number of runs remaining) comparisons:

sub Lazy::Sort::SHIFT{

wantarray and eval{Games::Roguelike::Nethack::play()};
my ($compare,$Ary,$Runs) = @_[0,1,2];

# empty run arrays are prevented by splicing out empty
# runs as they occur
# while(@{$Runs->[0]} == 0) {
# shift @{$Runs};
# @{$Runs} or return undef;
#};
@{$Runs} or return undef;

my $best = $Runs->[0]->[0];
my $bestrun = 0;

for my $run (1..$#{$Runs}){
if (&$compare(
$Ary->[$best],
$Ary->[$Runs->[$run]->[0]]
) < 0){
$best = $Runs->[$run]->[0];
$bestrun = $run;
}
}

shift @{$Runs->[$bestrun]};
if (@{$Runs->[$bestrun]} == 0){
splice @{$runs},$bestrun,1;
}
return $Ary->[$best]
}





I believe I have just described a crippled merge-sort, that finds runs
once and then does R comparisons to pull out each element. Ton's
insight that if we know M in advance we can throw away elements in a run
past M is good.

By finding runs and then pulling elements off the runs until we have M
of them, we get worst-case of 2N comparisons to find the runs and a
worst case of R=N/2 runs for a contrived sequence such as

@Ary = map { ($_ | 1) ? $_ : - $_ } (1000..1)

After finding runs, we can find the M best with M*R more comparisons.
Which may or may not be an improvement over a NlogM single pass. How
big do the numbers have to be before it's worth the expected 1.5*N
comparisons to find out how small R is, given that after determining R
we can still fall back to the single pass when M*R is larger than NlogM?


Finding the hints is the other half of the problem. I've seen several
identifiable cases so far:


@result = (sort @Ary)[0..CONSTANT];

($first, $second, $third) = sort @Ary;

Would it be possible for the hint to be of the form of the pre-sized
assigned-to array, so the short-sort could assign directly into it
instead of using the stack?

while collecting runs we can give up on the whole deal when we have too
many runs. Too many runs is :

M*R > NlogM

R > (NlogM)/M

so, calculate that, then collect runs, if we make it through the whole
array with fewer, shift elements off of runs, otherwise do a single
pass with binary insertions.


I'm sure everyone is sick of me posting less-than-fully-baked postings
by now, I thank you for your continuing indulgence.

G'day David / P5Ps,

david nicol wrote:
<pedant>
Module names should go from general to specific. Hence 'Sort::Lazy' may
be a better choice. (This also lines up nicely with all the other
Sort::* modules on CPAN.
</pedant>
I *really* like the idea of a lazy sort, where each element is produced
on demand. However I believe that it's different to a 'truncated sort',
where we can throw away all but the top M elements.

In a lazy sort, we may be asked to produce the entire sorted list,
sooner or later, we can't throw away any elements. For a truncated
sort, we know that we're never going to asked more than M. A truncated
sort definitely allows you to run much faster, using my suggestion of
discarding elements in Quicksort, or Ton's suggestion of truncating runs
in Mergesort.

The two sorts have different applications, too. Truncated sorts are
perfect for 'top 10' style lists. Lazy sorts are ideal when you wish to
go through elements in a sorted order, but have a good reason to believe
that you may stop early, but don't know in advance at which element you
wish to stop.

I would be impressed if you can do better than heap-sort for a lazy
sort. It seems ideal for the job, as it produces exactly one sorted
element each iteration, and runs in NlogN time. There are a few
efficient algorithms out there as well.

I do think that your merge sort has merit for truncated sort. I just
don't know a good way of passing in hints. ;(

Cheers,

Paul

I was afraid somebody might say that. This breaks the promise of
stability. The order of equal elements is now reversed from the
input order. (I'm about to disappear on vacation, so don't
interpret my silence as lack of interest). -- jpl

Gosh. It takes quite a lot of effort to contrive a test that actually
demonstrate this. The simplest scenario I can think of is tied values.

"Reverse deoptimised" has sufficient extra ops to confound the peephole
optimiser and prevent it from using the (faulty) reverse optimisation:

$ cat sortstable.pl
#!perl -w

use strict;

package Oscalar;
use overload (qw("" stringify 0+ numify fallback 1)
);

sub new {
bless [$_[1], $_[2]], $_[0];
}

sub stringify { $_[0]->[0]}

sub numify { $_[0]->[1] }

package main;

my @orig = qw (A B A C A D A E A);

my @input;
foreach (0..$#orig) {
push @input, new Oscalar $orig[$_], $_;
}

sub report {
printf "$_ %d\n", $_ foreach @_;
}

report @input;

print "Forwards\n";
report sort {$a cmp $b} @input;

print "Reverse\n";
report sort {$b cmp $a} @input;

print "Reverse deoptimised\n";
report sort {$$ - $$ || $b cmp $a} @input;
__END__
$ ./perl -Ilib sortstable.pl
A 0
B 1
A 2
C 3
A 4
D 5
A 6
E 7
A 8
Forwards
A 0
A 2
A 4
A 6
A 8
B 1
C 3
D 5
E 7
Reverse
E 7
D 5
C 3
B 1
A 8
A 6
A 4
A 2
A 0
Reverse deoptimised
E 7
D 5
C 3
B 1
A 0
A 2
A 4
A 6
A 8


I think that if we negate the sort comparison for reversal, rather than
reversing the order of the sorted elements, we'd be OK.

But this also means that my proposed optimisation doesn't work (directly
as I thought) - *it* ought to set this (current) reversed flag, and
the current peephole optimiser needs to flag the negation, to keep stable
sorts correctly stable.

Nicholas Clark

Balderdash.

[david@plaza david]$ perl -le '@Ar = qw/5one 4one 5two 4two/; print
foreach sort {$b <=> $a} @Ar'
5two
5one
4two
4one
[david@plaza david]$ perl -le '@Ar = qw/5one 4one 5two 4two/; $default =
0; print foreach sort {$b <=> $a or $default} @Ar'
5one
5two
4one
4two

overloaded values are what is in the 5.9 test suite, which includes
tests for stability of reversed sorts. Here's two additional tests
that use regular scalars instead of overloaded ones, FWIW.

Based on my memory of the thread David figured a way to test sort stability
without resorting to overloading, by using <=> and not-really-numbers
rather than the complex overloading games I thought of.

However, the patch isn't warnings clean, which given that sort.t runs under
warnings, isn't going to fly.

Nicholas Clark

Yes, but in this case what does mean the comment :
Easily fixable, just like the test count :)

I think the comment should be:

# test that optimized {$b cmp $a} and {$b <=> $a} remain stable
# (new in 5.9) without overloading

The code definitely needs to use <=>, otherwise it's not testing stability.


Ronald

--- perl-current/t/op/sort.t Tue Jul 13 10:29:38 2004
+++ perl-current-new/t/op/sort.t Wed Jul 21 17:04:53 2004
@@ -22,7 +22,7 @@
my $upperfirst = 'A' lt 'a';

# Beware: in future this may become hairier because of possible
-# collation complications: qw(A a B c) can be sorted at least as
+# collation complications: qw(A a B b) can be sorted at least as
# any of the following
#
# A a B b
@@ -577,6 +577,15 @@
@input = sort {$b <=> $a} @input;
ok "@input", "G H I D E F A B C", 'stable $b <=> $a in place sort';

+# test that optimized {$b cmp $a} and {$b <=> $a} remain stable
+# (new in 5.9) without overloading
+{ no warnings;
+@b = sort { $b <=> $a } @input = qw/5first 6first 5second 6second/;
+ok "@b" , "6first 6second 5first 5second", "optimized {$b <=> $a} without overloading" ;
+@input = sort {$b <=> $a} @input;
+ok "@input" , "6first 6second 5first 5second","inline optimized {$b <=> $a} without overloading" ;
+};
+
# These two are actually doing string cmp on 0 1 and 2
@input = &generate1;
@output = reverse sort @input;

Thanks, applied as #23166 to bleadperl.

no not at all. We have been calling the optimization "{$b cmp $a}"
even though it works with both alpha-compare and the spaceship operator.

Switching to the spaceship in the comment would be clearer.

I was not aware that the overloaded tests were already in there when I
went to add the native-overloaded ones using "not-really-numbers."
Overloaded values are treated a little bit different than native SVs
so the non-overloaded test does test a combination that is not being
otherwise tested. I cannot imagine a scenario where the oveloaded tests
would pass and
sort { $b <=> $a } @input = qw/5first 6first 5second 6second/
would fail.

Yes I can -- I have an active imagination -- a misguided fool makes sort
functioning dependent on the elements being magical. These tests would
then fail.

I've removed the optimisation with change 23093
Specifically I've disabled the code in op.c that adds the hint, as I believe
that the hint is correct for the case of reverse sort ...

Nicholas Clark

Which is now optimised in list context - change 23102

I'm not sure how worthwhile this really is, but I think it means that
there's no argument about what's the most efficient way to reverse sort
a list - don't write a reversed comparison function, simply write
reverse sort ....

Nicholas Clark

I wonder if this could be turned into yet another context -- "reverse
list" context -- causing any returning array to get reversed on the
stack before being returned, in a lighter way than calling the reverse
function. Just another idea.

Based on the number of regression tests that I broke while implementing
this, I don't think that it's a very common scenario, so would be complicating
the general case for something rather specific and very rare. Plus it's unclear
how to make any of it work in a backwards compatible way.

Nicholas Clark

I hope you had fun trying.

How impossible is it to find out the size of an Lvalue array? I'm
imagining defining the true value of wantarray() function to be
a reference to the array that is to be filled by the result.

Is that possible?.

Eh? what would wantarray return a ref to in

sub f { wantarray() ... }
($a, $b, @c) = f();

an array of aliases to $a, $b, and $c:

[${\$a},${\$b},${\$c}]


so that assigning to

@{wantarray()}

will be the same thing as returning values. Except then we need to
get out of the function somehow. So maybe optimizing the stack-copies
out of returning would only happen when assignment to @{wantarray()}
happens in a return:

return @{wantarray()} = qw/foo bar baz/;

Or better yet, assigning to @{wantarray()} or a slice of it would
imply returning.

This might get real confusing real fast, and I can't right away come up
with a use for the feature that wouldn't be more cleearly written using
C<map> and doing explicit dispatch outside of the function.

It would be a powerful implementation-hiding abstraction

sub f(){
my $target = wantarray() or die 'usage: ($a, $b, $c) = f()';

my @NeedsEffing = grep
{effthisp $target->[$_]}
(0..$#$target);

@$target[@NeedsEffing] =
map
{effthis $_}
@$target[@NeedsEffing];
}


but what would it give us that we can't already get by making the
assignee one of the function parameters instead of an l-value?

sub f(@){
wantarray() or die 'usage: f($a, $b, $c)';

my @NeedsEffing = grep {effthisp $_[$_]} (0..$#_);

effthis( $_ ) for @_[@NeedsEffing];
}


The real advantages are that access to details about the Lvalue allows
expected-type-based polymorphism. If we care about that.

For the purposes of implementing a truncated sort optimization, all we
care about is the length of the L-array, if any. If that's not going to
be available, truncated sorting is best left to the unwritten
Sort::Truncated module and however the invocation works it will take M,
or at least the target array, as a parameter.

G'day David / P5P,

david nicol wrote:
So what do we do in the case of:

print f();

wantarray() should clearly by true, but there are no variables that we
can alias.

This could be worked around by creating an alias to a transient
anonymous variable, which is then passed to print upon completion.
However I'm not sure if we can do that without losing performance.

Cheerio,

Paul

s/performance/sanity/;

I really don't think that there is anything useful to gain here.

Nicholas Clark