develooper Front page | perl.perl5.porters | Postings from July 2017

SORTf_DESC

Thread Next
From:
John P. Linderman
Date:
July 16, 2017 16:56
Subject:
SORTf_DESC
Message ID:
CAC0cEp9MRw-eq8MfdRvronowp73sdpSvoO54NAJ2c1CwCfvvKQ@mail.gmail.com
When the SORTf_DESC flag is on in pp_sort.c (I guess this flag is turned on
by some higher level perl code... it's not mentioned in "perldoc sort"),
the original comparison function, which will have been squirreled away in
PL_sort_RealCmp, is replaced by

static I32
cmp_desc(pTHX_ gptr const a, gptr const b)
{
    return -PL_sort_RealCmp(aTHX_ a, b);
}


According to "perldoc -f sort", a user-supplied comparison must return

an integer less than, equal to, or greater than 0, depending on how the
elements of the list are to be ordered. (The "<=>" and "cmp" operators are
extremely useful in such routines.)


I am troubled by two things. One is that with 64 bit integers becoming
increasingly common, returning any integer that doesn't fit in an I32 is
likely to raise havoc. I guess this can be fixed by changing "perldoc -f"
to insist that the integer returned be "a 32-bit signed integer". A more
subtle concern is that the maximum negative 32-bit signed integer has no
positive counterpart, so negating it doesn't change the sign. More
documentation changes to "perldoc -f"?

For what it's worth, as I chug along on destabilizing mergesort, I have
found it useful to "normalize" what is returned by the comparison so it
returns only -1, 0 and 1 (just -1 and 1 when a stable sort is demanded). So
I could (although I don't...yet) use the return value to index into an
array of size 3. And I can determine "compatibility of merging adjacent
runs with senses s1 and s2, respectively" with

if (s1*s2 >= 0) { /* candidate for merging */ }


I wouldn't dare take the product of two arbitrary integers without worrying
about overflow, but -1, 0 and 1 are well behaved. This relatively simple
test swallows up a lot of special cases. The only failure case is where s1
and and s2 are both non-zero with opposite signs, indicating one run is
strictly increasing and the other strictly decreasing, so there is no hope
of "bridging them together to form a single run".

Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About