Java中最快的列表排序方法

Question

Java中最快的列表排序方法

7

我有以下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);
        }           
    }
}

我正在使用上面的代码，根据服务器数据速率将元素按降序排序。这里样本集非常小，假设我有一个包含100个元素的更大的样本集，并且需要每5-10秒执行一次该代码。这是排序列表的最快方法，还是我不知道更快的方法？

- bhavs

2

除非您的比较步骤非常繁重（似乎不是这种情况），否则100个元素并不算一个大集合。在任何稍微现代一点的机器上，100个元素将被极快地排序。 - pcalcao

5

你想每5-10秒钟排序100个元素吗？那么不要再担心最佳算法了，因为你不可能通过任何可衡量的方式来改进Collections.sort。 - Paul Tomblin

你可以使用TreeMap吗？它几乎像列表一样工作，但始终保持所有元素排序。 - Nican

1

你的比较器可以简化为一行代码 "return Double.compare(o1.getServerDataRate(), o2.getServerDataRate());"。 - Adam

@Nican 我本来可以使用TreeMap（这实际上是我的最初选择），但是由于某些数据速率可能会重复，所以我使用了以上代码。 - bhavs

7个回答

4

如果您的比较步骤不是非常重的话（看起来不像），那么100个元素并不是一个很大的集合。在任何稍微现代一点的计算机上，100个元素都能被非常快速地排序。

话虽如此，我认为您的方法已经非常接近标准了，除非您真正需要它，否则不必担心优化它。

过早的优化是许多错误的根源（假设是母亲）。

- pcalcao

2

即使字段是私有的，也不需要在类中使用方法调用（method calls），因为私有限制了对类的访问，而不是对象的访问。

由于您的方法只是返回属性，所以可以直接使用该属性：

@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个元素范围内，几乎不可测量。

你的方法返回一个double - 你能解释一下为什么吗？

使用整数，你可以这样做：

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

但是请考虑int类型数据的上下限问题。

- user unknown

1

这不是正常的。检查一下你计时的方式。

long start = System.nanoTime();

// Sort here

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

- Martijn Courteaux

1

考虑到您不经常进行排序，速度不应该是一个问题。即使有成千上万的项目，Collections.sort 也非常快。

您是否尝试过您的应用程序以查看速度是否是一个问题？过早地进行优化并不是一个好主意 :)

请注意您代码中的一件事情：除非您确保所有服务器的 dataRates 在排序期间不会更改，否则可能会得到不一致的结果！您应该同步您的方法，以便在整个列表排序之前 datarates 不会更改。

- ARRG

0

你可以使用数据结构来更快地完成排序。

二叉搜索树（BST）或 TRIE 可以帮助您更快地对大量数据进行排序。

虽然它们需要一些较长的代码，但如果数据集很大，它们将在长期运行中帮助您。

- Sabya

0

首先，您的 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

- worker105

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Lawrey · Accepted Answer

我改了你的测试

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。