сортировка списка Java с использованием таблицы результатов

Question

У меня есть список из N строк и параллельный список из N баллов. Мне нужно отсортировать строки, используя оценки в таблице. Как мне это сделать?

Мое текущее решение - использовать вспомогательный список индексов, например:

public static List<String> sortByScores(List<String> strings, final List<Float> scores) {
    List<Integer> indices = new ArrayList<Integer>(strings.size());
    for (int i=0; i<strings.size(); i++) 
        indices.add(i);
    Collections.sort(indices, new Comparator<Integer>() {
        @Override public int compare(Integer arg0, Integer arg1) {  // sort in descending order
            return -scores.get(arg0).compareTo(scores.get(arg1));
        }
    });
    List<String> sortedStrings = new ArrayList<String>(strings.size());
    for (int i=0; i<indices.size(); ++i)
        sortedStrings.add(strings.get(indices.get(i)));
    return sortedStrings;
}

Это работает, но кажется неэффективным.

Есть ли лучшее решение?

Answer 1

Псевдокод

// Precondition: length of each list is the same, call it N
let m = new TreeMap<Integer, List<String>>()
for i in 0 .. N-1
    if m.containsKey(scores[i])
        m.get(scores[i]).append(strings[i])
    else
        m.put(scores[i], a new list containing the sole element strings[i])
    end if
end if

for each entry (k, v) in m
    output all the strings in v
end

Нет необходимости сортировать или определять сопоставимые объекты или что-либо еще, потому что древовидная карта уже отсортирована по оценкам!

Answer 2

Я бы создал новый POJO, содержащий String и его Score, и дал бы ему реализовать Comparable

Answer 3

Поместите строку и счет в один класс и реализуйте интерфейс Comparable таким образом, как вы сортируете счет, но вы можете получить доступ к строке после ее сортировки (мне кажется, это наиболее эффективно).

Пример:

public class ScoreClass implements Comparable<ScoreClass>
{
    String myString;
    float score;

    public int compareTo(ScoreClass c)
    {
        return Float.compare(this.score, c.score);
    }
}

Это код, скомпилированный мозгом, поэтому дайте мне знать, если что-то не так.

Answer 4

ОК, я протестировал все методы, которые вы предложили, используя случайный набор строк:

public static void testSortByScores(int count) {
    int length = 4;
    // Create a random array and random scores:
    List<String> strings = new ArrayList<String>(count);
    List<Float> scores = new ArrayList<Float>(count);
    RandomString randomString = new RandomString(length);
    String letters = "abcdefghijklmnopqrstuvwxyz";
    for (int iString=0; iString<count; ++iString) {
        StringBuffer randomStringBuffer = new StringBuffer(length);
        int score = 0;
        for (int iChar=0; iChar<length; ++iChar) {
            int index = (int)(Math.random()*letters.length());
            char c = letters.charAt(index);
            randomStringBuffer.append(c);
            score += index;
        }
        strings.add(randomStringBuffer.toString());
        scores.add((float)score);
    }


    long start = System.currentTimeMillis();
    strings = sortByScoresUsingIndices(strings,scores);
    //strings = sortByScoresUsingClass(strings,scores);
    //strings = sortByScoresUsingTree(strings,scores);
    System.out.println("sorting "+count+" took "+(System.currentTimeMillis()-start)+" ms.");
}

, и вот результаты:

Мой метод - sortByScoresUsingIndices - вероятно, хуже:

sorting 10000 took 52 ms.
sorting 30000 took 140 ms.
sorting 100000 took 396 ms.
sorting 300000 took 382 ms.
sorting 1000000 took 1122 ms.
sorting 3000000 took 5096 ms.

Затем следует метод с использованием ScoreClass, который я реализовал следующим образом:

public static List<String> sortByScoresUsingClass(List<String> strings, final List<Float> scores) {
    List<ScoreClass> list = new ArrayList<ScoreClass>(strings.size());
    for (int i=0; i<strings.size(); i++) {
        ScoreClass sc = new ScoreClass(strings.get(i),scores.get(i));
        list.add(sc);
    }
    Collections.sort(list);
    List<String> sortedStrings = new ArrayList<String>(strings.size());
    for (ScoreClass item: list)
        sortedStrings.add(item.myString);
    return sortedStrings;
}


sorting 10000 took 60 ms.
sorting 30000 took 121 ms.
sorting 100000 took 40 ms.
sorting 300000 took 280 ms.
sorting 1000000 took 648 ms.
sorting 3000000 took 3254 ms.

, и лучшим из них является метод с использованием TreeMap, но мне пришлось изменить его и использоватьсписок, потому что может быть более одной строки с одинаковым счетом:

public static List<String> sortByScoresUsingTree(List<String> strings, final List<Float> scores) {
    TreeMap<Float,List<String>> treeMap = new TreeMap<Float,List<String>>();
    for (int i=0; i<strings.size(); i++) {
        Float key = -scores.get(i);
        if (treeMap.get(key)==null)
            treeMap.put(key, new LinkedList<String>());
        treeMap.get(key).add(strings.get(i));
    }
    List<String> sortedStrings = new ArrayList<String>(strings.size());
    for (List<String> set: treeMap.values()) {
        sortedStrings.addAll(set);
    }
    return sortedStrings;
}

И результаты:

sorting 10000 took 29 ms.
sorting 30000 took 16 ms.
sorting 100000 took 25 ms.
sorting 300000 took 229 ms.
sorting 1000000 took 374 ms.
sorting 3000000 took 2723 ms.