Find the rank of an element in an array without sorting

user_4745376 0
Viewed 346

Given an array of n element and an element x in the array, is there a fast way to find the rank of x, without sorting it?

As I'm now dealing with a very large array, an algorithm with O(n) time complexity would still be too slow for me to work with which is why I am trying to find other alternative other than sorting.

EDIT:

So right now my algorithm is something like:

for x in list:
    A = x.dot(B) ## return a numpy array
    rank = findRank(a, A) ## find the rank of a in A
    doSomething2(rank)

So here my bottleneck is findRank(), in my current implementation, I first sort the array and then find the rank of the element in the sorted array.

sorting algorithm
1 Answers

Without assuming extra preparations (creating a tree data structure, or sorting), which in itself would require at least O(n) time, there is no way you can hope to determine the rank of a value in an unsorted array in sub linear time: every value in that array potentially plays a role in determining that rank, so you need to inspect all array values.

As the algorithm already has a linear time complexity for the execution of:

A = x.dot(B) ## return a numpy array

...this should not be an issue.

You mention in comments that your implementation of findRank sorts A. This is sub optimal, as it represents a O(nlogn) time complexity.

Instead, just count the number of values in the array that are smaller than the value you need the rank of. That will correspond to the zero-based rank:

rank = np.sum(A < a)
user_54598390
Related