Итак, в каком-то вопросе мне потребовалось реализовать следующее: структура данных фиксированного размера (n = 10), которая всегда упорядочена (по убыванию, не имеет значения), безопасна для потоков и поддерживает произвольный доступ.
Мое решение было - используя TreeSet, при каждом добавлении элемента, если уже есть элементы n, удалите наименьший элемент (если новый элемент больше его) и добавьте новый элемент.В противном случае просто добавьте новый элемент.При доступе к случайному индексу используйте итератор TreeSet для итерации до получения необходимого индекса.
Мне не очень нравится это решение.Поэтому я подумал о другом решении: использовать ArrayList, построенный с размером n.Всякий раз, когда вы пытаетесь добавить элемент, выполните Collections.binarySearch() для элемента и вставьте его, если он не существует, используя индекс, возвращенный из binarySearch.Если после добавления элемента длина списка больше n (на самом деле равна n+1), удалите наименьший элемент (который находится в конце списка).Таким образом, мы получаем log (n) для добавления (так же, как TreeSet из предыдущего решения), и произвольный доступ равен O (1).Единственное, что мне не нравится в этом, это то, что add() для произвольного индекса в середине списка требует сдвига всех элементов после него.(хорошо работает для маленьких n, но для больших n, может быть, нет?)
Для обоих решений я использую ReentrantReadWriteLock - приобретаем writeLock () для add и readLock () для операций get () / read.
Есть ли лучшее решение?