是添加到集合然后对其排序更快,还是添加到已排序的集合更快?

树集有一个 log(n) 时间复杂度保证 add()/remove()/contains() 方法。 ArrayList 拿 n*log(n) 操作,但是 add()/get() 只需要 1

所以如果你主要是检索,而不经常分类, 阵列列表 TreeSet 是个更好的选择。

理论上,最后的排序应该更快。

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

为什么不两全其美呢?如果不再使用它,请使用树集进行排序,并用内容初始化ArrayList

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

编辑:

pastebin.com/5pyPMJav )测试这三种方法(ArrayList+集合.排序,树集和我最好的两个世界的方法)和我的总是赢。测试文件创建了一个包含10000个元素的映射,这些元素的值有一个非常糟糕的比较器,然后三个策略中的每一个都有机会a)对数据进行排序,b)对其进行迭代。下面是一些示例输出(您可以自己测试):

编辑:我添加了一个方面,记录调用比较一下(Thingy)我还添加了一个基于优先级队列的新策略,它比以前的解决方案快得多(至少在排序方面)。

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方法没有区别,我的基准测试中有bug吗?)

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

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

但是,如果您希望一直保证排序顺序,或者您可能经常添加/删除元素,那么就使用排序的集合,并在迭代中获得成功。

知道

我还要补充的是,树集的定义是一个集合,这意味着对象是唯一的。树集通过在Comparator/Comparable上使用compareTo来确定相等性。如果您尝试添加两个compareTo返回值为0的对象,则很容易发现缺少数据。e、 g.将“C”、“A”、“B”、“A”添加到树集中将返回“A”、“B”、“C”

Collections.sort

TreeSet

所以两者都是相同的大O算法。

在列表中插入是1。

SortedSet中的排序已经包含在inserting中,因此它是0。 列表中的排序是O(n*log(n))。

所以SortedSet的总复杂度是O(n*k),对于除最后一种情况外的所有情况都是k<log(n)。 相反,List的总复杂度是O(n*log(n)+n),所以O(n*log(n))。

因此,在我看来,针对可用功能和性能的最佳解决方案是Sean Patrick Floyd提出的:

• 使用分类集插入,

1. 如果要排序的集合是短期的,例如,用作方法的参数,并且需要在方法中对列表进行排序,则使用集合.排序(收藏)。或者如果它是长寿命的对象,但是您很少需要对它进行排序。

理由:特定的东西需要排序的集合,您可能不会经常添加或删除。因此,一旦对集合进行排序,您就不会真正关心其中的元素了。你基本上:

如果向已排序的集合中添加新元素,则必须再次对集合排序,因为插入新元素时不能保证顺序。

2. 如果要排序的集合是长期存在的和/或它是类中的字段,并且需要在 任何时候 然后应该使用排序数据结构,如TreeSet。

插入/删除->使用它(始终保证集合已排序)

没有特定的时刻需要对集合进行排序,而是希望集合一直进行排序。

使用TreeSet的缺点是保留已排序集合所需的资源。它使用红黑树,并且需要O(logn)时间开销来执行get、put操作。

然而,如果使用简单的集合(如ArrayList),get、add操作是O(1)常量时间。