Тема Java Collections API одна из основополагающих при изучении. На моей памяти ни одно собеседование на должность java-программиста не обходилось без выяснения тонкостей использования того или иного класса коллекций. В сети и книгах очень много информации по этой теме, однако как правило слабо охватываются вопросы связанные с производительностью и потреблением ресурсов. Соответственно, создаются некоторые сложности при выборе класса для применения в том или ином случае, что особенно критично при разработке высоконагруженных систем. Чтобы выбор был немного более прозрачным, я решил провести небольшое исследование по определению производительности коллекций при выполнении основных операций над их элементами. Также приведу небольшое сравнение показателей некоторых коллекций Java с классами-аналогами из .Net.
В качестве вступления пара слов об интерфейсах, реализуемых коллекциями. Есть 3 базовых интерфейса:
Эти интерфейсы реализованы множеством классов. Из названия класса коллекции можно судить об ее особенностях. Возьмем для примера класс LinkedHashSet:
Рассмотрим несколько основных реализаций и функции доступные для каждой:
* — в Map-классах для добавления элементов используется метод put, который можно трактовать и как вставку (insert). В тестах я использовал этот метод в категориях «добавление элемента» и «вставка элемента».
В большей части таблицы все понятно. Хочется заострить внимание на ячейках с "±". Это означает, что функция для коллекции доступна, но ее использование требует большей бдительности, т.к. может повлечь большую трату ресурсов процессора. Рассмотрим сначала процедуру вставки элемента применительно к классам ArrayList и LinkedList. Для ArrayList алгоритм вставки в i-ю позицию будет выглядеть примерно так:
— скопировать элементы с индексами i..size-1 («хвост массива») во временный массив;
— увеличить длину массива на 1;
— присвоить i-му элементу новое значение;
— скопировать все элементы из временного массива обратно, начиная с индекса i+1.
Как можно догадаться — при увеличении размера массива операция вставки элемента в произвольную позицию будет занимать большее время. То же самое будет происходить и при удалении произвольного элемента. Это время возрастает пропорционально размеру массива и индексу вставляемого элемента. Соответственно самой ресурсоемкой будет вставка(удаление) элемента в начало массива (индекс 0). Далее в тестах приводится количественная оценка этого времени. Забегая вперед, следует сказать, что не стоит совсем отказываться от использования операций вставки. Если необходима не очень частая вставка элементов и размер массива не превышает 5-10 тыс. элементов, то производительность будет на приемлемом уровне.
Для LinkedList ситуация несколько иная: массив построен не по индексу, а цепочкой, т.е. каждый элемент имеет ссылки на соседние. Операция произвольной вставки будет потреблять времени немногим меньше, чем в ArrayList и также время будет расти пропорционально размеру массива. Основная потеря времени в этом случае происходит при поиске позиции, в которую необходимо вставить элемент. Т.к. индекс отсутствует, то позиция определяется перебором i элементов от головы или size-i от хвоста массива. Сама же процедура вставки сводится к изменению ссылок в двух соседних и вставляемом элементе. Основной плюс такой организации — это возможность «дешево» вставлять/удалять элементы в начало массива, независимо от его длины.
Исходя из вышеописанного, процедура выборки произвольного элемента по индексу будет быстро отрабатываться для ArrayList и намного медленней для LinkedList. Причем время выборки для ArrayList незначительно зависит от количества элементов в массиве, а для LinkedList оно растет пропорционально.
Железо: AMD Athlon 64 X2 3800+, 4GB ОЗУ.
Софт: Windows Vista Bussines 32, Java 1.6.0_20, .NET v4.
Исследуемые параметры: основные функции чтения/записи для коллекций (см. таблицу выше).
Методика:
Выводы: предоставлю сделать самим читателям, т.к. на графиках достаточно информации, чтобы оценить использование различных коллекций в том или ином случае.
Как можно увидеть — результаты в среднем примерно равны. Небольшой перевес в сторону java наблюдается лишь в коллекциях с размером более 500 000 элементов.
Коллекции в java
В качестве вступления пара слов об интерфейсах, реализуемых коллекциями. Есть 3 базовых интерфейса:
- Set — множество уникальных элементов;
- List — упорядоченный массив элементов;
- Map — ассоциативный массив вида ключ=>значение, где ключ и значение могут быть объектами любого класса. Ключи в списке должны быть уникальными.
Эти интерфейсы реализованы множеством классов. Из названия класса коллекции можно судить об ее особенностях. Возьмем для примера класс LinkedHashSet:
- слово Set говорит о реализации соответствующего интерфейса;
- Linked — означает, что элементы связаны между собой «по цепочке», т.е. каждый имеет ссылки на своих соседей. В данной реализации это позволяет сохранить последовательность элементов, в которой они были добавлены в коллекцию;
- Hash — говорит о том, что коллекция базируется на значениях, зависящих от значений Hash-кода для каждого элемента. Это позволяет производить быструю проверку наличия элемента в коллекции.
Функционал коллекций
Рассмотрим несколько основных реализаций и функции доступные для каждой:
- HashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов при обходе(итерации) не определен. Не допускает дубликатов.
- TreeSet — множество отсортированное в натуральном порядке. Не допускает дубликатов.
- LinkedHashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов соответствует последовательности добавления в коллекцию.
- LinkedList — связанный список. Каждый элемент ссылается на 2 соседних. Порядок элементов соответствует последовательности добавления.
- ArrayList — индексированный список. Каждому элементу соответствует индекс типа int.
- HashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов не определен.
- LinkedHashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов соответствует последовательности добавления.
- TreeMap — ассоциативный массив. В качестве уникальных ключей используется отсортированное в натуральном порядке множество.
| Функции | HashSet | TreeSet | LinkedHashSet | LinkedList | ArrayList | HashMap | LinkedHashMap | TreeMap |
| Добавление элемента (add/put)* | + | + | + | + | + | + | + | + |
| Проверка наличия элемента (contains) | + | + | + | - | - | + | + | + |
| Последовательный доступ к элементу (итерация) | + | + | + | + | + | + | + | + |
| Чтение произвольного элемента (get) | - | - | - | ± | + | + | + | + |
| Вставка элемента | - | - | - | + | ± | + | + | + |
* — в Map-классах для добавления элементов используется метод put, который можно трактовать и как вставку (insert). В тестах я использовал этот метод в категориях «добавление элемента» и «вставка элемента».
В большей части таблицы все понятно. Хочется заострить внимание на ячейках с "±". Это означает, что функция для коллекции доступна, но ее использование требует большей бдительности, т.к. может повлечь большую трату ресурсов процессора. Рассмотрим сначала процедуру вставки элемента применительно к классам ArrayList и LinkedList. Для ArrayList алгоритм вставки в i-ю позицию будет выглядеть примерно так:
— скопировать элементы с индексами i..size-1 («хвост массива») во временный массив;
— увеличить длину массива на 1;
— присвоить i-му элементу новое значение;
— скопировать все элементы из временного массива обратно, начиная с индекса i+1.
Как можно догадаться — при увеличении размера массива операция вставки элемента в произвольную позицию будет занимать большее время. То же самое будет происходить и при удалении произвольного элемента. Это время возрастает пропорционально размеру массива и индексу вставляемого элемента. Соответственно самой ресурсоемкой будет вставка(удаление) элемента в начало массива (индекс 0). Далее в тестах приводится количественная оценка этого времени. Забегая вперед, следует сказать, что не стоит совсем отказываться от использования операций вставки. Если необходима не очень частая вставка элементов и размер массива не превышает 5-10 тыс. элементов, то производительность будет на приемлемом уровне.
Для LinkedList ситуация несколько иная: массив построен не по индексу, а цепочкой, т.е. каждый элемент имеет ссылки на соседние. Операция произвольной вставки будет потреблять времени немногим меньше, чем в ArrayList и также время будет расти пропорционально размеру массива. Основная потеря времени в этом случае происходит при поиске позиции, в которую необходимо вставить элемент. Т.к. индекс отсутствует, то позиция определяется перебором i элементов от головы или size-i от хвоста массива. Сама же процедура вставки сводится к изменению ссылок в двух соседних и вставляемом элементе. Основной плюс такой организации — это возможность «дешево» вставлять/удалять элементы в начало массива, независимо от его длины.
Исходя из вышеописанного, процедура выборки произвольного элемента по индексу будет быстро отрабатываться для ArrayList и намного медленней для LinkedList. Причем время выборки для ArrayList незначительно зависит от количества элементов в массиве, а для LinkedList оно растет пропорционально.
Условия тестирования
Железо: AMD Athlon 64 X2 3800+, 4GB ОЗУ.
Софт: Windows Vista Bussines 32, Java 1.6.0_20, .NET v4.
Исследуемые параметры: основные функции чтения/записи для коллекций (см. таблицу выше).
Методика:
- для каждого исследуемого класса программа с набором процедур компилировалась отдельно;
- запуск производился 5 раз для каждого размера коллекции и в зачет шли средние арифметические от измеренных времен;
- в java время измерялось с помощью функции System.nanoTime(), в c#(.Net) — DateTime.Now();
- операции «проверка наличия элемента (contains)» и «чтение произвольного элемента (get)» выполнялись по 100 000 раз для каждого размера массива, элемент(индекс) для поиска генерировался случайно;
- в качестве элементов коллекций использовалась строка вида: «testString» + i. Эта же строка использовалась в качестве индекса для Map-коллекций.
- для java-коллекций с помощью профайлера был определен размер на основании данных об используемой памяти до создания коллекции и после.
Результаты тестирования
Размеры java-коллекций в зависимости от количества элементов
Сравнительные тесты java-коллекций
Выводы: предоставлю сделать самим читателям, т.к. на графиках достаточно информации, чтобы оценить использование различных коллекций в том или ином случае.
Сравнительные тесты java vs .net
Как можно увидеть — результаты в среднем примерно равны. Небольшой перевес в сторону java наблюдается лишь в коллекциях с размером более 500 000 элементов.
Литература
- The Collections Framework API Reference
- Исходный код классов коллекций Java SE.