Transform a set of numbers in numpy so that each number gets converted into a number of other numbers which are less than it

Question

Consider a set of numbers:

In [8]: import numpy as np

In [9]: x = np.array([np.random.random() for i in range(10)])

In [10]: x
Out[10]: 
array([ 0.62594394,  0.03255799,  0.7768568 ,  0.03050498,  0.01951657,
        0.04767246,  0.68038553,  0.60036203,  0.3617409 ,  0.80294355])

Now I want to transform this set into another set y in the following way: for every element i in x, the corresponding element j in y would be the number of other elements in x which are less than i. For example, the above given x would look like:

In [25]: y
Out[25]: array([ 6.,  2.,  8.,  1.,  0.,  3.,  7.,  5.,  4.,  9.])

Now, I can do this using simple python loops:

In [16]: for i in range(len(x)):
    ...:     tot = 0
    ...:     for j in range(len(x)):
    ...:         if x[i] > x[j]: tot += 1
    ...:     y[i] = int(tot)

However, when length of x is very large, the code becomes extremely slow. I was wondering if any numpy magic can be brought to rescue. For example, if I had to filter all the elements less than 0.5, I would have simply used a Boolean masking:

In [19]: z = x[x < 0.5]

In [20]: z
Out[20]: array([ 0.03255799,  0.03050498,  0.01951657,  0.04767246,  0.3617409 ])

Can something like this be used so that the same thing could be achieved much faster?

Answer 1

What you actually need to do is get the inverse of the sorting order of your array:

import numpy as np
x = np.random.rand(10)
y = np.empty(x.size,dtype=np.int64)
y[x.argsort()] = np.arange(x.size)

Example run (in ipython):

In [367]: x
Out[367]: 
array([ 0.09139335,  0.29084225,  0.43560987,  0.92334644,  0.09868977,
        0.90202354,  0.80905083,  0.4801967 ,  0.99086213,  0.00933582])

In [368]: y
Out[368]: array([1, 3, 4, 8, 2, 7, 6, 5, 9, 0])

---

Alternatively, if you want to get the number of elements greater than each corresponding element in x, you have to reverse the sorting from ascending to descending. One possible option to do this is to simply swap the construction of the indexing:

y_rev = np.empty(x.size,dtype=np.int64)
y_rev[x.argsort()] = np.arange(x.size)[::-1]

another, as @unutbu suggested in a comment, is to map the original array to the new one:

y_rev = x.size - y - 1

Answer 2

Here's one approach using np.searchsorted -

np.searchsorted(np.sort(x),x)

Another one mostly based on @Andras Deak's solution using argsort() -

x.argsort().argsort()

Sample run -

In [359]: x
Out[359]: 
array([ 0.62594394,  0.03255799,  0.7768568 ,  0.03050498,  0.01951657,
        0.04767246,  0.68038553,  0.60036203,  0.3617409 ,  0.80294355])

In [360]: np.searchsorted(np.sort(x),x)
Out[360]: array([6, 2, 8, 1, 0, 3, 7, 5, 4, 9])

In [361]: x.argsort().argsort()
Out[361]: array([6, 2, 8, 1, 0, 3, 7, 5, 4, 9])