Рубрики
Без рубрики

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

Узнайте о сложности времени для общих операций с коллекциями Java

Автор оригинала: baeldung.

1. Обзор

В этом уроке мы поговорим о производительности различных коллекций из 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 {

    List 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() выполняются примерно в одно и то же время . Мы также ясно видим огромную разницу между результатами метода 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) {
    return state.employeeSet.remove(state.employee);
}

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

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 .