fastest way to sort a list in Java

Question

I have the following code in Java:

   public  class ServerInfo {
    int serverId;
    int serverDataRate;
    public ServerInfo(int serverId, int serverDataRate) {
        this.serverId = serverId;
        this.serverDataRate = serverDataRate;
    }
    public int getServerId() {
        return serverId;
    }
    public double getServerDataRate() {
        return serverDataRate;
    }
       public String toString(){
            return serverId + ":" + serverDataRate;
        }
    }    

    public class ServerInfoComparator implements Comparator<ServerInfo> {

    @Override
    public int compare(ServerInfo o1, ServerInfo o2) {
          double datarate1=o1.getServerDataRate();
          double datarate2=o2.getServerDataRate();

          if(datarate1>datarate2)
              return -1;
          else if(datarate1<datarate2)
              return +1;
          else
              return 0;
    }           
}

   public class Sample {
    List<ServerInfo> listOfServers= new ArrayList<ServerInfo>();

    public void insertIntoList(){

        listOfServers.add( new ServerInfo(0,256));
        listOfServers.add( new ServerInfo(1,270));
        listOfServers.add( new ServerInfo(2,256));
        listOfServers.add( new ServerInfo(3,290));
        listOfServers.add( new ServerInfo(4,300));
        listOfServers.add( new ServerInfo(5,300));
        listOfServers.add( new ServerInfo(6,256));
        listOfServers.add( new ServerInfo(7,265));
        listOfServers.add( new ServerInfo(8,289));
        listOfServers.add( new ServerInfo(9,310));  
    }

    public static void main( String[] args){
        Sample s = new Sample();
        s.insertIntoList();
        ServerInfoComparator com  = new ServerInfoComparator();
        Collections.sort(s.listOfServers,com);

        for( ServerInfo server: s.listOfServers){
            System.out.println(server);
        }           
    }
}

I am using the above code to sort the elements in descending order based on the serverDataRate. Here the sample set is quite small supposing I have a larger sample set of 100 elements in the list and the code had to be executed every 5-10 seconds. Is this the fastest way to sort the list or is there a faster method I am not aware of?

Solution 1

I changed your test

private final List<ServerInfo> listOfServers = new ArrayList<ServerInfo>();

public void insertIntoList() {
    for (int i = 0; i < 1000000; i++)
        listOfServers.add(new ServerInfo(i, (int) (200 + Math.random() * 200)));
}

public static void main(String[] args) {
    MyApp s = new MyApp();
    s.insertIntoList();
    ServerInfoComparator com = new ServerInfoComparator();
    long start = System.nanoTime();
    Collections.sort(s.listOfServers, com);
    long time = System.nanoTime() - start;
    System.out.printf("Sorting %,d took %.3f seconds%n", s.listOfServers.size(), time/1e9);

    for (ServerInfo server : s.listOfServers) {
//    System.out.println(server);
    }
}

and it prints

Sorting 1,000,000 took 0.438 seconds

That's quite a bit faster ;)

BTW: I changed the double fields to be int.

Solution 2

100 elements isn't a large set unless your comparison step is really heavy (doesn't seem like it). 100 elements will get sorted extremely fast in any slightly modern machine.

That being said, I think your approach is pretty close to standard, and I wouldn't worry about trying to optimize it unless you really end up needing it.

Early optimization is the father of many screw ups (assumptions being the mother).

Solution 3

You don't need to use method calls in the class, even if the field was private which isn't always known - private restricts the access to a class, not to an object.

Since your method does nothing but return the attribute, you can use the attribute directly:

@Override
public int compare(ServerInfo o1, ServerInfo o2) {
/*
      double datarate1=o1.getServerDataRate ();
      double datarate2=o2.getServerDataRate ();
*/
      double datarate1=o1.serverDataRate;
      double datarate2=o2.serverDataRate;

      if (datarate1 > datarate2)
          return -1;
      else if ( datarate1 < datarate2)
          return +1;
      else
          return 0;
}           

But the JVM might optimize the function call, and in the range of 100 elements, it will hardly be measurable.

Your method returns a double - can you explain why?

With ints, you could just do:

@Override
public int compare (ServerInfo o1, ServerInfo o2) {
      return o2.serverDataRate - o1.serverDataRate;
}           

But consider the extremest possible values for questions of int over- and underrun.

Solution 4

This isn't normal. Check your way of timing it.

long start = System.nanoTime();

// Sort here

long time = System.nanoTime() - start;
System.out.println(time / 1000000L + " Milliseconds");

Solution 5

Given that you are not sorting often, speed shouldn't be an issue. Even with thousands of items, Collections.sort is very fast.

Have you tried your application to see whether speed was an issue ? Premature optimisation is not a good idea :)

Be wary of one thing about your code: unless you make sure that the dataRates of all servers do not change during sorting, you may get inconsistent results ! You should synchronize your methods so that datarates don't change until the whole list is sorted.

View more solutions