<br><br><div><span class="gmail_quote">On 6/19/07, <b class="gmail_sendername">Jon Wright</b> <<a href="mailto:wright@esrf.fr">wright@esrf.fr</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Dear numpy experts,<br><br>I see from the docs that there seem to be 3 sorting algorithms for array<br>data (quicksort, mergesort and heapsort). After hearing a rumour about<br>radix sorts and floats I google'd and now I'm wondering about a radix
<br>sort for numpy (and Numeric) scalars? See:<br><br><a href="http://www.stereopsis.com/radix.html">http://www.stereopsis.com/radix.html</a><br><a href="http://en.wikipedia.org/wiki/Radix_sort">http://en.wikipedia.org/wiki/Radix_sort
</a><br><br>The algorithm is apparently a trick where no comparisons are used. A<br>shockingly bad benchmark of a swig wrapped test function below suggests<br>it really is quicker than the array.sort() numpy method for uint8. At
<br>least with >256 element uint8 test arrays (numpy1.0.3, mingw32, winXP),<br>for me, today; of course ymmv.<br><br>With large enough arrays of all of the integer numeric types and also<br>ieee reals, appropriate versions of the radix sort might be able to:
<br>    "... kick major ass in the speed department."<br>[<a href="http://www.cs.berkeley.edu/~jrs/61b/lec/36">http://www.cs.berkeley.edu/~jrs/61b/lec/36</a>]<br><br>Have these sorts already been implemented in scipy? Can someone share
<br>some expertise in this area? There is a problem about the sorting not<br>being done in-place (eg: better for argsort than sort). I see there is a<br>lexsort, but it is not 100% obvious to me how to use that to sort<br>
scalars, especially ieee floats. If numpy is a library for handling big<br>chunks of numbers with knowable binary representations, I guess there<br>might be some general interest in having this radix sort compiled for<br>
the platforms where it works?<br><br>Thanks for any opinions,<br><br>Jon<br>---</blockquote><div><br>Straight radix sort might be an interesting option for some things.  However, its performance can depend on whether the input data is random or not and it takes up more space than merge sort. Other potential drawbacks arise from the bit twiddling needed for signed numbers and floats, the former solved by converting to offset binary numbers (complement the sign bit), and the latter in the way your links indicate, but both leading to a proliferation of special cases. Maintaining byte order and byte addressing portability between cpu architectures might also require masking and shifting that will add computational expense and may lead to more special cases for extended precision floats and so on. That said, I would be curious to see how it works out if you want to give it a try.
<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">==setup.py==<br>from distutils.core import setup, Extension<br>e = Extension("_sort_radix_uint8",sources=["radix_wrap.c"])
<br>setup(ext_modules=[e])<br><br>==radix.i==<br>%module sort_radix_uint8<br>%{<br>#define SWIG_FILE_WITH_INIT<br>void sort_radix_uint8(unsigned char * ar, int len){<br>     int hits[256];<br>     int i, j;<br>     for(i=0;i<256;i++) hits[i]=0;
<br>     for(i=0;i<len;i++) hits[(int)ar[i]]+=1;<br>     i=0; j=0;<br>     while(i<256){<br>         while(hits[i]>0){<br>             /* shortcut for uint8 */<br>             ar[j++] = (unsigned char) i;<br>             hits[i]--;
<br>         }<br>         i++;<br>     }<br>}<br>%}<br>%init %{<br>import_array();<br>%}<br>%include "numpy.i"<br>%apply (unsigned char* INPLACE_ARRAY1, int DIM1) { (unsigned char * ar,<br>int len)}<br>void sort_radix_uint8(unsigned char * ar, int len);
</blockquote><div><br>You can't use this method for longer keys, you will need to copy over the whole number. Sedgewick's <span style="font-style: italic;">Algorithms in C++</span> has a discussion and implementation of the radix sort. And, of course, Knuth also.
<br><br>Chuck<br></div><br></div><br>