Почему вставка в ArrayList быстрее, чем вставка в LinkedList в Java 8? - PullRequest
Новая
       13

Почему вставка в ArrayList быстрее, чем вставка в LinkedList в Java 8?

0 голосов
/ 07 декабря 2018

Я думаю, что вставка в LinkedList должна выполняться быстрее, чем вставка в ArrayList, потому что вставка в LinkedList просто требует копирования ссылок, тогда как вставка в ArrayList требует создания нескольких новых массивов в дополнение к копированию ссылок.Но я создал Java-код для проверки этого и обнаружил обратное: вставка в ArrayList выполняется быстрее, чем вставка в LinkedList. 

import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class ListPerformanceTester {
    public static void main(String[] args) {
        System.out.println("Time to perform ten million insertions using LinkedList: " +
                timeToPerformTenMillionInsertionsUsing(new LinkedList<>()));
        System.out.println("Time to perform ten million insertions using ArrayList: " +
                timeToPerformTenMillionInsertionsUsing(new ArrayList<>()));
    }

    private static long timeToPerformTenMillionInsertionsUsing(List<String> list) {
        Instant start = Instant.now();
        for (int i = 0; i < 10000000; ++i) {
            list.add("");
        }
        return Duration.between(start, Instant.now()).toMillis();
    }
}

Результаты запуска три раза: 

Time to perform ten million insertions using ArrayList: 135
Time to perform ten million insertions using LinkedList: 1321

Time to perform ten million insertions using ArrayList: 126
Time to perform ten million insertions using LinkedList: 1094

Time to perform ten million insertions using ArrayList: 125
Time to perform ten million insertions using LinkedList: 1086

Я даже попытался изменить порядок вставок на тот случай, если это дало эффект, и LinkedList все еще занимал больше времени: 

Time to perform ten million insertions using LinkedList: 2642
Time to perform ten million insertions using ArrayList: 402

Почему вставка в ArrayList быстрее, чем вставка в LinkedList? 

$ java -version
java version "1.8.0_171"
Java(TM) SE Runtime Environment (build 1.8.0_171-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)

1 Ответ

0 голосов
/ 07 декабря 2018

... но ... это быстрее .Время вставки связанного списка на передней или задней панели составляет постоянное время .Вставка списка массивов: амортизируется постоянное время , с оговоркой, что, если он достигнет определенной емкости, он удвоит размер своего внутреннего массива и копирование по всемиз предыдущих значений, которые он должен был отслеживать, это O (k), где k - размер текущего списка.

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

При этом, если мы разогреем код, выполнив, скажем, 100 раз, а затемвежливо попросите Java собирать мусор после каждого запуска теста (и знать, что он может сказать «нет»), мы можем получить немного лучшую картину. 

class ListPerformanceTester {
    public static void main(String[] args) {
        System.out.println("Warming up by running 100 times...");
        for(int i = 0; i < 100; i++) {
            // warm up
            timeToPerformTenMillionInsertionsUsing(new LinkedList<>());
            timeToPerformTenMillionInsertionsUsing(new ArrayList<>());
        }

        System.out.println("Starting test.");
        for(int i = 0; i < 10; i++) {
            System.out.println("Time to perform ten million insertions using LinkedList: " +
                                       timeToPerformTenMillionInsertionsUsing(new LinkedList<>()));
            System.out.println("Time to perform ten million insertions using ArrayList: " +
                                       timeToPerformTenMillionInsertionsUsing(new ArrayList<>()));
            System.out.println();

            System.gc();
        }

    }

    private static long timeToPerformTenMillionInsertionsUsing(List<String> list) {
        Instant start = Instant.now();
        for (int i = 0; i < 10000000; ++i) {
            list.add("");
        }
        return Duration.between(start, Instant.now()).toMillis();
    }
}

Вот десять результатов с моей машины (которая является IntelCore i7-7820HQ): 

Warming up by running 100 times...
Starting test.
Time to perform ten million insertions using LinkedList: 40
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 46

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 39
Time to perform ten million insertions using ArrayList: 47
...