添加到集合然后对其进行排序或添加到已排序的集合中是否更快? [英] Is it faster to add to a collection then sort it, or add to a sorted collection?

问题描述

如果我有这样的 Map:

HashMap<Integer, ComparableObject> map;

我想获取一组使用自然排序排序的值，哪种方法最快?

and I want to obtain a collection of values sorted using natural ordering, which method is fastest?

创建一个像 ArrayList 这样的可排序集合的实例，添加值，然后对其进行排序:

Create an instance of a sortable collection like ArrayList, add the values, then sort it:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

创建一个有序集合的实例，如 TreeSet，然后添加值:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

请注意，生成的集合永远不会被修改，因此排序只需要进行一次.

Note that the resulting collection is never modified, so the sorting only needs to take place once.

推荐答案

TreeSet 有一个 log(n) 时间复杂度保证 add()/remove()/contains() 方法.对 ArrayList 排序需要 n*log(n) 操作，但 add()/get() 只需要 1> 操作.

TreeSet has a log(n) time complexity guarantuee for add()/remove()/contains() methods. Sorting an ArrayList takes n*log(n) operations, but add()/get() takes only 1 operation.

所以如果你主要是检索，并且不经常排序，ArrayList 是更好的选择.如果您经常排序但不检索那么多 TreeSet 将是更好的选择.

So if you're mainly retrieving, and don't sort often, ArrayList is the better choice. If you sort often but dont retrieve that much TreeSet would be a better choice.

这篇关于添加到集合然后对其进行排序或添加到已排序的集合中是否更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！