java - 具有可比 Vs TreeSet 的列表

Question

选项 1：创建一个实现 Comparable 的列表，并在每次添加值时使用 collections.sort(List l) 对其进行排序。选项 2：制作一个 TreeSet（它始终保持自身排序）。

哪个会更快？我问这个是因为 List 为我提供了我需要的 ListIterator 选项，因为它允许我在迭代时添加一个元素。

Answer 1

最重要的区别：

Criterion       | List with Collections.sort | TreeSet 
----------------+----------------------------+---------
cost of adding  | O(n log n)                 | O(log n)
equal sort keys | permitted                  | eliminated as duplicates
iteration       | bidirectional, can insert  | unidirectional, can not insert

要在没有得到 a 的情况下在迭代时插入元素ConcurrentModificationException，您可以执行以下操作：

for (E e : new ArrayList<E>(collection)) {
    // some other code

    collection.add(anotherE);
}

Answer 2

Collections.sort 使用经过修改的合并排序和nlog(n)排序时间。如果您在每次添加时调用该方法，您可能会以n^2log(n)时间结束。而在 TreeSet 中的插入是保证 log(n)。因此，如果您在每次添加时调用它，它就会变成n.log(n)。所以我建议改用 TreeSet。但是 TreeSet 不允许重复，所以这可能会影响您的决定。

如果您使用的是 List，那么您可以做一件事来优化，而不是使用 Collections.sort；如您所知，每次在列表中插入元素时，列表已经排序，因此在此处使用插入排序会给您带来更好的性能，因为在这种情况下插入排序的性能更好。

Answer 3

在这里使用 TreeSet。

添加到 TreeSet 是一个log(n)操作。添加到列表是 const time，但排序是n log(n).