Java 使用自定义比较器时使用 TreeSet 还是 ArrayList 更好
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24371204/
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
Is it better to use a TreeSet or ArrayList when using a custom comparator
提问by padawan
I have implemented a graph.
I want to sort a given subset of vertices with respect to their degrees.
Therefore, I've written a custom comparator named DegreeComparator.
我已经实现了一个图表。我想根据度数对给定的顶点子集进行排序。因此，我编写了一个名为DegreeComparator.
private class DegreeComparator implements Comparator<Integer>
{
@Override
public int compare(Integer arg0, Integer arg1)
{
if(adj[arg1].size() == adj[arg0].size()) return arg1 - arg0;
else return adj[arg1].size() - adj[arg0].size());
}
}
So, which one of the below is more efficient?
那么，以下哪一项更有效？
Using TreeSet
使用 TreeSet
public Collection<Integer> sort(Collection<Integer> unsorted)
{
Set<Integer> sorted = new TreeSet<Integer>(new DegreeComparator());
sorted.addAll(unsorted);
return sorted;
}
Using ArrayList
使用 ArrayList
Collections.sort(unsorted, new DegreeComparator());
Notice that the second approach is not a function, but a one-line code.
请注意，第二种方法不是函数，而是一行代码。
Intuitively, I'd rather choose the second one. But I'm not sure if it is more efficient.
直觉上，我宁愿选择第二个。但我不确定它是否更有效。
采纳答案by Sameer Kazi
Java API contains numerous Collection and Map implementations so it might be confusing to figure out which one to use. Here is a quick flowchart that might help with choosing from the most common implementations
Java API 包含许多 Collection 和 Map 实现，因此弄清楚使用哪一个可能会令人困惑。这是一个快速流程图，可能有助于从最常见的实现中进行选择
回答by JB Nizet
A TreeSet is a Set. It removes duplicates (elements with the same degree). So both aren't equivalent.
TreeSet 是一个集合。它删除重复项（具有相同度数的元素）。所以两者并不等价。
Anyway, if what you want naturally is a sorted list, then sort the list. This will work whether the collection has duplicates or not, and even if it has the same complexity (O(n*log(n)) as populating a TreeSet, it is probably faster (because it just has to move elements in an array, instead of having to create lots of tree nodes).
无论如何，如果您自然想要一个排序列表，那么对列表进行排序。无论集合是否有重复，这都会起作用，即使它与填充 TreeSet 具有相同的复杂性（O（n*log（n）），它也可能更快（因为它只需要移动数组中的元素，而不必创建大量的树节点）。
回答by maaartinus
If you only sort once, then the ArrayListis an obvious winner. The TreeSetis better if you add or remove items often as sorting a list again and again would be slow.
如果您只排序一次，那么ArrayList显然是赢家。的TreeSet，如果你经常添加或删除的项目，如再次排序列表，并再次将是缓慢更好。
Note also that all tree structures need more memory and memory access indirection which makes them slower.
还要注意，所有的树结构都需要更多的内存和内存访问间接，这使它们变慢。
If case of medium sized lists, which change rather frequently by a single element, the fastest solution might be using ArrayListand inserting into the proper position (obviously assuming the arrays get sorted initially).
如果是中等大小的列表，它会经常被单个元素更改，那么最快的解决方案可能是使用ArrayList并插入到正确的位置（显然假设数组最初被排序）。
You'd need to determine the insert position via Arrays.binarySearchand insert or remove. Actually, I would't do it, unless the performance were really critical and a benchmark would show it helps. It gets slow when the list get really big and the gain is limited as Java uses TimSort, which is optimized for such a case.
您需要通过Arrays.binarySearch插入或删除来确定插入位置。实际上，我不会这样做，除非性能非常关键并且基准测试表明它有帮助。当列表变得非常大并且增益有限时，它会变慢，因为 Java 使用TimSort，它针对这种情况进行了优化。
As pointed in a comment, assuring that the Comparatorreturns different values is sometimes non-trivial. Fortunately, there's Guava's Ordering#arbitrary, which solves the problem if you don't need to be compatible with equals. In case you do, a similar method can be written (I'm sure I could find it somewhere if requested).
正如评论中所指出的，确保Comparator返回不同的值有时并非易事。幸运的是，有 Guava's Ordering#arbitrary，如果您不需要与equals. 如果您这样做，可以编写类似的方法（如果需要，我相信我可以在某处找到它）。
