使用自定义比较器时，使用TreeSet或ArrayList是否更好？

我已经实现了一个图表。 我想根据它们的度数对给定的顶点子集进行排序。 因此，我编写了一个名为DegreeComparator的自定义比较器。

 private class DegreeComparator implements Comparator { @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()); } } 

那么，下面哪一个更有效率？

使用TreeSet

 public Collection sort(Collection unsorted) { Set sorted = new TreeSet(new DegreeComparator()); sorted.addAll(unsorted); return sorted; } 

使用ArrayList

 Collections.sort(unsorted, new DegreeComparator()); 

请注意，第二种方法不是函数，而是单行代码。

直观地说，我宁愿选择第二个。 但我不确定它是否更有效率。

Answer 1

TreeSet是一个Set。 它删除重复项（具有相同程度的元素）。 所以两者都不相同。

无论如何，如果您想要的自然是排序列表，那么对列表进行排序。 无论集合是否具有重复，这都将起作用，即使它具有与填充TreeSet相同的复杂度（O（n * log（n）），它也可能更快（因为它只需要移动数组中的元素，而不是必须创建大量的树节点）。

Answer 2

Java API包含许多Collection和Map实现，因此可能会弄清楚要使用哪一个。 这是一个快速的流程图，可能有助于从最常见的实现中进行选择

Answer 3

如果你只排序一次，那么ArrayList显然是赢家。 如果您经常添加或删除项目作为再次排序列表，那么TreeSet会更好。

还要注意，所有树结构都需要更多内存和内存访问间接，这使得它们更慢。

---

如果中等大小的列表（由单个元素频繁更改）的情况下，最快的解决方案可能是使用ArrayList并插入到正确的位置（显然假设数组最初排序）。

您需要通过Arrays.binarySearch确定插入位置并插入或删除。 实际上，我不会这样做，除非性能真的很关键，基准测试会显示它有帮助。 当列表变得非常大并且增益受限时，它会变慢，因为Java使用TimSort ，后者针对这种情况进行了优化。

---

正如评论中所指出的那样，确保Comparator返回不同的值有时是非常重要的。 幸运的是，Guava的Ordering#arbitrary ，如果您不需要与equals兼容，它可以解决问题。 如果你这样做，可以写一个类似的方法（我敢肯定，如果要求，我可以找到它）。