CODEWITHSUNDEEP
javalistsorting
bhavs
bhavs

Reputation: 2291

fastest way to sort a list in Java

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?

Upvotes: 7

Views: 48454

Answers (7)

worker105
worker105

Reputation: 1

First,Your serverDataRate variable type is int. But getter method return type is double. When the comparator is working, all getServerDataRate method converts the field to a londer data format. If your getter method return type same as the field type then the compare time will be shorter. Second, No need to use if(), in compare method if your mission is simple operation. Just use subtraction. Like this:


the getter:
    public int getServerDataRate() {
        return serverDataRate;
    }

in comparator:
return o1.getServerDataRate()-o2.getServerDataRate(); // from smallest to largest value
or
return o2.getServerDataRate()-o1.getServerDataRate(); // from largest to smallest value

Upvotes: 0

user unknown
user unknown

Reputation: 36229

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.

Upvotes: 2

Peter Lawrey
Peter Lawrey

Reputation: 533472

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.

Upvotes: 12

ARRG
ARRG

Reputation: 2486

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.

Upvotes: 1

Sabya
Sabya

Reputation: 1429

You can use data structure to accomplish the sorting in faster way.

A BST (Binary Search Tree ) or TRIE will help u sort huge data in faster way.

They will require a bit lengthy code, but will help u in log run if the data set is large.

Upvotes: 0

pcalcao
pcalcao

Reputation: 15975

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).

Upvotes: 4

Martijn Courteaux
Martijn Courteaux

Reputation: 68847

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");

Upvotes: 1

Related Questions