添加到集合然后对其进行sorting还是添加到已sorting的集合?

如果我有这样的Map

 HashMap<Integer, ComparableObject> map; 

我想获得使用自然顺序sorting的值的集合,哪种方法最快?

(一个)

创build像ArrayList这样的可sorting集合的实例,添加值,然后对其进行sorting:

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

(B)

创build一个有序集合(如TreeSet的实例,然后添加值:

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

请注意,生成的集合永远不会被修改,所以sorting只需要进行一次。

对于add()/remove()/contains()方法,TreeSet具有log(n)时间复杂度保证。 对ArrayList进行sorting需要n*log(n)操作,但add()/get()只需要1操作。

所以,如果你主要是检索,而不是经常sorting, ArrayList是更好的select。 如果你经常sorting,但不检索那么多TreeSet将是一个更好的select。

理论上,最后的sorting应该更快。 在整个过程中保持sorting状态可能需要额外的CPU时间。

从CS的angular度来看,两种操作都是NlogN,但是1种应该有较低的常量。

为什么不使用两全其美? 如果您再也不使用它,请使用TreeSet进行sorting,并使用内容初始化ArrayList

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

编辑:

我已经创build了一个基准testing(可以在pastebin.com/5pyPMJav访问它)来testing三种方法(ArrayList + Collections.sort,TreeSet和我两全其美的方法),而我总是获胜。 testing文件创build一个包含10000个元素的映射,其中的值有一个有意识的可怕的比较器,然后三个策略中的每一个都有机会a)对数据进行sorting,并且b)遍历它。 这里是一些示例输出(你可以自己testing):

编辑:我已经添加了一个方面,logging调用Thingy.compareTo(Thingy),我也添加了一个基于PriorityQueues的新战略比任何以前的解决scheme(至less在sorting)快得多。

 compareTo() calls:123490 Transformer ArrayListTransformer Creation: 255885873 ns (0.255885873 seconds) Iteration: 2582591 ns (0.002582591 seconds) Item count: 10000 compareTo() calls:121665 Transformer TreeSetTransformer Creation: 199893004 ns (0.199893004 seconds) Iteration: 4848242 ns (0.004848242 seconds) Item count: 10000 compareTo() calls:121665 Transformer BestOfBothWorldsTransformer Creation: 216952504 ns (0.216952504 seconds) Iteration: 1604604 ns (0.001604604 seconds) Item count: 10000 compareTo() calls:18819 Transformer PriorityQueueTransformer Creation: 35119198 ns (0.035119198 seconds) Iteration: 2803639 ns (0.002803639 seconds) Item count: 10000 

奇怪的是,我的方法在迭代中performance得最好(我会认为迭代中ArrayList方法没有区别,我的基准testing中是否有一个错误?)

免责声明:我知道这可能是一个可怕的基准,但它有助于让你的观点,我当然没有操纵它,使我的方法取胜。

(这个代码对于apache的commons / lang依赖于equals / hashcode / compareTo构build器,但是应该很容易重构它)

如果你select实现B),一定要阅读我关于TreeSet的评论。

如果你的应用程序只是偶尔进行sorting,但是会迭代很多,我会说你最好使用一个简单的未sorting列表。 将其sorting一次,然后从更快的迭代中受益。 数组列表上的迭代速度特别快。

但是,如果你想sorting顺序保证所有的时间,或者你可能经常添加/删除元素,然后使用sorting的集合,并采取迭代的命中。

所以在你的情况下,我会说A)是更好的select。 该列表被sorting一次,不会改变,因此从数组中获益。 迭代应该非常快,特别是如果你知道它是一个ArrayList,并且可以直接使用ArrayList.get()而不是迭代器。

我还要补充说TreeSet的定义是一个Set,意思是对象是唯一的。 TreeSet通过在Comparator / Comparable上使用compareTo来确定相等性。 如果您尝试添加compareTo返回值为0的两个对象,则可能很容易发现自己缺less数据。例如,向TreeSet添加“C”,“A”,“B”,“A”将返回“A”,“B “, “C”

Collections.sort使用具有O(nlog n)的mergeSort。

TreeSet有红黑树底层,基本操作有O(logn)。 因此n个元素也有O(nlog n)。

所以都是一样的大Oalgorithm。