Эффективно храните коллекцию Java в сложном сценарии

Question

Какую коллекцию Java следует использовать, если у меня много объектов с медленно меняющимися ключами?
В основном у меня есть один ArrayList, в котором есть все объекты, требующие сортировки.Этот ArrayList иногда изменяется другим потоком.Чтобы перебрать его, я записал ArrayList в другой ArrayList с помощью clear и затем addAll до сих пор, но теперь я понял, что это также может вызвать исключение ConcurrentModificationException, поэтому я хочу изменить это.

Эта новая коллекция (в настоящее время ArrayList), который я использую для итерации, должен быть отсортирован с помощью специального компаратора.Проблема в том, что, прежде чем я сделаю следующую копию оригинала, ключи будут изменены, и мне придется сортировать их несколько раз.Порядок для этих сортов почти всегда правильный.Сортировка вставки здесь может быть хорошей.
Большой вопрос сейчас:

1. Должен ли я использовать TreeSet и вызывать на нем Collections.sort при изменении порядка
2. Использую ли якакой-то List (какой? ArrayList? LinkedList?) и вызов Collections.sort при изменении порядка

Я думаю, что правильный ответ на этот вопрос можно дать, только если учесть, что мне нужно скопироватьсначала другую несортированную коллекцию (ArrayList, но не обязательно) и делайте это, пока данные в коллекции изменяются другим потоком.

Мои мысли по поводу решения следующие:

1. Пусть вторая коллекция будет ArrayList и обновлять ее всегда с Collections.copy (сначала нужно сделать правильный размер, но обычно это должен быть правильный размер уже в моем сценарии (я понимаю, что это не атомарно и может вызвать проблемы)), затемзвоните Collections.sort на него так часто, как я хочу.Может быть, реализовать алгоритм сортировки вставкой для каждой сортировки после начальной сортировки, потому что он должен быть быстрее.
2. Как-нибудь использовать TreeSet для второй коллекции.Проблема в том, что я не знаю, как бы я перебрал исходный потокобезопасный, чтобы добавить все элементы оттуда.Также я не знаю, как эффективно сортировать Set после этой инициализации.Я видел, как кто-то использует Collections.sort, но я не знаю об эффективности там.Также помните, что он почти отсортирован.

Что нужно иметь в виду, мне нужно только перебирать как исходную, так и рабочую копию Collection, индексация не требуется.

Я сделал некоторый 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);
    }
}

Массивы pending_additions и pending_removals - единственные, написанные из другого потока.Это мое улучшение с тех пор, как я написал этот пост, поэтому не нужно копировать и восстанавливать весь список.
Мой вопрос остается в силе, должен ли я использовать TreeSet для повышения производительности, должен ли я сделать что-то другое?По сути, я не знаю, как эффективно сортировать TreeSet.Я мог даже предположить, что ArrayList с Collection.sort () более эффективен, но я не знаю.Может кто-нибудь объяснить это.

Также я использую собственный компаратор, в котором есть даже немного математики, так что здесь очень удобно оптимизировать процесс сортировки

Answer 1

Ваша текущая реализация уже использует, что список частично отсортирован:

Javadoc для Collections.sort пишет

Эта реализация относится к методу List.sort (Comparator)

и Javadoc этого метода говорит

Эта реализация представляет собой стабильную, адаптивную, итеративную сортировку слиянием, которая требует гораздо меньше, чем n lg (n) сравнений, когда входной массив частично отсортирован, и в то же время предлагает производительность традиционной сортировки слиянием, когда входной массив упорядочен случайным образом. Если входной массив почти отсортирован, реализация требует приблизительно n сравнений. Требования к временному хранилищу варьируются от небольшой константы для почти отсортированных входных массивов до n / 2 ссылок на объекты для случайно упорядоченных входных массивов.

Реализация имеет одинаковое преимущество в возрастающем и убывающем порядке в своем входном массиве и может использовать в порядке возрастания и убывания в разных частях одного и того же входного массива. Он хорошо подходит для объединения двух или более отсортированных массивов: просто объедините массивы и отсортируйте полученный массив.

Реализация была адаптирована из списка сортировки Тима Питерса для Python (TimSort). Он использует методы Питера Макилроя «Оптимистическая сортировка и теоретико-информационная сложность», в материалах четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, стр. 467-474, январь 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)); }