Java collection o notation

Сложность времени коллекций Java

В этом руководствеwe’ll talk about the performance of different collections from the Java Collection API. Когда мы говорим о коллекциях, мы обычно думаем о структурах данныхList, Map, иSet и их общих реализациях.

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

2. Сложность времени

Обычноwhen we talk about time complexity, we refer to Big-O notation. Проще говоря, нотация описывает, как время выполнения алгоритма увеличивается с размером входных данных.

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

3. Listс

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

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

3.1. ArrayListс

The ArrayList in Java is backed by an array. Это помогает понять внутреннюю логику его реализации. Доступно более подробное руководство дляArrayListin this article.

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

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

3.2. CopyOnWriteArrayListс

Эта реализация интерфейсаList —very useful when working with multi-threaded applications. Это потокобезопасный и хорошо объясненный вthis guide here.

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

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

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

3.3. LinkedListс

LinkedList is a linear data structure which consists of nodes holding a data field and a reference to another node. Чтобы узнать больше о функциях и возможностяхLinkedList, посмотритеthis article here.

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

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

3.4. Разогрев JVM

Теперь, чтобы доказать теорию, давайте поиграемся с реальными данными. To be more precise, we’ll present the JMH (Java Microbenchmark Harness) test results of the most common collection operations.

Если вы не знакомы с инструментом JMH, посмотрите этотuseful guide.

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

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

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

3.5. Контрольные тесты

Пришло время провести тесты производительности. Сначала мы начнем сArrayList:

@State(Scope.Thread) public static class MyState < ListemployeeList = 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 объектов. После,we initialize it with 100.000 items inside of the setUp() method. The @State indicates that the @Benchmark tests have full access to the variables declared in it within the same thread.

Наконец, пора добавить тесты производительности для методов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)

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

From the results we can learn, that testContains() and testIndexOf() methods run in approximately the same time. Мы также можем ясно видеть огромную разницу между оценками метода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). Comparing to ArrayList, we also notice the significant difference between testAdd() method results. As we have here O(n) complexity for the add() method versus ArrayList’s O(1).

We can clearly see the linear growth of the time, as performance numbers are 878.166 compared to 0.051.

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. Mapс

В последних версиях JDK мы наблюдаем значительное улучшение производительности для реализацийMap, таких как заменаLinkedList на сбалансированную древовидную структуру узлов в синтернальных реализацияхHashMap, LinkedHashMap . This shortens the element lookup worst-case scenario from O(n) to O(log(n)) time during the HashMap collisions.

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

Чтобы узнать больше о столкновенияхHashMap, просмотритеthis write-up. From the write-up, we can also learn, that storing and retrieving elements from the HashMap takes constant O(1) time.

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

As we see, the numbers prove the O(1) constant time for running the methods listed above. Теперь давайте сравним результаты тестаHashMap с оценками других экземпляровMap.

Для всех перечисленных методовwe have O(1) for HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap and 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 and ConcurrentSkipListMap the put(), get(), remove(), containsKey() operations time is O(log(n)).

[.pl-smi] # Здесьwe want to make sure that our performance tests will run approximately in logarithmic time. По этой причине мы непрерывно инициализируем карты с 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

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

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

5. Setс

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

Чтобы лучше понять внутреннее устройствоHashSet, здесь вам поможетthis guide.

Теперь давайте забегаем вперед и представим числа временной сложности. For HashSet, LinkedHashSet, and EnumSet the add(), remove() and contains() operations cost constant O(1) time. Thanks to the internal HashMap implementation.с

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

ДляCopyOnWriteArraySet, методыadd(), remove() andcontains() имеют среднюю временную сложность 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)

Кроме того, мы оставляем оставшиеся тестовые конфигурации как есть.

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. Заключение

В этой статьеwe present the time complexity of the most common implementations of the Java data structures.

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

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

Источник