Лучший способ повторить сортировку SortedSet/SortedMap в Java назад

Ответ 1

В Java 1.6 вы можете использовать NavigableSet.

Ответ 2

используйте это, прежде чем заполнить свою карту:

SortedMap sortedMap = new TreeMap(java.util.Collections.reverseOrder());

Ответ 3

Более быстрый способ итерации коллекции - взять ее копию массива. Это можно выполнить итерацией вперед и назад без создания объекта или даже вызова метода. Недостатком является то, что вам необходимо обновлять его, а также свою коллекцию всякий раз, когда она изменяется.

В следующем примере требуется 1,208 нс для итерации более 1000 элементов либо вперед, либо назад.

import java.util.Comparator;
import java.util.Random;
import java.util.NavigableSet;
import java.util.TreeSet;

/*
Average time for iteration of 1000 elements was 1,208 ns
*/
public class Main {
    public static void main(String... args) {
        doPerfTest(true);
        doPerfTest(false);
    }

    private static void doPerfTest(boolean warmup) {
        NavigableSet<MyData> set = new TreeSet<MyData>(new MyCompataror());
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            set.add(new MyData("text-" + random.nextLong(), random.nextInt()));
        }
        MyData[] myDatas = set.toArray(new MyData[set.size()]);
        long start = System.nanoTime();
        final int runs = 500 * 1000;
        for (int i = 0; i < runs; i+=2) {
            // forward iteration
            for (MyData md : myDatas) {

            }
            // reverse iteration
            for (int j = myDatas.length - 1; j >= 0; j--) {
                MyData md = myDatas[j];
            }
        }
        long time = System.nanoTime() - start;
        if (!warmup)
            System.out.printf("Average time for iteration of 1000 elements was %,d ns", time / runs);
    }

    static class MyCompataror implements Comparator<MyData> {
        public int compare(MyData o1, MyData o2) {
            int cmp = o1.text.compareTo(o2.text);
            if (cmp != 0)
                return cmp;
            return o1.value > o2.value ? +1 :
                    o1.value < o2.value ? -1 : 0;
        }
    }

    static class MyData {
        String text;
        int value;

        MyData(String text, int value) {
            this.text = text;
            this.value = value;
        }
    }
}

Теперь замените основной цикл, и среднее время станет 20 493.

// forward iteration
for(Iterator<MyData> it = set.iterator(); it.hasNext();) {
    MyData md = it.next();
}
// reverse iteration
for(Iterator<MyData> it = set.descendingIterator(); it.hasNext();) {
    MyData md = it.next();
}

Теперь сравним это с копированием каждый раз (о чем я говорил не так оптимально, как получение копии только при изменении), время падает до 15,134 нс!

Таким образом, использование NavigableSet может быть медленнее из трех обсуждаемых опций.

Ответ 4

Вы можете определить SortedMap, например TreeMap с пользовательским Comparator, который отменяет порядок сортировки. Если вам нужно итерации в обоих направлениях, возможно, возможно сохранить две копии структуры данных в памяти?