添加到集合然后对其进行排序或添加到已排序的集合是否更快？

Question

如果我有Map这样的:

HashMap<Integer, ComparableObject> map;

我想获得一个使用自然排序排序的值集合,哪种方法最快？

(一个)

创建可排序集合的实例,例如ArrayList,添加值,然后对其进行排序:

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

(B)

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

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

请注意,结果集合永远不会被修改,因此排序只需要进行一次.

Answer 1

TreeSet具有 log(n)时间复杂度的add()/remove()/contains()方法保证.排序ArrayList采取n*log(n)操作,但add()/get()只采取1操作.

因此,如果您主要检索并且不经常排序,那么这ArrayList是更好的选择.如果你经常排序,但不要检索那么多TreeSet将是一个更好的选择.

Answer 2

从理论上讲,最后的排序应该更快.在整个过程中维护已排序状态可能需要额外的CPU时间.

从CS的角度来看,两个操作都是NlogN,但是1种应该具有较低的常量.

Answer 3

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

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

编辑:

我已经创建了一个基准测试(您可以在pastebin.com/5pyPMJav上访问它)来测试三种方法(ArrayList + Collections.sort,TreeSet和我最好的两种方法)并且我总是获胜.测试文件创建一个包含10000个元素的映射,其中的值有一个故意糟糕的比较器,然后三个策略中的每一个都有机会a)对数据进行排序,b)迭代它.这是一些示例输出(您可以自己测试):

编辑:我添加了一个方面,记录调用Thingy.compareTo(Thingy),我还添加了一个基于PriorityQueues的新策略,比以前的任何一个解决方案都要快得多(至少在排序方面).

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

奇怪的是,我的方法在迭代中表现最好(我原本以为迭代中的ArrayList方法没有差异,我的基准测试中是否有错误？)

免责声明:我知道这可能是一个可怕的基准,但它有助于明确指出你,我当然没有操纵它来让我的方法获胜.

(代码对于equals/hashcode/compareTo构建器具有apache commons/lang的依赖关系,但它很容易重构出来)

Answer 4

如果您选择实施B),请务必阅读我对底部TreeSet的评论

如果你的应用程序只是偶尔进行排序而是经常重复,我会说你最好使用一个简单的未排序列表.将其排序一次,然后从更快的迭代中获益.迭代在数组列表上特别快.

但是,如果您希望始终保证排序顺序,或者您可能经常添加/删除元素,则使用已排序的集合并在迭代时执行命中.

所以在你的情况下,我会说A)是更好的选择.该列表排序一次,不会更改,因此可以从阵列中获益.迭代应该非常快,特别是如果你知道它的ArrayList并且可以直接使用ArrayList.get()而不是Iterator.

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