[Numpy-discussion] Inverting argsort(a, axis=0) to obtain column-wise ranks

Alexander Michael lxander.m@gmail....
Thu Sep 9 22:53:07 CDT 2010

I was, of course, just thinking of the incremental work of inverting
the initial argsort, but you are completely correct in pointing out
that the overall complexity is O(n*log(n)) either way. As it turns
out, both approaches run in the same amount of time for my problem.


On Thursday, September 9, 2010, Robert Kern <robert.kern@gmail.com> wrote:
> On Thu, Sep 9, 2010 at 15:59, Alexander Michael <lxander.m@gmail.com> wrote:
>> Clever and concise (and expect that it works), but isn't this less
>> efficient? Sorting is O(n*log(n)), while the code I gave is O(n).
>> Using argsort has the potential to use less memory, though.
> No, the code you gave is also O(n*log(n)) because it uses an
> argsort(). Using two argsort()s won't change the O() complexity. O()
> often tells you very little. Time it with typical values and find out.
> Memory use is often the bottleneck. And sometimes, the real
> performance differences just don't matter.
> --
> Robert Kern
> "I have come to believe that the whole world is an enigma, a harmless
> enigma that is made terrible by our own mad attempt to interpret it as
> though it had an underlying truth."
>   -- Umberto Eco
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion

More information about the NumPy-Discussion mailing list