Linkedlist java сложность операций

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

В этом уроке мы поговорим о производительности различных коллекций из API Java Collection . Когда мы говорим о коллекциях, мы обычно думаем о структурах данных 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) время
• get() – всегда постоянное время O(1) операция
• remove() – выполняется в линейном O(n) времени. Мы должны перебрать весь массив, чтобы найти элемент, подходящий для удаления
• indexOf() – также выполняется в линейном времени. Он перебирает внутренний массив и проверяет каждый элемент один за другим. Таким образом, временная сложность для этой операции всегда требует O(n) времени
• содержит() – реализация основана на indexOf() . Таким образом, он также будет работать в O(n) время

3.2. CopyOnWriteArrayList

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

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

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

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

3.3. Список ссылок

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

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

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

3.4. Прогрев СП

Теперь, чтобы доказать теорию, давайте поиграем с фактическими данными. Чтобы быть более точным, мы представим результаты тестирования 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 < 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 . После этого мы инициализируем его с помощью 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)

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() выполняются примерно в одно и то же время . Мы также ясно видим огромную разницу между результатами метода test Add(), test Get() и остальными результатами. Добавление элемента занимает 2 .296 микросекунды, а получение одного-0,007-микросекундная операция.

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

Аналогично, мы можем написать те же тесты для CopyOnWriteArrayList collection. Все, что нам нужно, – это заменить ArrayList в списке сотрудников экземпляром 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() по сравнению с Arraylist O(1).

Мы можем ясно видеть линейный рост времени, так как показатели производительности 878.166 по сравнению с 0.051 .

Теперь это LinkedList time:

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

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

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

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 с другими результатами экземпляра Map .

Для всех перечисленных методов/| у нас есть 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)) Операции

Для древовидной структуры Древовидная карта и 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 мс.,000 имеет незначительное увеличение 00:03:30 И, наконец, когда n=1 000 000 запуск завершается 00:05:27 мс .

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

5. Набор

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

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

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

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

Для 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)

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

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

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

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 test, они также выглядят одинаково.

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

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

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

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

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

Источник