<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Feb 17, 2014 at 11:32 AM, Julian Taylor <span dir="ltr"><<a href="mailto:jtaylor.debian@googlemail.com" target="_blank">jtaylor.debian@googlemail.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="HOEnZb"><div class="h5">On 17.02.2014 15:18, Francesc Alted wrote:<br>
> On 2/17/14, 1:08 AM, <a href="mailto:josef.pktd@gmail.com">josef.pktd@gmail.com</a> wrote:<br>
>> On Sun, Feb 16, 2014 at 6:12 PM, Daπid <<a href="mailto:davidmenhur@gmail.com">davidmenhur@gmail.com</a>> wrote:<br>
>>> On 16 February 2014 23:43, <<a href="mailto:josef.pktd@gmail.com">josef.pktd@gmail.com</a>> wrote:<br>
>>>> What's the fastest argsort for a 1d array with around 28 Million<br>
>>>> elements, roughly uniformly distributed, random order?<br>
>>><br>
>>> On numpy latest version:<br>
>>><br>
>>> for kind in ['quicksort', 'mergesort', 'heapsort']:<br>
>>>      print kind<br>
>>>      %timeit np.sort(data, kind=kind)<br>
>>>      %timeit np.argsort(data, kind=kind)<br>
>>><br>
>>><br>
>>> quicksort<br>
>>> 1 loops, best of 3: 3.55 s per loop<br>
>>> 1 loops, best of 3: 10.3 s per loop<br>
>>> mergesort<br>
>>> 1 loops, best of 3: 4.84 s per loop<br>
>>> 1 loops, best of 3: 9.49 s per loop<br>
>>> heapsort<br>
>>> 1 loops, best of 3: 12.1 s per loop<br>
>>> 1 loops, best of 3: 39.3 s per loop<br>
>>><br>
>>><br>
>>> It looks quicksort is quicker sorting, but mergesort is marginally faster<br>
>>> sorting args. The diference is slim, but upon repetition, it remains<br>
>>> significant.<br>
>>><br>
>>> Why is that? Probably part of the reason is what Eelco said, and part is<br>
>>> that in sort comparison are done accessing the array elements directly, but<br>
>>> in argsort you have to index the array, introducing some overhead.<br>
>> Thanks, both.<br>
>><br>
>> I also gain a second with mergesort.<br>
>><br>
>> matlab would be nicer in my case, it returns both.<br>
>> I still need to use the argsort to index into the array to also get<br>
>> the sorted array.<br>
><br>
> Many years ago I needed something similar, so I made some functions for<br>
> sorting and argsorting in one single shot.  Maybe you want to reuse<br>
> them.  Here it is an example of the C implementation:<br>
><br>
> <a href="https://github.com/PyTables/PyTables/blob/develop/src/idx-opt.c#L619" target="_blank">https://github.com/PyTables/PyTables/blob/develop/src/idx-opt.c#L619</a><br>
><br>
> and here the Cython wrapper for all of them:<br>
><br>
> <a href="https://github.com/PyTables/PyTables/blob/develop/tables/indexesextension.pyx#L129" target="_blank">https://github.com/PyTables/PyTables/blob/develop/tables/indexesextension.pyx#L129</a><br>
><br>
> Francesc<br>
><br>
<br>
</div></div>that doesn't really make a big difference if the data is randomly<br>
distributed.<br>
the sorting operation is normally much more expensive than latter<br>
applying the indices:<br>
<br>
In [1]: d = np.arange(10000000)<br>
<br>
In [2]: np.random.shuffle(d)<br>
<br>
In [3]: %timeit  np.argsort(d)<br>
1 loops, best of 3: 1.99 s per loop<br>
<br>
In [4]: idx = np.argsort(d)<br>
<br>
In [5]: %timeit d[idx]<br>
1 loops, best of 3: 213 ms per loop<br>
<br>
<br>
<br>
But if your data is not random it can make a difference as even<br>
quicksort can be a lot faster then.<br>
timsort would be a nice addition to numpy, it performs very well for<br>
partially sorted data. Unfortunately its quite complicated to implement.<br></blockquote><div><br></div><div>Quicksort and shellsort gain speed by having simple inner loops. I have the impression that timsort is optimal when compares and memory access are expensive, but I haven't seen any benchmarks for native types in contiguous memory.<br>
<br></div><div>Chuck <br></div><br></div></div></div>