Предоставляют ли какие-либо библиотеки Java реализацию очереди произвольного доступа?
Автор вопроса: CalumОтветов: 8
Я реализую скользящее окно над потоком событий на Java. Итак, я хочу структуру данных, которая позволяет мне делать следующее:
добавлять в конец структуры данных при возникновении новых событий;
удалять из начала структуры данных при обработке старых событий;
получить стандартный произвольный доступ (size(), get(i)) к элементам структуры данных; в общем, типичный List "прочитан" операции;
эффективен для всех вышеперечисленных операций;
неограничен.
Другой доступ не требуется. И никакой потокобезопасности не требуется.
В настоящее время я делаю это с ArrayList, чтобы привести все в порядок. Но я хочу что-то более эффективное; метод remove(0) (2. выше) неэффективен с ArrayList.
Номера 1. и 2. являются стандартными Queue операции в стиле. Однако реализации Queue в JDK (например, ArrayDeque) не допускайте get(i) в 3.
Итак, мне интересно, есть ли какие-либо библиотеки, которые имеют такую реализацию и подходят для коммерческого использования.
Если нет, я думаю, я прибегну к написанию своего собственного...
Насколько часты эти операции? Возможно, вам придется обменять серьезное пространство на время - например. вы могли бы использовать циклически связанный список с индексом для быстрого поиска (индекс: я забыл название этой структуры; двоичное дерево указателей на 0 и n/2, каждый из которых хранит указатели на середину своей половины и т. д. ). Alex Feinman 05.11.2009
Я столкнулся с этой проблемой и попытался решить ее, скопировав исходный код ArrayDeque и добавив что-то вроде:
E get(index){ return elements[(head + index) % size];}
Ответ 3 · рейтинг 3 · James Black
Если у вас достаточно большой массив, вы можете реализовать очередь с базовым массивом и просто использовать индекс в качестве заголовка списка и использовать оператор мода, чтобы при необходимости можно было обернуться.
Итак, у вас есть круговой массив, поддерживающий функции вставки и удаления.
ОБНОВЛЕНИЕ:
Это быстрая операция для копирования массива в больший массив, поэтому просто удвойте размер, когда приближаетесь к концу, и просто скопируйте массив в качестве шага при выполнении вставки. В целом у вас все равно будет очень быстрый доступ, так как нормой не должно быть увеличение и копирование.
Ответ 4 · рейтинг 2 · Will Hartung
Как быстро события входят в эту очередь и выходят из нее?
С одной стороны, вы можете иметь "достаточно большой" кольцевой буфер.
Хотя технически он "ограничен", вы можете сделать его "неограниченным", увеличив его по мере необходимости.
Точно так же вы можете "сжать" его с точки зрения общей емкости, когда он "тихий".
Но для многих приложений кольцевой буфер емкостью 100, 1000 или даже 10000 элементов практически не ограничен.
Ответ 5 · рейтинг 1 · Jasoon
Единственная библиотека, которая, как мне кажется, реализует такой интерфейс, это LinkedList, но, честно говоря, я не уверен, каковы характеристики производительности.
Ответ 6 · рейтинг 1 · Chris B.
Просто выбрасываю это как альтернативу созданию собственного, поэтому, пожалуйста, примите это с недоверием: в зависимости от того, как часто вам нужен произвольный доступ get(i) и какая производительность вам от него нужна (и насколько велика будет ваша очередь в целом). , вы всегда можете использовать ArrayDeque.toArray()[i], когда вам нужно получить доступ к элементу. toArray() использует System.arraycopy() под прикрытием, что должно быть довольно быстрым для небольших размеров очереди и случайного использования. Помогло бы понять, зачем вам нужен произвольный доступ к очереди и как часто он нужен - возможно, есть другой способ реализовать ваш алгоритм без него.
Ответ 7 · рейтинг 1 · Derek Lewis
Если оно действительно должно быть неограниченным, то что-то вроде ConcurrentSkipListMap может оказаться полезным, если вы назначите возрастающую последовательность каждому событию, чтобы использовать его в качестве ключа на карте. Он предоставил такие методы, как pollFirst/LastEntry. Если вы можете пожертвовать его неограниченной природой, тогда кольцевой буфер может быть тем, что вам нужно.
Ответ 8 · Adrian Panasiuk
Биномиальная куча может иметь O(1) амортизированную вставку и O(log n) амортизированную операцию удаления min; Я считаю, что он также может иметь O (log ** 2 n) амортизированный произвольный доступ. Queue-push вставит элемент в кучу с последовательными целыми числами в качестве ключей.
С помощью rbtree вы можете выполнить отправку в очередь с пессимистичным O (log n) для всех операций вставки, удаления min и произвольного доступа. Это связано с тем, что дерево будет иметь непрерывный набор целых чисел в качестве ключей, а k-й элемент очереди будет элементом дерева с k-м ключом.
