самый быстрый способ сортировки списка в 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

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

Кстати: я изменил поля doubleбыть int.

Answer 2

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

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

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

Answer 3

Вам не нужно использовать вызовы методов в классе, даже если поле было приватным, что не всегда известно - 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 4

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

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

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

Answer 5

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

long start = System.nanoTime();

// Sort here

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

Answer 6

Во-первых, тип вашей переменной serverDataRate - int. Но метод возврата метода get является двойным. Когда компаратор работает, весь метод getServerDataRate преобразует поле в более длинный формат данных. Если ваш метод получателя возвращает тип, совпадающий с типом поля, тогда время сравнения будет короче. Во-вторых, нет необходимости использовать 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

Answer 7

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

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

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