A quick 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 use the above code to sort items in descending order based on serverDataRate. Here, the sample set is pretty small, assuming I have a wider set of samples from 100 items in the list, and the code should run every 5-10 seconds. Is this the fastest way to sort the list, or is there a faster method that I don't know about?

Answer 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 he prints

 Sorting 1,000,000 took 0.438 seconds 

This is a little faster;)

BTW: I changed the double fields to int .

Answer 2

100 elements are not a big set if your comparison step is really heavy (not like it). 100 items will be sorted very quickly in any slightly modern machine.

Speaking, I think your approach is pretty close to the standard, and I would not have to worry about optimizing it if you really don't need it.

Early optimization is the father of many screws (assumptions are the mother).

Answer 3

You do not need to use method calls in the class, even if this field was private, which is not always known - private restricts access to the class, and not to the object.

Since your method returns nothing but returns an attribute, you can directly use the attribute:

 @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 can optimize the function call, and in the range of 100 elements it is unlikely to be measurable.

Your method returns double - can you explain why?

With ints, you can simply do:

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

But consider the most extreme possible values ​​for int over- and underrun questions.

Answer 4

This not normal. Check your timing.

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

Answer 5

Given that you don't sort often, speed should not be a problem. Even with thousands of items, Collections.sort is really fast.

Have you tried your application to find out if the problem was a problem? Premature optimization is not a good idea :)

Use caution with your code: if you don’t make sure that all sorts do not have dataRates during sorting, you may get inconsistent results! You must synchronize your methods so that dataRates does not change until the entire list is sorted.

Answer 6

You can use the data structure to speed up sorting.

A BST (Binary Search Tree) or TRIE helps you sort huge data faster.

They will require a bit of long code, but will help to run in the log if the data set is large.

Answer 7

First, your serverDataRate variable type is int. But the return type of the getter method is double. When the comparator is running, the entire getServerDataRate method converts the field to a more convenient data format. If your getter method returns a type similar to the type of the field, the comparison time will be shorter. Secondly, there is no need to use if () in the comparison method if your mission is a 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