Временная сложность коллекций Java

1. Обзор

В этом туториале мы поговорим о производительности разных коллекций из Java Collection API . Когда мы говорим о коллекциях, мы обычно думаем о структурах данных List, Map и Set , а также об их общих реализациях.

Во-первых, мы рассмотрим понимание сложности Big-O для общих операций. Затем мы покажем реальные цифры времени выполнения некоторых операций сбора.

2. Временная сложность

Обычно, когда мы говорим о временной сложности, мы имеем в виду нотацию Big-O . Проще говоря, нотация описывает, как время выполнения алгоритма растет с увеличением размера входных данных.

Доступны полезные статьи, чтобы узнать больше о теории нотации Big-O и практических примерах Java .

3. Список

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

Здесь мы рассмотрим обзор производительности реализаций ArrayList, LinkedList и CopyOnWriteArrayList .

3.1. ArrayList

ArrayList в Java поддерживается массивом . Это помогает понять внутреннюю логику его реализации. Более подробное руководство по ArrayList доступно в этой статье .

Итак, давайте сначала сосредоточимся на временной сложности общих операций на высоком уровне:

• add() — занимает O(1) времени; однако в худшем случае, когда необходимо создать новый массив и скопировать в него все элементы, это O (n)
• add(index, element) – в среднем выполняется за время O(n)
• get () — всегда является операцией O (1) с постоянным временем.
• remove() – выполняется за линейное время O(n) . Мы должны перебрать весь массив, чтобы найти элемент, подходящий для удаления.
• indexOf() — также работает в линейном времени. Он перебирает внутренний массив и проверяет каждый элемент один за другим, поэтому временная сложность этой операции всегда требует O(n) времени.
• contains() — реализация основана на indexOf(), поэтому она также будет выполняться за время O(n) .

3.2. КопиОнВритеАррайлист

Такая реализация интерфейса List удобна при работе с многопоточными приложениями . Это потокобезопасно и хорошо объяснено в этом руководстве здесь .

Вот обзор производительности нотации Big-O для CopyOnWriteArrayList :

• add () — зависит от позиции, в которую мы добавляем значение, поэтому сложность составляет O (n)
• get () — это O (1) операция с постоянным временем
• remove() – занимает O(n) времени
• contains() – аналогично, сложность O(n)

Как мы видим, использование этой коллекции очень затратно из-за характеристик производительности метода add() .

3.3. Связанный список

LinkedList — это линейная структура данных, состоящая из узлов, содержащих поле данных и ссылку на другой узел . Дополнительные о функциях и возможностях LinkedList см. в этой статье здесь .

Приведем среднюю оценку времени, необходимого для выполнения некоторых основных операций:

• add() — добавляет элемент в конец списка. Он обновляет только хвост, и, следовательно, его сложность O (1) с постоянным временем.
• add(index, element) – в среднем выполняется за время O(n)
• get() — поиск элемента занимает O(n) времени.
• remove(element) — чтобы удалить элемент, нам сначала нужно его найти. Эта операция O(n).
• remove(index) — чтобы удалить элемент по индексу, нам сначала нужно перейти по ссылкам с самого начала; следовательно, общая сложность равна O(n).
• contains() - также имеет временную сложность O(n)

3.4. Разогрев JVM

Теперь, чтобы доказать теорию, давайте поиграем с реальными данными. Чтобы быть более точным, приведем результаты теста JMH (Java Microbenchmark Harness) наиболее распространенных операций сбора .

Если мы не знакомы с инструментом JMH, мы можем ознакомиться с этим полезным руководством .

Сначала приведем основные параметры наших бенчмарк-тестов:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 10)
public class ArrayListBenchmark {
}

Затем мы установим количество итераций прогрева равным 10 . Обратите внимание, что мы также хотим видеть среднее время выполнения наших результатов в микросекундах.

3.5. Сравнительные тесты

Теперь пришло время запустить наши тесты производительности. Во-первых, мы начнем с ArrayList :

@State(Scope.Thread)
public static class MyState {

    List<Employee> employeeList = new ArrayList<>();

    long iterations = 100000;

    Employee employee = new Employee(100L, "Harry");

    int employeeIndex = -1;

    @Setup(Level.Trial)
    public void setUp() {
        for (long i = 0; i < iterations; i++) {
            employeeList.add(new Employee(i, "John"));
        }

        employeeList.add(employee);
        employeeIndex = employeeList.indexOf(employee);
    }
}

Внутри нашего ArrayListBenchmark мы добавляем класс State для хранения исходных данных.

Здесь мы создаем ArrayList объектов Employee . Затем мы инициализируем его 100 000 элементов внутри метода setUp() . @State указывает, что тесты @Benchmark имеют полный доступ к объявленным в нем переменным в том же потоке. ``

Наконец, пришло время добавить контрольные тесты для методов add(), contains(), indexOf(), remove() и get() :

@Benchmark
public void testAdd(ArrayListBenchmark.MyState state) {
    state.employeeList.add(new Employee(state.iterations + 1, "John"));
}

@Benchmark
public void testAddAt(ArrayListBenchmark.MyState state) {
    state.employeeList.add((int) (state.iterations), new Employee(state.iterations, "John"));
}

@Benchmark
public boolean testContains(ArrayListBenchmark.MyState state) {
    return state.employeeList.contains(state.employee);
}

@Benchmark
public int testIndexOf(ArrayListBenchmark.MyState state) {
    return state.employeeList.indexOf(state.employee);
}

@Benchmark
public Employee testGet(ArrayListBenchmark.MyState state) {
    return state.employeeList.get(state.employeeIndex);
}

@Benchmark
public boolean testRemove(ArrayListBenchmark.MyState state) {
    return state.employeeList.remove(state.employee);
}

3.6. Результаты теста

Все результаты представлены в микросекундах:

Benchmark                        Mode  Cnt     Score     Error
ArrayListBenchmark.testAdd       avgt   20     2.296 ±   0.007
ArrayListBenchmark.testAddAt     avgt   20   101.092 ±  14.145
ArrayListBenchmark.testContains  avgt   20   709.404 ±  64.331
ArrayListBenchmark.testGet       avgt   20     0.007 ±   0.001
ArrayListBenchmark.testIndexOf   avgt   20   717.158 ±  58.782
ArrayListBenchmark.testRemove    avgt   20   624.856 ±  51.101

Из результатов мы узнаем, что методы testContains() и testIndexOf() запускаются примерно в одно и то же время . Мы также можем ясно видеть огромную разницу между оценками методов testAdd() и testGet() по сравнению с остальными результатами. Добавление элемента занимает 2,296 мкс, а его получение — 0,007 мкс.

Кроме того, поиск или удаление элемента занимает примерно 700 микросекунд. Эти цифры являются доказательством теоретической части, где мы узнали, что add() и get() имеют временную сложность O(1) , а остальные методы — O(n) . n=10 000 элементов в нашем примере.

Точно так же мы можем написать те же тесты для коллекции CopyOnWriteArrayList . Все, что нам нужно сделать, это заменить ArrayList в employeeList экземпляром CopyOnWriteArrayList .

Вот результаты эталонного теста:

Benchmark                          Mode  Cnt    Score     Error
CopyOnWriteBenchmark.testAdd       avgt   20  652.189 ±  36.641
CopyOnWriteBenchmark.testAddAt     avgt   20  897.258 ±  35.363
CopyOnWriteBenchmark.testContains  avgt   20  537.098 ±  54.235
CopyOnWriteBenchmark.testGet       avgt   20    0.006 ±   0.001
CopyOnWriteBenchmark.testIndexOf   avgt   20  547.207 ±  48.904
CopyOnWriteBenchmark.testRemove    avgt   20  648.162 ± 138.379

Здесь, опять же, цифры подтверждают теорию. Как мы видим, testGet() в среднем выполняется за 0,006 мс, что можно считать O(1) . Сравнивая с ArrayList , мы также замечаем значительную разницу между результатами метода testAdd() , так как здесь у нас есть сложность O(n) для метода add() по сравнению с O(1) ArrayList.

Мы ясно видим линейный рост времени, так как показатели производительности составляют 878,166 по сравнению с 0,051 .

Теперь пришло время LinkedList :

Benchmark        Cnt     Score       Error
testAdd          20     2.580        ± 0.003
testContains     20     1808.102     ± 68.155
testGet          20     1561.831     ± 70.876 
testRemove       20     0.006        ± 0.001

Из оценок видно, что добавление и удаление элементов в LinkedList происходит довольно быстро.

Кроме того, существует значительный разрыв в производительности между операциями добавления/удаления и получения/содержания.

4. Карта

В последних версиях JDK мы наблюдаем значительное улучшение производительности для реализаций Map , например, замена LinkedList сбалансированной структурой узлов дерева в HashMap и внутренних реализаций LinkedHashMap . Это сокращает время поиска элемента в наихудшем случае с O(n) до O(log(n)) во время коллизий HashMap .

Однако, если мы реализуем правильные методы .equals() и .hashcode() , коллизии маловероятны.

Чтобы узнать больше о коллизиях HashMap , ознакомьтесь с этой статьей . Из статьи мы также узнаем, что сохранение и извлечение элементов из HashMap занимает постоянное время O(1) .

4.1. Тестирование операций O(1)

Теперь давайте посмотрим на некоторые реальные цифры. Во-первых, HashMap :

Benchmark                         Mode  Cnt  Score   Error
HashMapBenchmark.testContainsKey  avgt   20  0.009 ± 0.002
HashMapBenchmark.testGet          avgt   20  0.011 ± 0.001
HashMapBenchmark.testPut          avgt   20  0.019 ± 0.002
HashMapBenchmark.testRemove       avgt   20  0.010 ± 0.001

Как мы видим, цифры доказывают постоянное время O(1) для выполнения перечисленных выше методов. Теперь давайте сравним результаты теста HashMap с оценками других экземпляров карты .

Для всех перечисленных методов у нас есть O(1) для HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap и ConcurrentHashMap.

Представим результаты остальных тестовых баллов в виде таблицы:

Benchmark      LinkedHashMap  IdentityHashMap  WeakHashMap  ConcurrentHashMap
testContainsKey    0.008         0.009          0.014          0.011
testGet            0.011         0.109          0.019          0.012
testPut            0.020         0.013          0.020          0.031
testRemove         0.011         0.115          0.021          0.019

Из выходных чисел мы можем подтвердить требования временной сложности O (1) .

4.2. Тестирование операций O(log(n))

Для древовидной структуры TreeMap и ConcurrentSkipListMap время операций put(), get(), remove() и containsKey() равно O(log(n)).

Здесь мы хотим убедиться, что наши тесты производительности будут выполняться примерно за логарифмическое время . По этой причине мы будем непрерывно инициализировать карты с n = 1000, 10 000, 100 000, 1 000 000 элементов.

В данном случае нас интересует общее время выполнения:

items count (n)         1000      10,000     100,000   1,000,000
all tests total score   00:03:17  00:03:17   00:03:30  00:05:27

Когда n=1000, общее время выполнения составляет 00:03:17 миллисекунд. При n=10 000 время почти не изменилось, 00:03:18 мс. n=100 000 имеет незначительное увеличение в 00:03:30 . И, наконец, когда n=1 000 000, выполнение завершается через 00:05:27 мс .

После сравнения чисел времени выполнения с функцией log(n) каждого n мы можем подтвердить, что корреляция обеих функций совпадает.

5. Установить

Как правило, Set представляет собой набор уникальных элементов. Здесь мы рассмотрим реализации HashSet , LinkedHashSet , EnumSet, TreeSet, CopyOnWriteArraySet и ConcurrentSkipListSet интерфейса Set .

Чтобы лучше понять внутренности HashSet , это руководство поможет вам.

Теперь давайте перейдем к представлению значений временной сложности. Для HashSet , LinkedHashSet и EnumSet операции add (), remove() и contains() стоят постоянно O(1) времени благодаря внутренней реализации HashMap .

Точно так же TreeSet имеет временную сложность O (log (n)) для операций, перечисленных в предыдущей группе. Это связано с реализацией TreeMap . Временная сложность для ConcurrentSkipListSet также составляет O(log(n)) времени, так как она основана на структуре данных списка пропуска.

Для CopyOnWriteArraySet методы add (), remove() и contains() имеют среднюю временную сложность O(n).

5.1. Методы испытаний

Теперь давайте перейдем к нашим тестам производительности:

@Benchmark
public boolean testAdd(SetBenchMark.MyState state) {
    return state.employeeSet.add(state.employee);
}

@Benchmark
public Boolean testContains(SetBenchMark.MyState state) {
    return state.employeeSet.contains(state.employee);
}

@Benchmark
public boolean testRemove(SetBenchMark.MyState state) {
    return state.employeeSet.remove(state.employee);
}

Мы оставим остальные конфигурации тестов как есть.

5.2. Сравнение чисел

Давайте посмотрим на поведение оценки выполнения во время выполнения для HashSet и LinkedHashSet , имеющих n = 1000; 10 000; 100 000 предметов.

Для HashSet цифры следующие:

Benchmark      1000    10,000    100,000
.add()         0.026   0.023     0.024
.remove()      0.009   0.009     0.009
.contains()    0.009   0.009     0.010

Точно так же результаты для LinkedHashSet :

Benchmark      1000    10,000    100,000
.add()         0.022   0.026     0.027
.remove()      0.008   0.012     0.009
.contains()    0.008   0.013     0.009

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

В результате мы подтверждаем, что все протестированные методы работают с постоянным временем O(1) .

6. Заключение

В этой статье представлена временная сложность наиболее распространенных реализаций структур данных Java.

Мы видели реальную производительность каждого типа коллекции во время выполнения тестов производительности JVM. Мы также сравнили производительность одних и тех же операций в разных коллекциях. В результате мы научились выбирать правильную коллекцию, соответствующую нашим потребностям.

Как обычно, полный код для этой статьи доступен на GitHub .