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

问题描述

如果我有一个地图像这样：

  HashMap< Integer，ComparableObject>地图; 
  

我想获得使用自然排序排序的值的集合， p>

（A）

创建一个可排序集合的实例，例如 ArrayList ，添加值，然后对其进行排序：

  List< ComparableObject> sortedCollection = new ArrayList< ComparableObject>（map.values（））; 
 Collections.sort（sortedCollection）; 
  

（B）

如 TreeSet 的有序集合，然后添加以下值：

  ; ComparableObject> sortedCollection = new TreeSet< ComparableObject>（map.values（））; 
  

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

解决方案

TreeSet具有 log（n）时间复杂度保证$ c> add（）/ remove（）/ contains（）方法。
排序 ArrayList 需要 n * log（n）操作，但 add （）/ get（）只需要操作 1 。

主要检索，不经常排序， ArrayList 是更好的选择。如果你经常排序，但不检索这么多 TreeSet 将是一个更好的选择。

If I have a Map like this:

HashMap<Integer, ComparableObject> map;

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

(A)

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)

Create an instance of an ordered collection like TreeSet, then add the values:

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 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.

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屋！