Является ли LinkedList действительно быстрее, чем ArrayList в случае вставки в середине списка?

Ответ 1

Разоренный

Не совсем. Здесь

for(int i = 0; i < MAX_VAL; i++) {
    linkedList.add(MAX_VAL/2, i);
}

вы не просто вставляете элемент; вы платите стоимость итерации от начала до i каждый раз. Естественно, что O(i).

С другой стороны, список должен быть довольно большим, прежде чем вы действительно увидите преимущества производительности вставки среднего списка. System.arraycopy является быстродействующей операцией, а с другой стороны, каждая вставка в LinkedList требует выделения экземпляра node.

Таким образом, ArrayList является лучшим выбором для 99% или более случаев в реальном мире, а использование узкого преимущества LinkedList требует большой осторожности.

Общие замечания по микрообнаружению JVM

Я также должен предупредить вас, что ваш бенчмаркинг плохо страдает. Существует довольно значительный контрольный список вещей, на которые следует обратить внимание, когда вы микробенчарируете на JVM, например:

• всегда разогревайте код, чтобы дать возможность компилятору JIT;
• Будьте очень осторожны в интерпретации результатов nanoTime из-за ошибок точности/точности. Сделайте чтение, по крайней мере, в миллисекундах (миллионы наносекунд), чтобы обеспечить надежность;
• контролировать побочные эффекты сборщика мусора;
• и др.

Поэтому совет должен использовать готовый каркас для микрообнаружения, например OpenJDK jmh.

Ответ 2

Чтобы продемонстрировать (in) эффект операции add(), лучше использовать объект ListIterator вместо объекта списка. Если вы используете метод add() непосредственно в связанном списке, он начинается с заголовка списка и должен перебираться в позицию, в которую вы хотите вставить элемент. Эта часть принимает O (n). Если вы используете ListIterator, он будет удерживать позицию, в которой мы добавляем элементы, и алгоритм не должен каждый раз перебираться в середину списка.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();


        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time:\t" + (System.nanoTime() - time));


        //Reset the lists
        linkedList = new LinkedList<Integer>();
        arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }

        time = System.nanoTime();
        ListIterator<Integer> li = linkedList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            li.add(i);
        }
        System.out.println("LL iterator:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        ListIterator<Integer> ali = arrayList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            ali.add(i);
        }
        System.out.println("AL iterator:\t" + (System.nanoTime() - time));
    }
}

Мои результаты показывают, что использование ListIterator в LinkedList дает наилучшую производительность для вставки элементов в "средний":

LL time:     237819474
AL time:      31410507
LL iterator:   5423172
AL iterator:  23975798

Ответ 3

У вашего теста есть предвзятость - он не измеряет обычную разницу в производительности.

Общие замечания о структуре LinkedList (по сравнению с ArrayList для большого списка):

• добавление/удаление node на голове или хвосте очень быстро
• Получение элемента из середины очень медленно
• Получение элемента становится быстрее (линейно) по мере приближения к концу списка
• Получение элемента из головы или хвоста приближается к скорости ArrayList
• Добавление/удаление элемента где-то посередине - это две операции: get plus node insertion
• Если вы используете ListIterator, вы можете добавить/удалить node где-то посередине и избежать операции get - очень быстрая операция

Ваш тест намеревается проверить (5).

Но он всегда выполняет худший случай - добавление/удаление элемента точно посередине.

Ваш микро-тест дает систематическую ошибку. Вам необходимо равномерно или произвольно распространять местоположение добавления/удаления. Или выполните макро-бенчмаркинг с реалистичными сложными и сложными приложениями.

Интересно прочитать о проблеме создания точного микро-теста: Теория и практика Java: анатомия ошибочного микрообъектива

Ответ 4

Я переписал программу Matej, чтобы случайным образом выбрать метод и запустить массив из 50 проб для каждого метода. Если вы берете в среднем самую быструю половину испытаний в каждой категории, то результат следующий:

LL: 570
AL: 120
Итератор LL: 1
AL iterator: 60

LL-итератор занимает много времени сортировки. В худших случаях производительность снижается в 15 раз из-за разминки (первый цикл) и gc (случайные всплески на несортированных данных).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class TestList {

    public static void main(String... args) {
        final int MAX_VAL = 10000;
        int[] currentIndex = {0, 0, 0, 0};
        int[] remaining = {50, 50, 50, 50};
        int[][] sequence = new int[4][50];

        while (keepWorking(remaining)) { //run 50 tests for each case at random

            int currentMethod = chooseMethod(remaining); //choose case. Probability is higher for tests with less trials

            switch (currentMethod) { //run a test based on the choice
                case 0:
                    sequence[currentMethod][currentIndex[currentMethod]] = getLL(MAX_VAL);
                    break;
                case 1:
                    sequence[currentMethod][currentIndex[currentMethod]] = getAL(MAX_VAL);
                    break;
                case 2:
                    sequence[currentMethod][currentIndex[currentMethod]] = getLLIt(MAX_VAL);
                    break;
                default:
                    sequence[currentMethod][currentIndex[currentMethod]] = getALIt(MAX_VAL);
                    break;
            }

            remaining[currentMethod]--;
            currentIndex[currentMethod]++;
        }

        for (int[] ar : sequence) {
            Arrays.sort(ar);
        }

        System.out.println("Time (us\nLL    \tAL\tLL incr\t AL incr");
        for (int i = 0; i < sequence[0].length; i++) {
            System.out.println(sequence[0][i] + "\t" + sequence[1][i] + "\t" + sequence[2][i] + "\t" + sequence[3][i]);
        }
        System.out.println("\nTime normalized to fastest run of a method\nLL\tAL\tLL incr\t AL incr");
        for (int i = 0; i < sequence[0].length; i++) {
            System.out.print(i);
            for (int j = 0; j < sequence.length; j++) {  //to 4
                int a = sequence[j][i] / (sequence[j][0]/100); //to keep result within the scope of int
                System.out.print("\t" + a);
            }
            System.out.println();
        }
    }

    public static boolean keepWorking(int[] remaining) {

        for (int i = 0; i < remaining.length; i++) {
            if (remaining[i] > 0) {
                return true;
            }
        }
        return false;
    }

    public static int chooseMethod(int[] rem) {
        int[] bins = new int[rem.length];
        for (int i = 0; i < rem.length; i++) {
            for (int j = i; j < rem.length; j++) {
                bins[j] += rem[i];
            }
        }
        int randomNum = new Random().nextInt(bins[rem.length - 1]);
        for (int i = 0; i < bins.length; i++) {
            if (randomNum < bins[i]) {
                return i;
            }
        }
        return -1;
    }

    public static int getLL(int MAX_VAL) {

        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
        }
        long time = System.nanoTime();

        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL / 2, i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getAL(int MAX_VAL) {

        List<Integer> arrayList = new ArrayList<>(MAX_VAL);
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL / 2, i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getLLIt(int MAX_VAL) {

        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
        }

        long time = System.nanoTime();

        ListIterator<Integer> li = linkedList.listIterator(MAX_VAL / 2);
        for (int i = 0; i < MAX_VAL; i++) {
            li.add(i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getALIt(int MAX_VAL) {

        List<Integer> arrayList = new ArrayList<>(MAX_VAL);
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(i);
        }

        long time = System.nanoTime();
        ListIterator<Integer> ali = arrayList.listIterator(MAX_VAL / 2);
        for (int i = 0; i < MAX_VAL; i++) {
            ali.add(i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }
}

Ответ 5

Некоторую осторожность следует выполнять с помощью простого профилирования следующим образом:

• Сбор мусора может произойти в непредсказуемое время, замедляя непредсказуемая часть.
• JRE работает медленнее, когда он начинается, а затем "прогревается".

Чтобы обойти это, сделайте профилирование в цикле, повторяя оба случая, много раз лучше в случайном порядке, и принимайте типичные значения, а не конечности. Иногда это приводит к различным результатам.

Ответ 6

поскольку ArrayList сохраняет значения последовательно таким образом 1: быстрее добавить значения (просто добавьте значение в последний индекс) 2: медленнее обновлять или удалять (нужно будет пройти весь список до того, как мы перейдем к node)

так как список массивов работает над концепцией LinkedList 1: медленнее при вставке (необходимо найти ссылку на предыдущее или следующее значение) 2: быстрее при обновлении (так как только точное node может быть достигнуто с помощью ссылки)

эта ссылка может быть отнесена

Ответ 7

в идеальном сценарии, который вы всегда вставляете в отсортированный список. Сначала вы находите индекс вставки с помощью двоичного механизма поиска, а затем вставляете его в этот индекс. Кроме того, при этом вы не можете использовать один и тот же проигрыватель все время. Вы установили итератор в New Evaluation. Таким образом, в этом сценарии реальной жизни, вставка которого выполняется быстрее.