SORTf_DESC

--001a113d51689e4fc20554722ae9
Content-Type: text/plain; charset="UTF-8"

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

--001a113d51689e4fc20554722ae9
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">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&#39;s not mentioned =
in &quot;perldoc=C2=A0sort&quot;), the original comparison function, which =
will have been squirreled away in PL_sort_RealCmp, is replaced by<div><div>=
<br></div></div><blockquote style=3D"margin:0px 0px 0px 40px;border:none;pa=
dding:0px"><div><div><div>static I32</div></div></div><div><div><div>cmp_de=
sc(pTHX_ gptr const a, gptr const b)</div></div></div><div><div><div>{</div=
></div></div><div><div><div>=C2=A0 =C2=A0 return -PL_sort_RealCmp(aTHX_ a, =
b);</div></div></div><div><div><div>}</div></div></div></blockquote><div><d=
iv><br></div></div><div>According to &quot;perldoc -f sort&quot;, a user-su=
pplied comparison must return</div><div><br></div><blockquote style=3D"marg=
in:0px 0px 0px 40px;border:none;padding:0px"><div><div>an integer less than=
, equal to, or greater than 0, depending on how the elements of the list ar=
e to be ordered. (The &quot;&lt;=3D&gt;&quot; and &quot;cmp&quot; operators=
 are extremely useful in such routines.)</div></div></blockquote><br><div>I=
 am troubled by two things. One is that with 64 bit integers becoming incre=
asingly common, returning any integer that doesn&#39;t fit in an I32 is lik=
ely to raise havoc. I guess this can be fixed by changing &quot;perldoc -f&=
quot; to insist that the integer returned be &quot;a 32-bit signed integer&=
quot;. A more subtle concern is that the maximum negative 32-bit signed int=
eger has no positive counterpart, so negating it doesn&#39;t change the sig=
n. More documentation changes to &quot;perldoc -f&quot;?</div><div><br></di=
v><div>For what it&#39;s worth, as I chug along on destabilizing mergesort,=
 I have found it useful to &quot;normalize&quot; what is returned by the co=
mparison so it returns only -1, 0 and 1 (just -1 and 1 when a stable sort i=
s demanded). So I could (although I don&#39;t...yet) use the return value t=
o index into an array of size 3. And I can determine &quot;compatibility of=
 merging adjacent runs with senses s1 and s2, respectively&quot; with</div>=
<div><br></div><blockquote style=3D"margin:0 0 0 40px;border:none;padding:0=
px"><div>if (s1*s2 &gt;=3D 0) { /* candidate for merging */ }</div></blockq=
uote><div><br></div><div>I wouldn&#39;t dare take the product of two arbitr=
ary integers without worrying about overflow, but -1, 0 and 1 are well beha=
ved. This relatively simple test swallows up a lot of special cases. The on=
ly failure case is where s1 and and s2 are both non-zero with opposite sign=
s, indicating one run is strictly increasing and the other strictly decreas=
ing, so there is no hope of &quot;bridging them together to form a single r=
un&quot;.</div></div>

--001a113d51689e4fc20554722ae9--
0
jpl
7/16/2017 4:56:41 PM
perl.perl5.porters 46478 articles. 0 followers. Follow

0 Replies
29 Views

Similar Articles

[PageSpeed] 20

Reply: