性能—在困难的场景中高效地对Java集合进行排序

Question

如果我有很多具有缓慢变化键的对象，我应该使用哪个Java集合
基本上，我有一个ArrayList，其中包含所有需要排序的对象。该ArrayList有时会被其他线程更改。为了对它进行迭代，我使用clear和addAll将ArrayList写入另一个ArrayList，直到现在，但我现在意识到这也会导致ConcurrentModificationException，所以我想更改它

我用于迭代的新集合（当前为ArrayList）需要使用自定义比较器进行排序。问题是，在我复制下一份原件之前，密钥会发生变化，我必须对其进行多次排序。这些种类的顺序通常已经基本正确了。插入排序在这里可能很好
现在的大问题是：

1. 我是否使用TreeSet和呼叫收集。订单更改时对其进行排序
2. 我是否使用某种列表（哪种？ArrayList？LinkedList？）和电话收款。订单更改时进行排序

我认为这个问题的正确答案只能在考虑到我必须先复制其他未排序的集合（ArrayList，但不一定）并在集合中的数据被其他线程更改时执行时给出

我对解决办法的想法如下：

1. 让第二个集合成为ArrayList，并始终使用集合更新它。复制（首先将其设置为正确的大小，但在我的场景中通常应该已经设置为正确的大小（我意识到这不是原子的，可能会导致问题）），然后调用集合。我想怎么分类就怎么分类。可能在初始排序之后为每个排序执行插入排序算法，因为这样应该更快
2. 对第二个集合使用TreeSet。问题是，我不知道如何迭代原始threadsafe以添加所有元素。此外，我不知道如何在初始化之后有效地对集合进行排序。我看到有人在使用收藏。不错，但我不知道那里的效率。还要记住，它几乎是分类的

您还需要记住的是，我只需要迭代原始和工作副本集合，不需要索引

我现在编写了一些Java代码来说明这个问题：

public static List<FloatWrapper> pending_additions = Collections.synchronizedList(new ArrayList<>());
public static List<FloatWrapper> pending_removals = Collections.synchronizedList(new ArrayList<>());

public static List<FloatWrapper> list = new ArrayList<>();

public static Random rnd = new Random();

public static void main(String[] args) {
    // initialize array
    for (int i = 0; i < 1000; i++) {
        list.add(new FloatWrapper(i));
    }
    // the main loop (runs basically infinitly)
    for (int runs_infinitly = 0; runs_infinitly < 100; runs_infinitly++) {
        // apply pending changes
        synchronized (pending_additions) {
            list.addAll(pending_additions);
            pending_additions.clear();
        }
        synchronized (pending_removals) {
            list.removeAll(pending_removals);
            pending_removals.clear();
        }

        // doing my stuff
        for (int i = 0; i < 5; i++) {
            // sort array with quicksort I believe, which is not the fastest
            // for this scenario usually, except for the start when its completly unsorted
            System.out.println("sorting");
            Collections.sort(list);
            // iterate very often doing different things
            for (int j = 0; j < 1; j++) {
                for (FloatWrapper num : list) {
                    // do something with num
                    System.out.print(num.number + " ");
                }
                System.out.println();
            }
            System.out.println("changing keys");
            // change the values that are used for sorting
            for (FloatWrapper num : list) {
                num.number += (rnd.nextFloat() - 0.5f) * 0.2f;
            }
        }
    }
}

public static class FloatWrapper implements Comparable<FloatWrapper> {
    public float number;

    public FloatWrapper(float number) {
        this.number = number;
    }

    public int compareTo(FloatWrapper arg0) {
        return Float.compare(number, arg0.number);
    }
}

从其他线程写入的数组只有挂起的_添加和挂起的_删除。自从我写这篇文章以来，它们是我的进步，所以不需要复制和引用整个列表
我的问题仍然存在，我是否应该使用树集来提高性能，我是否应该做其他不同的事情？基本上，我不知道如何有效地对树集进行排序。我甚至可以想象ArrayList和Collection。sort（）更有效，但我不知道。有人能解释一下吗

我还使用了一个定制的比较器，它甚至有一点数学知识，所以在这里优化排序过程是非常有益的

Answer 1

您当前的实现已经利用了列表的部分排序：

用于Collections.sort的Javadoc写入

This implementation defers to the List.sort(Comparator) method

以及该方法的Javadoc says

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

由于对集合进行迭代的频率远高于对集合进行排序，因此迭代（以及其中的操作）的成本可能远高于排序。也就是说，通过进一步调整排序，您不太可能获得显著的改进

Answer 2

您真正需要的不是很清楚，但是我认为您应该可以维护一个CopyOnWriteArrayList<T>，然后使用它进行迭代

list.stream().sorted(yourComparator).forEach(yourAction);

CopyOnWriteArrayList是线程安全的，也就是说，如果其他线程在迭代过程中更改了它，您将不会得到一个ConcurrentModificationException并像开始时那样继续迭代列表

编辑：或者，因为您要迭代多次：

List<FloatWrapper> sorted = list.stream().sorted().collect(toList());
for (int i = 0; i < 5; i++) { sorted.forEach(i -> doYourStuff(i)); }