Find the rank of each element of double[] array in better way in Java

Question

I have written code to calculate the rank of each element of a double[] array in the following code. For an example, if I have double array {3, 1.3, 2, 3} then I find the rank as {2, 0, 1, 2}. It has been calculated as

1.3 is least so it got rank 0.
2 is the next, so it got rank 1.
3 is the next bigger number, so both 3's get rank 2.

public static void main() {
    double[] x = {3, 1.3, 2, 3};
    System.out.println(Arrays.toString(x) + " - original");
    System.out.println("[2, 0, 1, 2] - should be");
    System.out.println(Arrays.toString(findRank(x)) + " - our rank");
}

private static int[] findRank(double[] x){
    List<Double> lst = new ArrayList<Double>();
    int[] rank=new int[x.length]; // maximum length for already unique array
    for(double d:x)
        if (lst.indexOf(d) == -1) //only unique elements in list
            lst.add(d);

    Collections.sort(lst);
    for(int i=0;i<x.length;i++) {
        rank[i]=lst.indexOf(x[i]);
    }
    return rank;
}

This code gives the following output

[3.0, 1.3, 2.0, 3.0] - original
[2, 0, 1, 2] - should be
[2, 0, 1, 2] - our rank

What I am interested in is the better implementation of above code. How can it be done in a better way?

Edit

This question asks for duplicate elements to be ranked similarly and continuously i.e. {0,1,2,3,...} without skipping the intermediate rank, which is different from similar but different question How to find what is the rank of each element in an integer array. That question requires output {3,0,1,3} if the input {3,1,2,3} is given. i.e. it handles duplicate elements differently, or it breaks on duplicate values in input. But this is about handling duplicates too and the desired output is {2,0,1,2}.

@progy_rock, it was a typo while editing the formatting of question. It has been corrected. — Prabhu, Sep 06 '16 at 17:02
I am primarily looking for efficiency. Code simplicity can be another desirable quality. — Prabhu, Sep 06 '16 at 17:06
Vote for reopen as this question involved possible duplicate values in input array @Prabhu recommend editing if you want it reopened. FYI you can use a TreeSet together with a Map (for indeces - multiple indexOf calls is pretty inneficient). — copeg, Sep 06 '16 at 17:45

score 1 · Answer 1 · answered Sep 06 '16 at 17:08

1

I would go for this approach:

public static int[] findRank(double[] inp) {
    int[] outp = new int[inp.length];
    for(int i = 0; i < inp.length; i++) {
        for(int k = 0; k < inp.length; k++) {
            if(inp[k] < inp[i]) outp[i]++;
        }
    }
    return outp;
}

I just came up with this on the fly, so I can't tell 100% if it is realy faster than your way, but I would say it looks nicer and you don't need to depend one the java implementations of Collections.sort() and Lists in general.

answered Sep 06 '16 at 17:08

darkfire000

11
3

1

This is O(n^2), definitely not faster than the original way of doing this. – bilalba Sep 06 '16 at 17:09
It is faster on arrays with a size of less than ~7000 – darkfire000 Sep 06 '16 at 17:16
This solution works, but seems to be more time complex than my solution. – Prabhu Sep 06 '16 at 18:09

score 1 · Answer 2 · answered Sep 07 '16 at 04:58

If you are looking for efficiency, don't go for finding the index of list with list.indexOf() multiple times. The time complexity of finding element in a list is O(n) as explained by http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

You can use Map instead of List. Finding the element by key in Map uses O(1) complexity.

rcgldr · Answer 3 · 2016-09-09T09:00:24.020

Assuming sort is O(n log(n)), then a single O(n) pass will generate unique rank. Sort array of Integers I[] according to x[] using lambda compare (lambda compare requires I[] to be of type Integer). Then generate unique rank R[] according to I[] and x[].

// return unique rank
private static int[] findRank(double[] x){
    int [] R = new int[x.length];
    if(x.length == 0)return R;
    Integer [] I = new Integer[x.length];
    for(int i = 0; i < x.length; i++)
        I[i] = i;
    Arrays.sort(I, (i0, i1) -> (int) Math.signum(x[i0]-x[i1]));
    int j = 0;
    for(int i = 0; i < x.length; i++){
        if(x[I[i]] != x[I[j]])
            j = i;
        R[I[i]] = j;
    }
    return R;
}

score 1 · Answer 4 · answered Sep 09 '16 at 04:41

You have some issues with efficiency in your code. The first and foremost one is the use of array.indexOf(). Finding index in array is costly O(n). You can instead create a Map in place of array, and use x.get(key) to get the rank associated with that. You can define and get keys in map as:

Map<Double,Integer> x = new HashMap<Double, Integer>();
x.put(3.5,0);
x.put(2.0,1);
x.put(4.1,2);
//.... and put following in loop
y=x.get(2.0); //y=1

But using Double as key in HashMap can be done, but it might not be very good idea as Double comparison might have floating point issues. But the basic idea is to use O(1) cost.

Find the rank of each element of double[] array in better way in Java

4 Answers4