FAQ

Cc: Glenn Linderman <perl@nevcal.com>, Nick Ing-Simmons <nick@ing-simmons.net>
David Nicol replied to the other Linderman:
On Sun, 2004-06-20 at 14:49, Glenn Linderman wrote:

So, in the situation where you have a countable number of parameters as
the target of the sort, such as your example, or

($first, $second, $third, $fourth) = sort @ary; # only sort 4 entries

@most[ 0 .. 6 ] = sort @ary; # only sort 7 entries

the compiler could derive the hint, in a similar manner as it presently
(recent feature) derives the in-place optimization.
Yes, exactly. We would begin by providing the hint for the simple cases
and gradually exapnd the range of optimized situations . I
imagine a working intermediate stage where your first example is
optimized and your second is not, but maybe the second is already
optimized to

($most[0],$most[1],$most[2],$most[3],$most[4],$most[5],$most[6]) = ...

at some level, in which case we could get them both at the same time.
I can kind of imagine how merge sort and quicksort could benefit
from knowing that only the "top N" elements were needed (runs
longer than N could be truncated in mergesort, partitions following
the first N elements could be dropped). Certain to make things
uglier, and probably hard to do without adversely impacting full
sorts, unless a lot of code gets duplicated. Qsort would probably
be easier to jigger to take advantage, but if you want to preserve
stability, you end up paying a penalty in space. Seems harmless
to make the hint available, though. It can simply be ignored until
a clever implementation pops up. -- jpl

Search Discussions

  • Glenn Linderman at Jun 25, 2004 at 3:53 pm
    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:
    Cc: Glenn Linderman <perl@nevcal.com>, Nick Ing-Simmons <nick@ing-simmons.net>
    David Nicol replied to the other Linderman:
    On Sun, 2004-06-20 at 14:49, Glenn Linderman wrote:

    So, in the situation where you have a countable number of parameters as
    the target of the sort, such as your example, or

    ($first, $second, $third, $fourth) = sort @ary; # only sort 4 entries

    @most[ 0 .. 6 ] = sort @ary; # only sort 7 entries

    the compiler could derive the hint, in a similar manner as it presently
    (recent feature) derives the in-place optimization.
    Yes, exactly. We would begin by providing the hint for the simple cases
    and gradually exapnd the range of optimized situations . I
    imagine a working intermediate stage where your first example is
    optimized and your second is not, but maybe the second is already
    optimized to

    ($most[0],$most[1],$most[2],$most[3],$most[4],$most[5],$most[6]) = ...

    at some level, in which case we could get them both at the same time.

    I can kind of imagine how merge sort and quicksort could benefit
    from knowing that only the "top N" elements were needed (runs
    longer than N could be truncated in mergesort, partitions following
    the first N elements could be dropped). Certain to make things
    uglier, and probably hard to do without adversely impacting full
    sorts, unless a lot of code gets duplicated. Qsort would probably
    be easier to jigger to take advantage, but if you want to preserve
    stability, you end up paying a penalty in space. Seems harmless
    to make the hint available, though. It can simply be ignored until
    a clever implementation pops up. -- jpl
    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.

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • David nicol at Jun 28, 2004 at 8:31 pm

    On Fri, 2004-06-25 at 10:55, Glenn Linderman wrote:

    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.




    --
    david nicol
    this message was sent from a filtering e-mail address.
    Until I add you to my friends list, to get by Big Emet
    the cowboy doorman your reply must include a listed
    "magic phrase" such as "cat and buttered toast"
  • David nicol at Jun 29, 2004 at 10:10 pm

    On Fri, 2004-06-25 at 10:55, Glenn Linderman wrote:

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








    --
    david nicol
    "People used to be able to read my thoughts, but
    it doesn't appear to work any more. Should I eat less cheese?"
    -- Elizabeth Woods
  • Glenn Linderman at Jun 29, 2004 at 11:24 pm
    On approximately 6/29/2004 3:10 PM, came the following characters from
    the keyboard of david nicol:
    On Fri, 2004-06-25 at 10:55, Glenn Linderman wrote:

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

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • Paul Fenwick at Jun 30, 2004 at 8:18 am
    G'day Glenn / P5P,

    Glenn Linderman wrote:
    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
    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


    --
    Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
    Director of Training | Ph: +61 3 9354 6001
    Perl Training Australia | Fax: +61 3 9354 2681
  • Ton Hospel at Jun 30, 2004 at 1:12 pm
    In article <40E2774F.1070106@perltraining.com.au>,
    Paul Fenwick <pjf@perltraining.com.au> writes:
    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).
    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.
  • Paul Fenwick at Jun 30, 2004 at 2:56 pm
    G'day Ton/P5P,

    Ton Hospel wrote:
    Mergesort works well too if you cut off runs at M.
    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.
    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.
    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

    --
    Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
    Director of Training | Ph: +61 3 9354 6001
    Perl Training Australia | Fax: +61 3 9354 2681
  • Abigail at Jun 30, 2004 at 4:00 pm

    On Thu, Jul 01, 2004 at 12:55:56AM +1000, Paul Fenwick wrote:
    G'day Ton/P5P,

    Ton Hospel wrote:
    Mergesort works well too if you cut off runs at M.
    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.
    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
  • Glenn Linderman at Jun 30, 2004 at 6:42 pm
    On approximately 6/30/2004 6:11 AM, came the following characters from
    the keyboard of Ton Hospel:
    In article <40E2774F.1070106@perltraining.com.au>,
    Paul Fenwick <pjf@perltraining.com.au> writes:
    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).
    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.
    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).

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • Nicholas Clark at Jun 30, 2004 at 6:58 pm

    On Wed, Jun 30, 2004 at 11:42:44AM -0700, Glenn Linderman wrote:

    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.
    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
  • Dave Mitchell at Jun 30, 2004 at 7:41 pm

    On Wed, Jun 30, 2004 at 07:58:40PM +0100, Nicholas Clark wrote:
    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?
    Shouldn't be too difficult.

    --
    "Foul and greedy Dwarf - you have eaten the last candle."
    -- "Hordes of the Things", BBC Radio.
  • David nicol at Jul 9, 2004 at 1:36 am

    On Wed, 2004-06-30 at 14:48, Dave Mitchell wrote:
    On Wed, Jun 30, 2004 at 07:58:40PM +0100, Nicholas Clark wrote:
    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?
    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;
    }
    }
  • Dave Mitchell at Jul 9, 2004 at 10:39 am

    On Thu, Jul 08, 2004 at 08:35:49PM -0500, david nicol wrote:
    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;

    --
    Technology is dominated by two types of people: those who understand what
    they do not manage, and those who manage what they do not understand.
  • Glenn Linderman at Jun 30, 2004 at 9:08 pm
    On approximately 6/30/2004 11:58 AM, came the following characters from
    the keyboard of Nicholas Clark:
    On Wed, Jun 30, 2004 at 11:42:44AM -0700, Glenn Linderman wrote:

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

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

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • David nicol at Jul 9, 2004 at 1:45 am

    On Wed, 2004-06-30 at 16:08, Glenn Linderman wrote:
    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.
    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.


    --
    david nicol
    "cat and buttered toast"
  • David nicol at Jul 9, 2004 at 1:03 am

    On Wed, 2004-06-30 at 08:11, Ton Hospel wrote:
    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.
    Does not the combining involve more comparisons?

    --
    david nicol
    this message was sent from a filtering e-mail address.
    Until I add you to my friends list, to get by Big Emet
    the cowboy doorman your reply must include a listed
    "magic phrase" such as "cat and buttered toast"
  • Ton Hospel at Jul 9, 2004 at 2:21 pm
    In article <1089335013.1041.182.camel@plaza.davidnicol.com>,
    david nicol <davidnicol@pay2send.com> writes:
    Does not the combining involve more comparisons?
    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
  • Glenn Linderman at Jul 9, 2004 at 6:46 pm
    On approximately 7/9/2004 7:19 AM, came the following characters from
    the keyboard of Ton Hospel:
    In article <1089335013.1041.182.camel@plaza.davidnicol.com>,
    david nicol <davidnicol@pay2send.com> writes:
    Does not the combining involve more comparisons?

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

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • Glenn Linderman at Jun 30, 2004 at 6:27 pm
    On approximately 6/30/2004 1:18 AM, came the following characters from
    the keyboard of Paul Fenwick:
    G'day Glenn / P5P,

    Glenn Linderman wrote:
    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
    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.
    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.
    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().
    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.
    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).
    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.
    Cheers,

    Paul
    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • David nicol at Jul 6, 2004 at 12:33 am

    On Wed, 2004-06-30 at 03:18, Paul Fenwick wrote:
    Glenn Linderman wrote:
    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
    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.

    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


    --
    david nicol
    "cat and buttered toast"
  • Glenn Linderman at Jul 6, 2004 at 1:38 am
    On approximately 7/5/2004 5:33 PM, came the following characters from
    the keyboard of david nicol:
    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.
    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.

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • Paul Fenwick at Jul 6, 2004 at 1:51 am
    G'day David / Glenn / P5P,

    david nicol wrote:
    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
    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

    --
    Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
    Director of Training | Ph: +61 3 9354 6001
    Perl Training Australia | Fax: +61 3 9354 2681
  • David nicol at Jul 5, 2004 at 11:06 pm

    On Tue, 2004-06-29 at 18:24, Glenn Linderman wrote:

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


    .
    --
    david nicol
    this message was sent from a filtering e-mail address.
    Until I add you to my friends list, to get by Big Emet
    the cowboy doorman your reply must include a listed
    "magic phrase" such as "cat and buttered toast"
  • John P. Linderman at Jun 30, 2004 at 6:34 pm

    Paul Fenwick, from down under, noted:

    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).
    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
  • Orton, Yves at Jul 1, 2004 at 9:59 am

    I've certainly written plenty of "selection" loops to determine the
    smallest or largest item in a group. That's "top 1".
    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
  • Glenn Linderman at Jul 1, 2004 at 8:50 pm
    On approximately 7/1/2004 3:02 AM, came the following characters from
    the keyboard of Orton, Yves:
    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.
    That is another type of source for "hint", and thanks for pointing out
    the technique.

    --
    Glenn -- http://nevcal.com/
    ===========================
    The best part about procrastination is that you are never bored,
    because you have all kinds of things that you should be doing.
  • John P. Linderman at Jul 7, 2004 at 2:39 pm

    david nicol asked for comments thus:
    On Tue, 2004-06-29 at 18:24, Glenn Linderman wrote:

    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.
    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 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
  • David nicol at Jul 9, 2004 at 2:14 am

    On Wed, 2004-07-07 at 09:39, John P. Linderman wrote:

    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?



    --
    david nicol
    "cat and buttered toast"
  • David nicol at Jul 9, 2004 at 2:51 am

    On Thu, 2004-07-08 at 21:14, david nicol wrote:

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



    --
    david nicol
    "cat and buttered toast"
  • Paul Fenwick at Jul 9, 2004 at 3:09 am
    G'day David / P5Ps,

    david nicol wrote:
    sub Lazy::Sort::TIEARRAY{
    <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>
    sub Lazy::Sort::SHIFT{

    wantarray and eval{Games::Roguelike::Nethack::play()};
    (*chuckles*)
    Finding the hints is the other half of the problem. I've seen several
    identifiable cases so far:
    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

    --
    Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
    Director of Training | Ph: +61 3 9354 6001
    Perl Training Australia | Fax: +61 3 9354 2681
  • John P. Linderman at Jul 9, 2004 at 5:10 pm

    Dave Mitchell replied to david nicol as follows:
    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;
    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
  • Nicholas Clark at Jul 12, 2004 at 7:14 pm

    On Fri, Jul 09, 2004 at 01:10:23PM -0400, John P. Linderman wrote:
    Dave Mitchell replied to david nicol as follows:
    No, that's for optimising away the sort block in

    @x = sort {$b cmp $a } @y;
    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
  • David nicol at Jul 13, 2004 at 2:34 am

    On Mon, 2004-07-12 at 14:14, Nicholas Clark wrote:
    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.
    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




    --
    david nicol
    "People used to be able to read my thoughts, but
    it doesn't appear to work any more. Should I eat less cheese?"
    -- Elizabeth Woods
  • David nicol at Jul 16, 2004 at 3:50 am

    On Mon, 2004-07-12 at 21:34, david nicol wrote:
    On Mon, 2004-07-12 at 14:14, Nicholas Clark wrote:
    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.
    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.
  • Rafael Garcia-Suarez at Jul 21, 2004 at 12:41 pm
    david nicol wrote:
    @@ -577,6 +577,13 @@
    @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} remains stable (new in 5.9)
    +# without overloading
    +@b = sort { $b <=> $a } @input = qw/5first 6first 5second 6second/;
    I assume you meant "cmp" instead of "<=>" here ?
    +ok "@b" , "6first 6second 5first 5second", "optimized {$b cmp $a} without overloading" ;
    +@input = sort {$b <=> $a} @input;
    +ok "@input" , "6first 6second 5first 5second","inline optimized {$b cmp $a} without overloading" ;
    +
    # These two are actually doing string cmp on 0 1 and 2
    @input = &generate1;
    @output = reverse sort @input;
  • Nicholas Clark at Jul 21, 2004 at 1:12 pm

    On Wed, Jul 21, 2004 at 02:37:35PM +0200, Rafael Garcia-Suarez wrote:
    david nicol wrote:
    @@ -577,6 +577,13 @@
    @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} remains stable (new in 5.9)
    +# without overloading
    +@b = sort { $b <=> $a } @input = qw/5first 6first 5second 6second/;
    I assume you meant "cmp" instead of "<=>" here ?
    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
  • Rafael Garcia-Suarez at Jul 21, 2004 at 1:16 pm

    Nicholas Clark wrote:
    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.
    Yes, but in this case what does mean the comment :
    +# test that optimized {$b cmp $a} remains stable (new in 5.9)
    +# without overloading
    However, the patch isn't warnings clean, which given that sort.t runs under
    warnings, isn't going to fly.
    Easily fixable, just like the test count :)
  • Ronald J Kimball at Jul 21, 2004 at 2:09 pm

    On Wed, Jul 21, 2004 at 03:12:53PM +0200, Rafael Garcia-Suarez wrote:
    Nicholas Clark wrote:
    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.
    Yes, but in this case what does mean the comment :
    +# test that optimized {$b cmp $a} remains stable (new in 5.9)
    +# without overloading
    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
  • David nicol at Jul 21, 2004 at 10:10 pm
    --- 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;
  • Rafael Garcia-Suarez at Jul 28, 2004 at 6:51 am

    david nicol wrote:

    --- 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
    Thanks, applied as #23166 to bleadperl.
  • David nicol at Jul 21, 2004 at 9:46 pm

    On Wed, 2004-07-21 at 07:37, Rafael Garcia-Suarez wrote:
    david nicol wrote:
    @@ -577,6 +577,13 @@
    @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} remains stable (new in 5.9)
    +# without overloading
    +@b = sort { $b <=> $a } @input = qw/5first 6first 5second 6second/;
    I assume you meant "cmp" instead of "<=>" here ?
    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.



    --
    david nicol
    "People used to be able to read my thoughts, but
    it doesn't appear to work any more. Should I eat less cheese?"
    -- Elizabeth Woods
  • Nicholas Clark at Jul 13, 2004 at 11:41 am

    On Fri, Jul 09, 2004 at 01:10:23PM -0400, John P. Linderman wrote:

    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
    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
  • Nicholas Clark at Jul 13, 2004 at 7:34 pm

    On Tue, Jul 13, 2004 at 12:41:21PM +0100, Nicholas Clark wrote:
    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 ...
    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
  • David nicol at Jul 16, 2004 at 3:58 am

    On Tue, 2004-07-13 at 14:34, Nicholas Clark wrote:

    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.
  • Nicholas Clark at Jul 21, 2004 at 1:15 pm

    On Thu, Jul 15, 2004 at 10:58:06PM -0500, david nicol wrote:
    On Tue, 2004-07-13 at 14:34, Nicholas Clark wrote:

    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 ....
    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
  • David nicol at Jul 21, 2004 at 9:59 pm

    On Wed, 2004-07-21 at 08:14, Nicholas Clark wrote:
    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?.


    --
    david nicol
    "People used to be able to read my thoughts, but
    it doesn't appear to work any more. Should I eat less cheese?"
    -- Elizabeth Woods
  • Dave Mitchell at Jul 21, 2004 at 10:16 pm

    On Wed, Jul 21, 2004 at 04:58:54PM -0500, david nicol wrote:
    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();

    --
    Standards (n). Battle insignia or tribal totems.
  • David nicol at Jul 21, 2004 at 11:02 pm

    On Wed, 2004-07-21 at 17:16, Dave Mitchell wrote:
    On Wed, Jul 21, 2004 at 04:58:54PM -0500, david nicol wrote:
    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.



    --
    david nicol
    "People used to be able to read my thoughts, but
    it doesn't appear to work any more. Should I eat less cheese?"
    -- Elizabeth Woods
  • Paul Fenwick at Jul 22, 2004 at 1:10 am
    G'day David / P5P,

    david nicol wrote:
    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 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

    --
    Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
    Director of Training | Ph: +61 3 9354 6001
    Perl Training Australia | Fax: +61 3 9354 2681
  • Nicholas Clark at Jul 22, 2004 at 8:46 am

    On Thu, Jul 22, 2004 at 11:10:11AM +1000, Paul Fenwick wrote:

    However I'm not sure if we can do that without losing performance.
    s/performance/sanity/;

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

    Nicholas Clark

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupperl5-porters @
categoriesperl
postedJun 25, '04 at 11:29a
activeJul 28, '04 at 6:51a
posts51
users13
websiteperl.org

People

Translate

site design / logo © 2022 Grokbase