Эффективный способ сортировки списка кортежей в Java

Question

Учитывая это общий тип данных Уик выглядит следующим образом: HashMap<EdgeTuple, Double> edgeList где кортеж является классом EdgeTuple и двойной это вес, который не является важным для выполнения этой задачи:

class EdgeTuple{ 
    int label1; 
    int label2; 
    public EdgeTuple(int label1, int label2){ 
     int min = Math.min(label1, label2); 
     int max = Math.max(label1, label2); 
     this.label1 = min; 
     this.label2 = max; 
    } 
} 

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

вход 0: [(0, то); some_weight]

вход 1: [(1, то); some_weight ]

...

запись п-1: [(last_value, что-то); some_weight]

Поэтому в основном то, что мне нужно сделать, это сортировать кортежи по возрастанию по их первому значению. У меня есть красные самые любимые ответы на эту тему, но до сих пор не удалось найти ничего приятного.

Одно из возможных решений опираться на компаратор, что-то вроде этого:

Comparator<Tuple> myComparator = new Comparator<Tuple>() { 
    public int compare(Tuple t1, Tuple t2) { 
     //the comparison rules go here 
    } 
}; 
Collections.sort(tupleList, myComparator); 

Сопоставление каждой пары кортежей не кажется тихой эффективным. Итак, мой вопрос: знаете ли вы какие-либо другие способы сортировки? Может быть, некоторые новые типы данных, которые обеспечивают подходящий интерфейс для выполнения данной задачи?

Благодаря

Answer 1

Вы можете реализуете Comparable интерфейса в EdgeTuple:

public static class EdgeTuple implements Comparable<EdgeTuple> { 
    int label1; 
    int label2; 
    public EdgeTuple(int label1, int label2){ 
     int min = Math.min(label1, label2); 
     int max = Math.max(label1, label2); 
     this.label1 = min; 
     this.label2 = max; 
    } 


    @Override 
    public int compareTo(EdgeTuple o) { 
     return this.label1 - o.label1; 
    } 
} 

и использовать TreeMap хранить карту предварительно отсортированные кортежи и не сортировать его каждый раз.

Answer 2

Ваша сортировка основана на целых числах между заранее определенным диапазоном, который соответствует counting sort, который быстрее, чем любой общий алгоритм сортировки.

Вы можете использовать эту реализацию в Java и адаптировать его для Tuples: http://www.javacodex.com/Sorting/Counting-Sort

Вот хороший объяснение + пример кода: http://www.geeksforgeeks.org/counting-sort/