быстрый способ сортировки списка в Java

Question

У меня есть следующий код в 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); 
     }   
    } 
} 

Я использую приведенный выше код для сортировки элементов в порядке, основанном на serverDataRate убывания. Здесь набор образцов довольно мал, предполагая, что у меня есть более широкий набор образцов из 100 элементов в списке, и код должен выполняться каждые 5-10 секунд. Является ли это самым быстрым способом сортировки списка или есть более быстрый метод, о котором я не знаю?

Answer 1

Я изменил ваш тест

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

и печатает

Sorting 1,000,000 took 0.438 seconds 

Это совсем немного быстрее;)

BTW: Я изменил double поля, чтобы быть int.

Answer 2

Это не нормально. Проверьте свой способ отсчета времени.

long start = System.nanoTime(); 

// Sort here 

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

Answer 3

100 элементов не является большим комплектом, если ваш шаг сравнения действительно тяжелый (не похоже на него). 100 элементов будут отсортированы чрезвычайно быстро в любой слегка современной машине.

Это, как говорится, я думаю, что ваш подход довольно близок к стандарту, и я бы не стал беспокоиться о том, чтобы его оптимизировать, если вы действительно не нуждаетесь в нем.

Ранняя оптимизация является отцом многих винтов (предположения являются матерью).

Answer 4

Структуру данных можно использовать для ускорения сортировки.

BST (Двоичное дерево поиска) или TRIE поможет вам сортировать огромные данные быстрее.

Для этого потребуется немного длинный код, но он поможет выполнить вход в журнал, если набор данных большой.

Answer 5

Учитывая, что вы не сортируете часто, скорость не должна быть проблемой. Даже с тысячами предметов Collections.sort очень быстро.

Вы пробовали свое приложение, чтобы узнать, не является ли проблема проблемой? Преждевременная оптимизация не является хорошей идеей :)

Остерегайтесь одной вещи о своем коде: если вы не убедитесь, что dataRates всех серверов не изменяется при сортировке, вы можете получить противоречивые результаты! Вы должны синхронизировать свои методы так, чтобы datarates не изменялись до тех пор, пока весь список не будет отсортирован.

Answer 6

Вам не нужно использовать вызовы методов в классе, даже если это поле было частным, что не всегда известно - private ограничивает доступ к классу, а не к объекту.

Поскольку ваш метод не делает ничего, кроме возврата атрибута, вы можете использовать атрибут непосредственно:

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

Но JVM может оптимизировать вызов функции, и в диапазоне 100 элементов, то вряд ли измеримы ,

Ваш метод возвращает двойной - можете ли вы объяснить, почему?

С Интс, вы можете просто сделать:

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

Но рассмотрим экстремистского возможные значения вопросов ИНТ сверх- и опустошения.

Answer 7

Во-первых, ваш тип переменной serverDataRate является int. Но возвращаемый тип метода getter равен double. Когда компаратор работает, весь метод getServerDataRate преобразует поле в более удобный формат данных. Если ваш метод getter возвращает тип, аналогичный типу поля, время сравнения будет короче. Во-вторых, вам не нужно использовать if(), в методе сравнения, если ваша миссия проста в эксплуатации. Просто используйте вычитание. Примерно так:

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