Подтвердить что ты не робот

ArrayList Vs LinkedList

Я следил за предыдущим сообщением об этом:

Для LinkedList

  • get is O (n)
  • add is O (1)
  • remove - O (n)
  • Iterator.remove - O (1)

Для ArrayList

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

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

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

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

ArrayList outclassed 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) );
4b9b3361

ОТВЕТЫ

Ответ 1

Помните, что сложность большого вывода описывает асимптотическое поведение и может не отражать фактическую скорость реализации. В нем описывается, как стоимость каждой операции растет с размером списка, а не скоростью каждой операции. Например, следующая реализация 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. Убедитесь, что цикл на самом деле что-то делает, чтобы обеспечить получение нужного кода.

Ответ 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 доступа или около того (есть оптимизация в коде, где он начинается с головы или хвоста, в зависимости от которых будет меньше обращений.)

Ответ 3

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

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

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

Ответ 4

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

Пусть 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 не предсказывает абсолютную или даже относительную производительность. Все, что он предсказывает, это форма функции производительности, так как управляющая переменная становится очень большой. Это полезно знать, но это не говорит вам все, что вам нужно знать.

Ответ 5

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

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

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

Другая проблема, если измерение с помощью JVM - это оптимизация компилятора hotspot. JIT-компилятор может исключить цикл do-nothing-loop.

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

Ответ 6

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

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

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

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

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

Ответ 7

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

Приветствия

Ответ 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));

}