ArrayList против LinkedList

Question

Я следил за предыдущим постом , в котором говорится:

Для LinkedList

• получи O (n)
• добавь O (1)
• удалить это O (n)
• Iterator.remove is O (1)

Для ArrayList

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

Итак, взглянув на это, я пришел к выводу, что если мне нужно сделать в моей коллекции только последовательную вставку, скажем, для 5000000 элементов, LinkedList превзойдет ArrayList.

И если мне нужно просто извлечь элементы из коллекции, выполнив итерацию, т. Е. Не захватывая элемент посередине, все равно LinkedList превзойдет `ArrayList.

Теперь, чтобы проверить мои два приведенных выше утверждения, я написал пример программы ниже ... Но я удивлен, что мои приведенные выше утверждения оказались неверными.

ArrayList превзошло Linkedlist в обоих случаях. Это заняло меньше времени, чем LinkedList для добавления, а также извлечения их из коллекции. Есть ли что-то, что я делаю не так, или первоначальные утверждения о LinkedList и ArrayList не выполняются для коллекций размером 5000000?

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

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j : arrL) {
    ;
}
System.out.println( (System.nanoTime() - nano2) );

Answer 1

Помните, что сложность big-O описывает асимптотическое поведение и может не отражать фактическую скорость реализации. Он описывает, как стоимость каждой операции растет с размером списка, а не скорость каждой операции. Например, следующая реализация add - это O (1), но она не быстрая:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

Я подозреваю, что в вашем случае ArrayList работает хорошо, потому что он довольно агрессивно увеличивает размер внутреннего буфера, поэтому не будет большого количества перераспределений. Когда размер буфера не нужно изменять, ArrayList будет быстрее add s.

Вы также должны быть очень осторожны, когда вы делаете этот вид профилирования. Я бы посоветовал вам изменить код профилирования, чтобы выполнить этап прогрева (чтобы JIT имел возможность провести некоторую оптимизацию, не влияя на ваши результаты), и усреднить результаты за несколько прогонов.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(обратите внимание, что sum может переполниться, и вам может быть лучше использовать System.currentTimeMillis()).

Также возможно, что компилятор оптимизирует ваши пустые циклы get. Убедитесь, что цикл действительно что-то делает для того, чтобы вызывать правильный код.

Answer 2

Это плохой тест ИМО.

• нужно повторить в цикле несколько раз, чтобы разогреть JVM
• нужно что-то делать в вашем итеративном цикле или это может быть оптимизированный массив
• ArrayList изменяет размеры, что дорого. Если бы вы построили ArrayList как new ArrayList(500000), вы бы построили за один удар, и тогда все выделения были бы довольно дешевыми (один предварительно выделенный резервный массив)
• Вы не указываете JVM своей памяти - она ​​должна быть запущена с -xMs == -Xmx (все предварительно выделено) и достаточно высокой, чтобы никакой GC, скорее всего, не сработал
• Этот тест не охватывает самый неприятный аспект LinkedList - произвольный доступ. (итератор не обязательно одно и то же). Если вы скармливаете 10% от размера большой коллекции как случайный выбор list.get, вы обнаружите, что связанные списки ужасны для захвата чего-либо, кроме первого или последнего элемента.

Для arraylist: jdk get - это то, что вы ожидаете:

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

(в основном просто возвращает индексированный элемент массива.,

Для связанного списка:

public E get(int index) {
    return entry(index).element;
}

выглядит похоже? Не совсем. entry - это метод, а не примитивный массив, и посмотрите, что он должен делать:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

Правильно, если вы попросите сказать list.get(250000), он должен начинаться с головы и многократно повторять следующий элемент. 250000 обращений или около того (есть оптимизация в коде, где он начинается с головы или хвоста, в зависимости от того, какой из них будет меньше обращений.)

Answer 3

ArrayList - это более простая структура данных, чем LinkedList. ArrayList имеет единый массив указателей в смежных областях памяти. Его нужно создавать заново только в том случае, если массив расширяется за пределы выделенного ему размера.

LinkedList состоит из цепочки узлов; каждый узел выделен и имеет передний и задний указатели на другие узлы.

Так что это значит? Если вам не нужно вставлять в середину, соединять, удалять в середине и т. Д., ArrayList обычно будет быстрее. Он требует меньшего количества памяти, имеет гораздо лучшую локальность ссылок (что важно для кэширования процессора) и т. Д.

Answer 4

Чтобы понять, почему полученные результаты не противоречат характеристике "большой O".Нам нужно вернуться к первым принципам;то есть определение .

Пусть f (x) и g (x) две функции, определенные на некотором подмножестве действительных чисел.Каждый записывает

f(x) = O(g(x)) as x -> infinity

тогда и только тогда, когда для достаточно больших значений x f (x) является не более чем константой, умноженной на g (x) в абсолютном значении.То есть f (x) = O (g (x)) тогда и только тогда, когда существует положительное действительное число M и действительное число x0, такое что

|f(x)| <= M |g(x)| for all x > x_0.

Во многих контекстах предполагается, что мызаинтересованы в скорости роста, поскольку переменная x стремится к бесконечности, остается неустановленной, и каждый пишет более просто, что f (x) = O (g (x)).

Итак, утверждение add1 is O(1) означает, что временная стоимость операции add1 в списке размера N стремится к постоянной C _add1 , а N стремится к бесконечности.

И утверждение add2 is O(1) amortized over N operations означает, что средняя стоимость времени одной из последовательности операций N add2 стремится к константе C _add2 , когда N стремится к бесконечности.

Что не говорит о том, что это за константы C _add1 и C _add2 .Фактически, причина того, что LinkedList медленнее, чем ArrayList в вашем тесте, заключается в том, что C _add1 больше, чем C _add2 .

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

Answer 5

1) Базовая структура данных Первое различие между ArrayList и LinkedList связано с тем, что ArrayList поддерживается Array, а LinkedList поддерживается LinkedList. Это приведет к дальнейшим различиям в производительности.

2) LinkedList реализует Deque Еще одно различие между ArrayList и LinkedList состоит в том, что помимо интерфейса List, LinkedList также реализует интерфейс Deque, который обеспечивает операции first-first-out для add () и poll () и некоторых других функций Deque. 3) Добавление элементов в ArrayList Добавление элемента в ArrayList - это операция O (1), если он не запускает изменение размера массива, в этом случае он становится O (log (n)). С другой стороны, добавление элемента в LinkedList - это операция O (1). , так как не требует навигации.

4) Извлечение элемента из позиции Чтобы удалить элемент из определенного индекса, например, вызывая remove (index), ArrayList выполняет операцию копирования, которая приближает его к O (n), в то время как LinkedList необходимо пройти к этой точке, что также делает его O (n / 2), так как он может перемещаться в любом направлении на основе близости .

5) Перебор ArrayList или LinkedList Итерация - это операция O (n) для LinkedList и ArrayList, где n - это номер элемента.

6) Извлечение элемента из позиции Операция get (index) - это O (1) в ArrayList, а O (n / 2) в LinkedList, так как она должна проходить до этой записи. Тем не менее, в обозначении Big O O (n / 2) - это просто O (n), потому что мы игнорируем там константы.

7) Память LinkedList использует объект-оболочку Entry, который является статическим вложенным классом для хранения данных и двух узлов следующего и предыдущего, в то время как ArrayList просто хранит данные в массиве.

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

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

Из всех вышеупомянутых различий между ArrayList и LinkedList, похоже, ArrayList - лучший выбор, чем LinkedList, почти во всех случаях, кроме случаев, когда вы выполняете частую операцию add (), а не remove () или get ().

Связанный список легче модифицировать, чем ArrayList, особенно если вы добавляете или удаляете элементы из начала или конца, потому что связанный список внутренне хранит ссылки на эти позиции, и они доступны во время O (1).

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

По моему мнению, используйте ArrayList вместо LinkedList для большинства практических целей в Java.

Answer 6

Трудно найти хороший вариант использования LinkedList. Если вам нужно только использовать интерфейс Dequeu, вам, вероятно, следует использовать ArrayDeque. Если вам действительно нужно использовать интерфейс List, вы часто будете слышать предложение всегда использовать ArrayList, поскольку LinkedList ведет себя очень плохо при доступе к случайному элементу.

К сожалению, у ArrayList также есть проблемы с производительностью, если элементы в начале или в середине списка должны быть удалены или вставлены.

Однако существует новая реализация списка, называемая GapList, которая объединяет сильные стороны как ArrayList, так и LinkedList. Он был разработан как замена для ArrayList и LinkedList и поэтому реализует интерфейсы List и Deque. Также реализованы все открытые методы, предоставляемые ArrayList (sureCapacty, trimToSize).

Реализация GapList гарантирует эффективный произвольный доступ к элементам по индексу (как это делает ArrayList) и в то же время эффективное добавление и удаление элементов в начало и конец списка (как это делает LinkedList).

Вы найдете больше информации о GapList на http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list.

Answer 7

Нотация big-O не об абсолютных временах, а об относительных временах, и ты не можешь сравнить числа одного алгоритма с другим.

Вы получаете информацию только о том, как тот же алгоритм реагирует на увеличение или уменьшение числа кортежей.

Один алгоритм может занять час для одной операции и 2 часа для двух операций, и это O (n), а другой тоже O (n), и занимает одну миллисекунду для одной операции и две миллисекундына две операции.

Другой проблемой при измерении с помощью JVM является оптимизация компилятора горячей точки.JIT-компилятор может устранить цикл бездействия.

Третье, что нужно учитывать, - это ОС и JVM, использующие кэши и выполняющие сборку мусора.

Answer 8

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

LinkedList : если вы добавляете элемент в индекс n, вы можете переместить указатель с 0 на n-1, а затем выполнить так называемую операцию добавления O (1). Операция удаления такая же.

---

ArraryList : ArrayList реализует интерфейс RandomAccess, что означает, что он может обращаться к элементу в O (1).
Если вы добавляете элемент в индекс n, он может перейти к индексу n-1 в O (1), переместить элементы после n-1, добавить набор элементов в слот n.
Операция перемещения выполняется встроенным методом System.arraycopy, это довольно быстро.

public static void main(String[] args) {

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

    List<Integer> linkList = new LinkedList<Integer>();

    long start = 0;
    long end = 0;
    Random random = new Random();

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,index == 0" + (end - start));

}

Answer 9

O нотационный анализ предоставляет важную информацию, но имеет свои ограничения. По определению, анализ нотаций предполагает, что каждая операция выполняется приблизительно в одно и то же время, что неверно. Как указал @seand, связанные списки внутренне используют более сложную логику для вставки и извлечения элементов (посмотрите на исходный код, вы можете нажать ctrl + click в вашей IDE). ArrayList внутренне нужно только вставлять элементы в массив и время от времени увеличивать его размер (что, даже будучи операцией o (n), на практике можно выполнить довольно быстро).

Приветствия