25 дек 2019 в 18:26

Вставка в середину: ArrayList vs LinkedList

Ожидает приглашения

Вставка в середину где быстрее у ArrayList или LinkedList? Избитый вопрос, ответ на который часто можно услышать один из двух:

“LinkedList. Там мы только ссылки переназначаем, а в ArrayList нужно сместить половину коллекции вправо плюс время от времени будем ловить потерю перфоманса на расширение емкости”.
“ArrayList. Ведь копирование происходит нативным методом, который довольно быстрый, в то время как LinkedList должен еще добраться до середины, перебирая каждый элемент, а это уже линейная асимптотическая сложность, в то время как у ArrayList это значение константа”. Также вспоминают, что емкость можно задать изначально больше, что снизит потери по производительности (дефолтная емкость ArrayList равна 10).

Попробуем разобраться кто прав

Oт теории к делу. Тестировать будем при помощи JMH. К слову, это весьма полезный бенчмарк для подобного юнит тестирования от Алексея Шипелева.

Исходные данные: коллекции ArrayList и LinkedList одинакового размера (10, 100, 1000, 10_000, 100_000, 1_000_000 элементов). Замерять будем среднюю скорость вставки одного элемента по индексу в середину. Замер в наносекундах. Тесты заключаются в прогоне 10 итераций, перед которыми также запускаем 10 итераций для прогрева JVM (результаты прогрева не учитываются). В течении каждой итерации на протяжении 10 секунд происходит вставка в середину. Важный момент: для чистоты эксперимента каждая последующая вставка возвращает коллекцию в исходное состояние. Для точности всю процедуру повторяем.

Конфигурация JMH

Исходный код

@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@Measurement(time = 10)
@Warmup(time = 10)
public class InsertInMiddle {
    @Param({"10", "100", "1000", "10000", "100000", "1000000"})
    private int size;
    private Byte byteVal = 7;
    private List<Byte> arrayList = new ArrayList<>();
    private List<Byte> linkedList = new LinkedList<>();

    @Setup(Level.Invocation)
    public void doSetup() {
        for (int i = 0; i < size; i++) {
            arrayList.add(byteVal);
        }
        for (int i = 0; i < size; i++) {
            linkedList.add(byteVal);
        }
    }

    @TearDown(Level.Invocation)
    public void doTearDown() {
        arrayList = new ArrayList<>();
        linkedList = new LinkedList<>();
    }

    @Benchmark
    public void testArrayList() {
        arrayList.add(size / 2, byteVal);
    }

    @Benchmark
    public void testLinkedList() {
        linkedList.add(size / 2, byteVal);
    }

    public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder().include(com.epam.InsertInMiddle.class.getSimpleName())
                .warmupIterations(10)
                .measurementIterations(10)
                .jvmArgs("-Xms10000m", "-Xmx10000m", "-XX:MaxDirectMemorySize=2500M")
                .forks(2)
                .build();
        new Runner(options).run();
    }
}

В результате выполнения тестов получаем

О чем говорят результаты

ArrayList уступил только при вставке в коллекцию размером 10 элементов. Выигрыш у LinkedList в этом случае вполне оправдан, так как элементов мало и следовательно пробежаться до середины и переназначить ссылки кажется не затратным делом, в то время как ArrayList требует сначала увеличить емкость (11-ый элемент уже не вмещается в дефолтную емкость) и затем копировать половину коллекции от середины вправо. В остальных рассматриваемых случаях перевес на стороне ArrayList.

Надеюсь данные наблюдения показались интересными и возможно сделают ваш ответ на собеседовании более развернутым. Спасибо за внимание!

Хабы:

Java