<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hey guys,<div><br></div><div>Thanks for all the suggestions. They seem already relatively involved, but I'll have a look at the table implementation. That seems to be the easiest of them all.</div><div><br></div><div>Cheers</div><div>    Wolfgang </div><div><br><div><div>On 2012-05-03, at 9:39 AM, Charles R Harris wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><br><br><div class="gmail_quote">On Thu, May 3, 2012 at 3:41 AM, Nathaniel Smith <span dir="ltr"><<a href="mailto:njs@pobox.com" target="_blank">njs@pobox.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Thu, May 3, 2012 at 4:44 AM, Charles R Harris<br>
<<a href="mailto:charlesr.harris@gmail.com">charlesr.harris@gmail.com</a>> wrote:<br>
><br>
><br>
> On Wed, May 2, 2012 at 3:20 PM, Nathaniel Smith <<a href="mailto:njs@pobox.com">njs@pobox.com</a>> wrote:<br>
</div><div class="im">>> This coordinate format is also what's used by the MATLAB Tensor<br>
>> Toolbox. They have a paper justifying this choice and describing some<br>
>> tricks for how to work with them:<br>
>>  <a href="http://epubs.siam.org/sisc/resource/1/sjoce3/v30/i1/p205_s1" target="_blank">http://epubs.siam.org/sisc/resource/1/sjoce3/v30/i1/p205_s1</a><br>
>> (Spoiler: you use a lot of sort operations. Conveniently, timsort<br>
>> appears to be perfectly adapted for their algorithmic requirements.)<br>
>><br>
><br>
> Timsort probably isn't the best choice here, it is optimized for python<br>
> lists of python objects where there is at least one level of indirection and<br>
> compares are expensive, even more expensive for compound objects. If the<br>
> coordinates are stored in numpy structured arrays an ordinary sort is likely<br>
> to be faster. Lexsort might even be faster as it could access aligned<br>
> integer data and not have to move lists of indexes around.<br>
<br>
</div>To be clear, I don't mean Timsort-the-implementation, I mean<br>
Timsort-the-algorithm (which is now also the default sorting algorithm<br>
in Java). That said, it may well be optimized for expensive compares<br>
and something like a radix sort would be even better.<br>
<br></blockquote><div><br>Java uses Timsort for sorting object arrays (pointers) and dual pivot quicksort for sorting arrays of native types, ints and such. Timsort is very good for almost sorted arrays and the mixed algorithms are becoming popular, i.e., introsort and recent updates to the dual pivot sort that also look for runs. One of the reasons compares can be expensive for arrays of pointers to objects is that the objects can be located all over memory, which blows the cache.<br>
<br>There are also a few mods to the numpy quicksort that might speed things up a bit more for common cases where there are a lot of repeated elements.<br><br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">

In these sparse tensor algorithms, we often need to sort by one<br>
coordinate axis, and then sort by another (a "corner turn"). The<br>
reason Timsort seems appealing is that (1) it goes faster than O(n log<br>
n) when there is existing structure in the data being sorted, (2)<br>
because it's a stable sort, sorting on one axis then sorting on<br>
another will leave lots of that structure behind to be exploited<br>
later. So one can expect it to hit its happy case relatively often.<br>
<div class="HOEnZb"><div class="h5"><br></div></div></blockquote><div><br>Yes, that's why we have mergesort. An optimistic version making some use of runs might make it faster. We do have object arrays and no type specialized sort for them, so bringing Timsort in for those could be useful.<br>
<br>Chuck  <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="HOEnZb"><div class="h5">
<br>
</div></div></blockquote></div><br>
_______________________________________________<br>NumPy-Discussion mailing list<br><a href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br>http://mail.scipy.org/mailman/listinfo/numpy-discussion<br></blockquote></div><br></div></body></html>