manera más rápida para ordenar una lista en Java

Question

tengo el siguiente código en 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); 
     }   
    } 
} 

Estoy utilizando el código anterior para ordenar los elementos en orden basado en la serverDataRate descendente. Aquí el conjunto de muestras es bastante pequeño, suponiendo que tengo un conjunto de muestra más grande de 100 elementos en la lista y el código tuvo que ejecutarse cada 5-10 segundos. ¿Es esta la forma más rápida de ordenar la lista o hay un método más rápido del que no soy consciente?

Answer 1

Me cambió su prueba

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

e imprime

Sorting 1,000,000 took 0.438 seconds 

Eso es un poco más rápido;)

BTW: He cambiado los campos double ser int.

Answer 2

Esto no es normal. Verifica tu forma de sincronizarlo.

long start = System.nanoTime(); 

// Sort here 

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

Answer 3

100 elementos no es un conjunto grande a menos que su paso de comparación sea muy pesado (no lo parece). 100 elementos serán ordenados extremadamente rápido en cualquier máquina ligeramente moderna.

Habiendo dicho eso, creo que su enfoque es bastante similar al estándar, y no me preocuparía tratar de optimizarlo a menos que realmente lo necesite.

La optimización temprana es el padre de muchos errores (las suposiciones son la madre).

Answer 4

Puede usar la estructura de datos para realizar la clasificación de forma más rápida.

Un BST (árbol de búsqueda binaria) o TRIE le ayudará a ordenar grandes cantidades de datos de una manera más rápida.

Necesitarán un código largo pero le ayudará a iniciar sesión si el conjunto de datos es grande.

Answer 5

Dado que no está ordenando con frecuencia, la velocidad no debería ser un problema. Incluso con miles de artículos, Collections.sort es muy rápido.

¿Has probado tu aplicación para ver si la velocidad era un problema? La optimización prematura no es una buena idea :)

Tenga cuidado con una cosa sobre su código: a menos que se asegure de que el dataRates de todos los servidores no cambie durante la clasificación, ¡puede obtener resultados inconsistentes! Debe sincronizar sus métodos para que datarates no cambien hasta que toda la lista esté ordenada.

Answer 6

No necesita utilizar llamadas a métodos en la clase, incluso si el campo era privado, que no siempre se conoce, ya que privado restringe el acceso a una clase, no a un objeto.

Debido a que su método no hace más que devolver el atributo, puede utilizar el atributo directa:

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

Pero la JVM podría optimizar la llamada a la función, y en el rango de 100 elementos, apenas será medible .

Su método arroja un doble. ¿Puede explicar por qué?

Con enteros, usted podría hacer:

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

Pero tenga en cuenta los posibles valores más extremas para cuestiones de int sobre y empotramiento.

Answer 7

Primero, su tipo de variable serverDataRate es int. Pero el tipo de devolución del método getter es doble. Cuando el comparador funciona, todo el método getServerDataRate convierte el campo en un formato de datos londer. Si su método getter retorna igual que el tipo de campo, entonces el tiempo de comparación será más corto. Segundo, no necesita usar if(), en el método de comparación si su misión es una operación simple. Solo usa la resta. De esta manera:

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