CODEWITHSUNDEEP
javaperformancelistsortingtuples
Jürgen K.
Jürgen K.

Reputation: 3487

Efficient way of sorting a list of tuples in java

Given is a generic datatype whick looks like this: HashMap<EdgeTuple, Double> edgeList where tuple is a class EdgeTuple and Double is a weight which is not important for the task: 

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

So as you can see the tuples are already having the smaller value on first position. What I want to do is to sort the list which final entry order should look like this:

entry 0: [(0,something);some_weight]

entry 1: [(1,something);some_weight]

...

entry n-1: [(last_value,something);some_weight]

So basically what i need to do is to sort the tuples ascending on their first value. I have red the most liked existing answers on this topic but still could not find anything satisfying.

One possible solution is to lean on a comparator, something like this:

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

The comparison of each pair of tuples does not seem quiet efficient. So my question is, do You know any other ways to sort? Maybe some new datatypes which provide a suitable more performant interface for the given task?

Thanks

Upvotes: 3

Views: 8648

Answers (2)

Vlad Bochenin
Vlad Bochenin

Reputation: 3082

You can implements Comparable interface in your 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;
    }
}

and use TreeMap to store presorted map of tuples and don't sort it every time.

Upvotes: 5

marmor
marmor

Reputation: 28239

Your sort is on integers between a pre-defined range, that qualifies for counting sort, which is faster then any generic sort algorithm.

You can use this implementation in Java, and adapt it for your Tuples: http://www.javacodex.com/Sorting/Counting-Sort

Here's a nice explanation + sample code: http://www.geeksforgeeks.org/counting-sort/

Upvotes: 2

Related Questions