CODEWITHSUNDEEP
javaarraysperformancesorting
Java Nerd
Java Nerd

Reputation: 968

Sorting a List takes a lot of time

I have the following list to sort:

  A 0.53
  B 0.56
  C 0.56
  D 0.98
  E 0.33

Please not that my list may contains 1000's of such type of records. I am Sorting my list and put the sorted list into an array as:

  String str="";
        for(String s: mylist){
            str+=s+",";
        }
        String[] sArr = str.split(",");
        String temp="";
        for(int i=0; i<sArr.length;i++) {
            for(int j= i+1; j<sArr.length;j++){
                if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){
                    temp= sArr[j];
                    sArr[j]= sArr[i];
                    sArr[i]=temp;
                }
            }
        } 

       //sArr now contains the sorted list

The problem is that it is taking too long to get sorted when I have 1000's of records. My Question: Is there any other way out to perform the same task efficiently in less time! or is there something wrong with my way of coding. Can somebody please help me out.

Upvotes: 1

Views: 1181

Answers (5)

Anderson Vieira
Anderson Vieira

Reputation: 9049

There seems to be two problems with the code. The first is this:

String str="";
for(String s: mylist) {
    str+=s+",";
}
String[] sArr = str.split(",");

Here you are, apparently for no reason, joining a collection of strings and then breaking it again into an array. This is made worse by the fact that you are using string concatenation (the + operator).

In Java, strings are immutable objects. This implies that every operation that looks like it is changing a string object is, in fact, creating a new one. Every time you do str+=s+"," you create new objects. Repeating this thousands of times is highly inefficient.

When you need to compose a String like this, you should use a StringBuilder instead. Though, in this case, I don't think it is necessary at all.

If I understood your code correctly, it seems that the list mylist already contains your records in the following format:

["A 0.53", "B 0.56", ...]

If this is the case, you can sort mylist directly.

From here on, I will assume that mylist is a List<String>. If this is not the case and mylist is really a String[], you just need to use Arrays.sort(mylist, comparator) instead of mylist.sort(comparator).

First, you need a method to extract the Double value from the String records, as I suppose you are trying to compare by the numbers as double and not as String.

static Double doubleFromRecord(String record) {
    return Double.valueOf(record.split("\\s")[1]);
}

So, doubleFromRecord("A 0.53") returns 0.53 as a Double.

Now you just need to call sort directly on mylist passing a Comparator that will compare the numbers from different elements:

mylist.sort((r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2)));

And mylist will be sorted.

The comparator:

(r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2))

Just takes two elements from mylist and returns the result of the comparison between their number part.

If you can, I would suggest that you create a class for your records, such as:

class Record {
    final String label;
    final double value;

    Record(String label, double value) {
        this.label = label;
        this.value = value;
    }
 }

And work with a List<Record> instead of a List<String>. So you could easily do:

myRecordList.sort((r1, r2) -> Double.compare(r1.value, r2.value));

Upvotes: 0

Yoda
Yoda

Reputation: 18068

You might want to use TreeSet which is sorted from the beginning. I borrowed small part of DataPoint class from laubed.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<DataPoint> set = new TreeSet<DataPoint>();
        String[] splitS;
        for (String s : YOUR_LIST) {
            splitS = s.split(" ");
            set.add(new DataPoint(splitS[0], Double.parseDouble(splitS[1])));
        }
        DataPoint[] sortedArray = new DataPoint[set.size()];
        set.toArray(sortedArray); //but to be honest there is no reason for using array at this point
    }
}

class DataPoint implements Comparable<DataPoint> {
    public String key;
    public double value;

    public DataPoint(String key, double value) {
        this.key = key;
        this.value = value;
    }

    public int compareTo(DataPoint p){
        return Double.compare(value, p.value);
    }
}

Upvotes: 0

Evan Bechtol
Evan Bechtol

Reputation: 2865

Well, the reason your sort takes so long is because you are not using an efficient sorting algorithm. Typically when you are sorting large quantities of data/records/etc., you want to identify the algorithm or solution that works best with what you have.

Currently, your algorithm appears to have a runtime of O(N^2), which is generally pretty bad, here is why it is O(N^2)

//The outer-loop traverses through the "N" indexes of the array.
for(int i=0; i<sArr.length;i++) {

        //The inner-loop also traverses through the "N" indexes of the array
        for(int j= i+1; j<sArr.length;j++){

            //Most comparisons are able to be done in O(1)
            if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){

                //Assignments are done in O(1)
                temp= sArr[j];
                sArr[j]= sArr[i];
                sArr[i]=temp;
            }
        }

So, we are really concerned with the run-time as N grows sufficiently large. As N grows large, we will get the result: O(N) * O(N) = O(N^2) This is because we are looking at the worst-case. Best-case would be that everything is already sorted and all we have to do is look at each element, which results in O(N) runtime.

If you look at an algorithm like a Quicksort (Or look at Mergesort) , you are sure to see a large improvement due to the fact that the worst-case and best-case (typically) sees a runtime of O(n log n), which is significantly faster than the current method.

I would encourage you to look at implementing better/more efficient sorting algorithms.

I believe that Java implements merge sort in their Arrays library. Arrays.sort()

Upvotes: 0

laubed
laubed

Reputation: 248

Your code relies on a lot of String operations. Strings are immutable in java. For example: if you have String a and String b and you write a += b; java doesnt just add String b to a. It creates a new String instance from string a + String b thereforce resulting in a new String object. Doing that once or twice is not a big deal but your code does heavily rely on that.

My approach would it be to create a new class for your data which implements the Comarable interface:

public class DataPoint implements Comparable<DataPoint>{
    public String key;
    public double value;

    public int compareTo(DataPoint p2){
        if(this.value < p2.value)
             return -1;
        if(this.value == p2.value)
             return 0;
        if(this.value > p2.value)
             return 1;
    }
}

Then build up a List of these DataPoint objects and call Collections.sort(dataPointList);

The dataPointList then contains the values ins sorted order.

Upvotes: 0

Manu
Manu

Reputation: 1485

There's a lot of ways to sort a list of elements. You are using insertion sort, which is a slow sorting method. You could just use:

Arrays.sort(sArr);

which should be faster than your insertion sort.

If you want to know more about sorting algorithms: wikipedia

Upvotes: 3

Related Questions