В этой статье представлен GapList, реализация, которая стремится объединить сильные стороны ArrayList и LinkedList. Мы покажем, как это реализовано, чтобы обеспечить эффективный произвольный доступ к элементам по индексу (как это делает ArrayList) и в то же время эффективное добавление и удаление элементов в и из головы и хвоста списка (как это делает LinkedList).
Фон
Платформа коллекций Java относится к наиболее часто используемым функциям в стандартной библиотеке Java. Почти каждое приложение использует его для обработки некоторых коллекций данных.
Структура включает в себя различные интерфейсы, а также реализации этих интерфейсов. Безусловно, самым популярным интерфейсом является java.util.List, который позволяет обрабатывать массив элементов в виде списка, который может увеличиваться и уменьшаться по мере необходимости.
Стандартная библиотека Java предлагает две основные реализации интерфейса List: ArrayList и LinkedList. Как объясняется в http://docs.oracle.com/javase/tutorial/collections/implementations/list.html, вы обычно будете использовать ArrayList в качестве реализации List общего назначения, поскольку обычно она быстрее и потребляет меньше памяти.
Но в цитируемом документе также упоминается, что выполнение операций добавления / удаления в начале или внутри ArrayList будет работать не очень хорошо. Возникает вопрос: действительно ли ArrayList подходит для реализации List общего назначения?
мотивация
Прежде чем углубляться в детали, мы хотим взглянуть на ситуацию, с которой вы можете столкнуться в повседневной жизни программиста. Это проиллюстрирует, что некоторые потребности не могут быть удовлетворены с помощью ArrayList или LinkedList.
Рассмотрим следующий вариант использования: мы пишем программное обеспечение, которое должно анализировать входящие события. Анализ всегда выполняется в окне фиксированного размера, содержащем последние поступившие события. Таким образом, чтобы поддерживать эти окна фиксированного размера, нам нужна структура данных, которая поддерживает эффективное добавление элементов в начале и удаление элементов в конце. Затем анализ выполняется методами, которые требуют произвольного доступа к списку — либо потому, что его проще реализовать, либо потому, что он действительно нужен.
Давайте рассмотрим две наши альтернативы:
- ArrayList будет лучше в части анализа, но будет плохо вести себя при добавлении / удалении событий
- LinkedList преуспел бы в добавлении и удалении элементов, но плохо себя вел в части анализа
Какую реализацию вы бы выбрали? Как хороший программист это не будет легким выбором, потому что вы знаете, что ваше решение не будет хорошо обрабатывать все случаи. Конечно, вы знаете, что вам не нужно заботиться о преждевременной оптимизации, но, тем не менее, это может вызвать у вас хотя бы плохое предчувствие. Может случиться так, что вы проводите некоторые измерения производительности, чтобы не спать спокойно ночью, или пишете свои проблемы в проектной документации или в комментариях Javadoc, чтобы показать коллегам, что вы поняли последствия того, что вы сделали.
Поэтому, что бы вы ни делали, решение не будет оптимальным, и вы, возможно, потратили некоторое время на измерение производительности, написание проблем или выполнение некоторых мозговых работ. И вы можете продолжать задаваться вопросом, как вы могли бы найти лучшее решение, которым вы могли бы действительно гордиться.
Но на самом деле вы хотели бы иметь стандартные библиотеки, которые были бы достаточно быстрыми, чтобы их можно было без проблем использовать в качестве строительных блоков для других компонентов. И тут на помощь приходит GapList: он будет превосходен во всех операциях.
Обзор ArrayList
Реализация GapList является улучшением ArrayList. Поэтому сначала мы посмотрим на реализацию ArrayList, чтобы понять, почему производительность некоторых операций имеет тенденцию быть плохой.
На следующем рисунке показано, как данные хранятся в ArrayList.
Все элементы хранятся в массиве Java. Первый элемент имеет индекс 0, второй — индекс 1 и т. Д. Чтобы предотвратить новое выделение при каждой вставке, выделенный массив обычно больше сохраненного количества элементов, а переменная размера используется для отслеживания используемых элементов.
Если мы посмотрим на иллюстрацию, станет совершенно очевидно, почему разные операции имеют разные характеристики производительности: операции в конце выполняются очень быстро, потому что данные не должны копироваться, тогда как операции в начале требуют дорогостоящей операции копирования.
Если мы проанализируем некоторые операции подряд, мы увидим, что последующие операции не могут получить прибыль от предыдущих операций. Таким образом, в следующем примере элементы справа от точки вставки должны быть перемещены дважды для двух последующих операций вставки.
Как следствие, ArrayList не подходит для итерации по списку и добавления или удаления элементов. Если вам действительно нужно перебрать ArrayList и изменить его, вам лучше создать новый экземпляр ArrayList во время взаимодействия.
Тот факт, что ArrayList предлагает очень асимметричное поведение производительности, также может стать проблематичным, если операции выполняются через графический интерфейс, где пользователь заметил бы, что операция в конце выполняется намного быстрее, чем та же операция в начале списка.
Введение в GapList
Чтобы решить выявленные проблемы, мы представляем GapList как еще одну реализацию интерфейса java.util.List. В качестве основных функций GapList предоставляет
- Эффективный доступ к элементам по индексу
- Постоянное время вставки в начало и конец списка
- Эксплуатировать местность ссылки часто встречается в приложениях
Давайте посмотрим, как реализован GapList для предоставления этих функций.
Если мы сравним, как ArrayList обрабатывает различные виды вставок, мы можем быстро найти решение, гарантирующее быструю вставку как в начале, так и в конце списка. Вместо того, чтобы перемещать все элементы, чтобы получить место в индексе 0, мы оставляем существующие элементы на месте и записываем элементы в конец выделенного массива, если осталось место. Таким образом, мы в основном используем массив как вращающийся буфер.
Для доступа к элементам в правильном порядке, мы должны запомнить начальную позицию первого элемента и использовать операцию по модулю для вычисления физического индекса из логического:
PhysIndex = (начало + индекс)% емкости
Чтобы использовать локальность ссылок, мы разрешаем включать пробел в хранилище элементов списка. Разрыв, образованный неиспользуемыми слотами в массиве поддержки, может быть где угодно в списке. Существует не более одного разрыва, но также не может быть ни одного.
Этот пробел помогает вам воспользоваться преимуществами ссылки на список, поэтому, если вы добавите элемент в середину списка, последующее добавление в середину будет быстрым.
Если GapList не имеет пробела, он создается при необходимости. Если разрыв находится не в том месте, он перемещается. Но если операции происходят рядом друг с другом, скопировать нужно всего несколько данных.
GapList также позволяет удалять элементы в начале и в конце без какого-либо перемещения элементов.
Удаления в середине обрабатываются аналогично вставкам: существующий разрыв может быть перемещен или исчезнуть, если больше не нужен.
Исполнение GapList
Теперь мы представляем контрольные показатели, сравнивающие GapList, ArrayList и LinkedList для некоторых распространенных операций.
Давайте сначала посмотрим на самую операцию импорта: получение элементов.
Мы можем видеть, что производительность GapList даже немного лучше, чем ArrayList при получении элементов. Производительность LinkedList в 2000 раз хуже при случайном доступе к элементам (обратите внимание, что все диаграммы используют логарифмическую ось).
Следующая диаграмма показывает производительность для добавления элементов.
GapList показывает хорошую производительность независимо от местоположения вставки, тогда как ArrayList в 3000 раз медленнее, если добавления происходят в начале списка.
В случае совершенно случайных операций добавления и удаления GapList немного медленнее, чем ArrayList. Это то, что мы ожидаем, так как нет ссылочной локации, которую GapList может использовать, а реализация GapList более сложна.
Но что произойдет, если последующие операции происходят рядом друг с другом? Или мы даже перебираем список?
Мы видим, что производительность GapList улучшается по мере того, как становятся более локальными последующие операции, и GapList может работать в 100 раз быстрее, чем ArrayList. Это также почти так же быстро, как LinkedList в итерации.
Производительность операций удаления аналогична показанным операциям добавления.
Подводя итог, мы увидели, что GapList предлагает отличную производительность в любом тестовом случае:
- это так же быстро, как ArrayList в получении элементов, который является наиболее важной операцией
- это так же быстро, как LinkedList в добавлении / удалении элементов в начале / конце списка
- это так же быстро, как ArrayList для добавления / удаления элементов в случайных местах
- это так же быстро, как LinkedList в добавлении / удалении элементов путем итерации
Особенности GapList
GapList был разработан как замена для ArrayList и LinkedList:
- GapList реализует интерфейс java.util.Deque, который реализован не ArrayList, а только LinkedList.
- Все открытые методы, предоставляемые ArrayList, также реализуются GapList (sureCapacty, trimToSize).
Известным недостатком Java Collections Framework является тот факт, что нет поддержки примитивных типов. Так что, если вам нужно сохранить кучу целых чисел, вы получите List <Integer>. Этот подход использует гораздо больше памяти, чем хранение данных в простом int [].
GapList также предлагает реализации для всех простых типов данных, например IntGapList.
Поскольку классы для примитивных типов данных генерируются из универсальной версии с использованием механизма шаблонов, некоторые массовые операции были добавлены непосредственно в GapList. Они включают в себя remove (), move (), copy (), но также sort (), rotate () или shuffle ().
GapList не является потокобезопасным. Также следует учитывать, что использование ссылочной локали работает только при наличии локализации: если два потока работают над разными частями списка, эта оптимизация может даже оказать негативное влияние на производительность, поскольку разрыв должен быть перемещен назад и вперед. Конечно, это также может произойти с одним потоком, но это менее вероятно.
MaxList — вариант использования для GapList
Теперь мы вернемся к нашему примеру, представленному как мотивация, и покажем, как GapList может помочь нам создать действительно простую и мощную реализацию.
Поскольку и добавление и удаление выполняются быстро, мы можем легко использовать GapList в качестве вращающегося буфера фиксированного размера. Элементы могут быть добавлены, пока не будет достигнут максимальный размер. Если должен быть добавлен другой элемент, первый элемент удаляется перед добавлением.
Поскольку все наши соображения производительности решаются с помощью GapList, реализация описанной функциональности довольно проста. По сути, вы должны переопределить методы add, чтобы гарантировать, что список никогда не будет превышать заданный предел.
add(T elem) {
if (size() == maxSize()) {
removeFirst();
}
super.add(elem)
}
Вывод
GapList предлагает отличную производительность в любой ситуации, что делает его превосходящим ArrayList и LinkedList. Это позволяет использовать GapList в качестве замены для ArrayList и LinkedList.
GapList, MaxList и реализации, работающие с примитивными типами данных, являются частью библиотеки коллекций Brownies и могут быть загружены с http://www.magicwerk.org/collections .