--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's not mentioned = in "perldoc=C2=A0sort"), 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 "perldoc -f sort", 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 "<=3D>" and "cmp" 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't fit in an I32 is lik= ely to raise havoc. I guess this can be fixed by changing "perldoc -f&= quot; to insist that the integer returned be "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't change the sig= n. More documentation changes to "perldoc -f"?</div><div><br></di= v><div>For what it's worth, as I chug along on destabilizing mergesort,= I have found it useful to "normalize" 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't...yet) use the return value t= o index into an array of size 3. And I can determine "compatibility of= merging adjacent runs with senses s1 and s2, respectively" with</div>= <div><br></div><blockquote style=3D"margin:0 0 0 40px;border:none;padding:0= px"><div>if (s1*s2 >=3D 0) { /* candidate for merging */ }</div></blockq= uote><div><br></div><div>I wouldn'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 "bridging them together to form a single r= un".</div></div> --001a113d51689e4fc20554722ae9--

0 |

7/16/2017 4:56:41 PM