Найдите ранг каждого элемента массива double[] лучше в Java

Я написал код для вычисления ранга каждого элемента массива double[] в следующем коде. Например, если у меня есть double массив {3, 1.3, 2, 3}, я нахожу ранг как {2, 0, 1, 2}. Он был рассчитан как

  • 1.3 является наименьшим, поэтому он получил ранг 0.
  • 2 является следующим, поэтому он получил ранг 1.
  • 3 — следующее большее число, поэтому обе тройки получают ранг 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;
}

Этот код дает следующий вывод

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

Что меня интересует, так это лучшая реализация приведенного выше кода. Как это можно сделать лучше?

Редактировать

Этот вопрос требует, чтобы повторяющиеся элементы ранжировались одинаково и непрерывно, то есть {0,1,2,3,...}, без пропуска промежуточного ранга, который отличается от аналогичного, но другого вопроса Как узнать ранг каждого элемента в массиве целых чисел. Этот вопрос требует вывода {3,0,1,3}, если задан ввод {3,1,2,3}. т. е. он по-разному обрабатывает повторяющиеся элементы или ломается при дублировании значений во входных данных. Но это касается и обработки дубликатов, и желаемый результат — {2,0,1,2}.


java arrays sorting rank
person Prabhu    schedule 06.09.2016    source источник
comment
почему вы удалили код из вопроса?   -  person progyammer    schedule 06.09.2016
comment
Как это сделать? Можете ли вы объяснить подробно?   -  person Prabhu    schedule 06.09.2016
comment
@progy_rock, это была опечатка при редактировании форматирования вопроса. Это было исправлено.   -  person Prabhu    schedule 06.09.2016
comment
Вы ищете простоту кода или эффективность?   -  person bilalba    schedule 06.09.2016
comment
Я в первую очередь ищу эффективность. Простота кода может быть еще одним желательным качеством.   -  person Prabhu    schedule 06.09.2016
comment
Проголосуйте за повторное открытие, так как этот вопрос связан с возможными повторяющимися значениями во входном массиве. @Prabhu рекомендует отредактировать, если вы хотите, чтобы он был открыт повторно. К вашему сведению, вы можете использовать TreeSet вместе с Map (для индексов - несколько вызовов indexOf довольно неэффективны).   -  person copeg    schedule 06.09.2016

Ответы (4)


arrow_upward
1
arrow_downward

Я бы пошел на этот подход:

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;
}

Я просто придумал это на лету, поэтому я не могу сказать на 100%, действительно ли это быстрее, чем ваш способ, но я бы сказал, что это выглядит лучше, и вам не нужно зависеть от реализации Java Collections.sort() и списков в целом.

person darkfire000    schedule 06.09.2016
comment
Это O (n ^ 2), определенно не быстрее, чем исходный способ сделать это. - person bilalba; 06.09.2016
comment
Это быстрее на массивах размером менее ~ 7000 - person darkfire000; 06.09.2016
comment
Это решение работает, но кажется более сложным, чем мое решение. - person Prabhu; 06.09.2016

arrow_upward
1
arrow_downward

Если вам нужна эффективность, не ищите индекс списка с list.indexOf() несколько раз. Временная сложность поиска элемента в списке составляет O(n), как объясняется http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

Вы можете использовать Map вместо List. Поиск элемента по ключу в Map использует сложность O(1).

person Community    schedule 07.09.2016

arrow_upward
1
arrow_downward

У вас есть некоторые проблемы с эффективностью в вашем коде. Прежде всего, это использование array.indexOf(). Поиск индекса в массиве стоит O(n). Вместо этого вы можете создать Map вместо массива и использовать x.get(key), чтобы получить связанный с ним ранг. Вы можете определить и получить ключи на карте как:

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

Но использовать Double as key в HashMap можно, но это может быть не очень хорошей идеей, поскольку сравнение Double может иметь проблемы с плавающей запятой. Но основная идея заключается в использовании стоимости O(1).

person Community    schedule 09.09.2016

arrow_upward
1
arrow_downward

Предполагая, что сортировка равна O (n log (n)), тогда один проход O (n) создаст уникальный ранг. Сортировка массива целых чисел I[] в соответствии с x[] с использованием лямбда-сравнения (лямбда-сравнение требует, чтобы I[] имел целочисленный тип). Затем сгенерируйте уникальный ранг R[] в соответствии с I[] и 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;
}
person rcgldr    schedule 07.09.2016