在 Java 中对列表进行排序的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9671243/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
fastest way to sort a list in Java
提问by bhavs
I have the following code in Java:
我在 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 am using the above code to sort the elements in descending order based on the serverDataRate. Here the sample set is quite small supposing I have a larger sample set of 100 elements in the list and the code had to be executed every 5-10 seconds. Is this the fastest way to sort the list or is there a faster method I am not aware of?
我使用上面的代码根据 serverDataRate 按降序对元素进行排序。这里的样本集非常小，假设我在列表中有一个包含 100 个元素的更大样本集，并且代码必须每 5-10 秒执行一次。这是对列表进行排序的最快方法还是我不知道的更快方法？
采纳答案by Peter Lawrey
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 it prints
它打印
Sorting 1,000,000 took 0.438 seconds
That's quite a bit faster ;)
这要快得多;)
BTW: I changed the doublefields to be int.
顺便说一句：我将double字段更改为int.
回答by Martijn Courteaux
This isn't normal. Check your way of timing it.
这不正常。检查你的计时方式。
long start = System.nanoTime();
// Sort here
long time = System.nanoTime() - start;
System.out.println(time / 1000000L + " Milliseconds");
回答by pcalcao
100 elements isn't a large set unless your comparison step is really heavy (doesn't seem like it). 100 elements will get sorted extremelyfast in any slightly modern machine.
100 个元素不是一个大集合，除非您的比较步骤非常繁重（看起来不像）。在任何稍微现代的机器中，100 个元素都会非常快地排序。
That being said, I think your approach is pretty close to standard, and I wouldn't worry about trying to optimize it unless you really end up needing it.
话虽如此，我认为您的方法非常接近标准，除非您真的最终需要它，否则我不会担心尝试优化它。
Early optimization is the father of many screw ups (assumptions being the mother).
早期优化是许多错误的根源（假设是母亲）。
回答by Sabya
You can use data structure to accomplish the sorting in faster way.
您可以使用数据结构以更快的方式完成排序。
A BST (Binary Search Tree ) or TRIE will help u sort huge data in faster way.
BST（二叉搜索树）或 TRIE 将帮助您以更快的方式对大量数据进行排序。
They will require a bit lengthy code, but will help u in log run if the data set is large.
它们将需要一些冗长的代码，但如果数据集很大，它将帮助您进行日志运行。
回答by ARRG
Given that you are not sorting often, speed shouldn't be an issue. Even with thousands of items, Collections.sort is very fast.
鉴于您不经常排序，速度应该不是问题。即使有数千个项目，Collections.sort 也非常快。
Have you tried your application to see whether speed was an issue ? Premature optimisation is not a good idea :)
您是否尝试过您的应用程序以查看速度是否是一个问题？过早的优化不是一个好主意:)
Be wary of one thing about your code: unless you make sure that the dataRatesof all servers do not change during sorting, you may get inconsistent results ! You should synchronize your methods so that dataratesdon't change until the whole list is sorted.
请注意您的代码的一件事：除非您确保dataRates在排序期间所有服务器的 都不会更改，否则您可能会得到不一致的结果！您应该同步您的方法，以便datarates在整个列表排序之前不要更改。
回答by user unknown
You don't need to use method calls in the class, even if the field was private which isn't always known - private restricts the access to a class, not to an object.
您不需要在类中使用方法调用，即使该字段是私有的，这并不总是已知的 - 私有限制了对类的访问，而不是对对象的访问。
Since your method does nothing but return the attribute, you can use the attribute directly:
由于您的方法只返回属性，因此您可以直接使用该属性：
@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 might optimize the function call, and in the range of 100 elements, it will hardly be measurable.
但是 JVM 可能会优化函数调用，在 100 个元素的范围内，它几乎无法衡量。
Your method returns a double - can you explain why?
你的方法返回一个双倍 - 你能解释一下为什么吗？
With ints, you could just do:
使用整数，你可以这样做：
@Override
public int compare (ServerInfo o1, ServerInfo o2) {
return o2.serverDataRate - o1.serverDataRate;
}
But consider the extremest possible values for questions of int over- and underrun.
但是，对于 int 溢出和不足的问题，请考虑最极端的可能值。
回答by worker105
First,Your serverDataRate variable type is int. But getter method return type is double. When the comparator is working, all getServerDataRate method converts the field to a londer data format. If your getter method return type same as the field type then the compare time will be shorter. Second, No need to use if(), in compare method if your mission is simple operation. Just use subtraction. Like this:
首先，您的 serverDataRate 变量类型是 int。但是getter 方法返回类型是double。当比较器工作时，所有 getServerDataRate 方法都会将字段转换为 londer 数据格式。如果您的 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
