Сравнение скорости работы ArrayList и LinkedList на практике

Приветствую Вас!

ArrayList и LinkedList — знают все. В каких ситуациях работает быстро, а в какой ситуации работает медленной тот или другой список — знают тоже все, кто в теории, а кто на практике. Данный пост подходит для тех, кто только начинает изучать Java, или кто слышал, о том «что быстрее», но не видел на практике.

Рекомендую предварительно прочитать расширенные посты про работу:
ArrayList — habrahabr.ru/post/128269
LinkedList — habrahabr.ru/post/127864

Почему решил измерять? Потому, что после изучения информации остались пробелы, где и что всё-таки быстрее. Особенно сподвиг прочтенный комментарий к статье про LinkedList:
Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.


Начнем. Как замерял?
Возможно, у кого-то возникнут сомнения по-поводу корректности замера, но результаты оказались в некоторых ситуациях очень схожи с теорией.
Пример кода, с помощью которого делал один из типов замеров:

Date startLinked = new Date();
        for(int i = 0; i < k; i++) {
            //операция .add .insert. remove. get .set с начала середины, и конца списка
            //k - кол-во операций
        }
        Date finishLinked = new Date();
        long linkedTime = finishLinked.getTime() - startLinked.getTime();


k — во всех замерах разное, т.к. где-то для получения результата нужно 3 миллиона операций, а где-то 10 тысяч достаточно, т.к. при 3 миллионах необходимо ждать не одну минуту.

Выходные данные
==============Add====================
---Add elements ( 6kk )
LinkedList: 2264 ms
ArrayList: 493 ms
ArrayList is faster

==============Insert=================
---Insert elements to begin( 100k )
LinkedList: 132 ms
ArrayList: 2742 ms
LinkedList is faster

---Insert elements to middle( 60k )
LinkedList: 4110 ms
ArrayList: 494 ms
ArrayList is faster

==============Remove=================
---Remove elements from begin ( 100k )
LinkedList: 2 ms
ArrayList: 3220 ms
LinkedList is faster

---Remove elements from middle ( 100k )
LinkedList: 7519 ms
ArrayList: 1544 ms
ArrayList is faster

---Remove elements from end ( 1kk )
LinkedList: 37 ms
ArrayList: 8 ms
ArrayList is faster

==============Get====================
---Get elements from begin ( 4kk )
LinkedList: 25 ms
ArrayList: 7 ms
ArrayList is faster

---Get elements from middle ( 40k )
LinkedList: 2320 ms
ArrayList: 0 ms
ArrayList is faster

---Get elements from end ( 3kk )
LinkedList: 23 ms
ArrayList: 5 ms
ArrayList is faster

==============Set====================
---Set elements at begin ( 1kk )
LinkedList: 342 ms
ArrayList: 12 ms
ArrayList is faster

---Set elements at middle ( 50k )
LinkedList: 3734 ms
ArrayList: 1 ms
ArrayList is faster

---Set elements at end ( 3kk )
LinkedList: 40 ms
ArrayList: 267 ms
LinkedList faster

==============Finish=================








Выводы

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

Когда использовать LinkedList:
1. Необходимо много данных добавлять в начало списка
2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
3. .set в конце списка

Когда использовать ArrayList
1. .get
2. .set (начало и середина)
3. .add
4. remove ( кроме начала списка )

Комментарии обязательные к ознакомлению:
Ув. denonlink
Добавление/удаление элементов LinkedList с помощью итератора гораздо быстрее, чем Arraylist habrahabr.ru/post/233797/#comment_7883135


Ув. sekrasoft
habrahabr.ru/post/233797/#comment_7882579

Пишите в комментарии замечания/предложения — буду корректировать, пока не найдём истину.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 55

    +2
    ---Set elements at end ( 3kk )
    LinkedList: 40 ms
    ArrayList: 267 ms
    ArrayList is faster

    Все таки LinkedList…
      0
      Благодарю. Исправил.
      +2
      Ну, по хорошему, для микробенчмарков стоит использовать что-нибудь вроде jhm. А так вы намеряли заодно кучу лишнего.
        –5
        Согласен, но для цели — определить что в какой ситуации быстрее, то решил пренебречь этой кучей. Т.к. она была +-одинакова для обоих списков и всех замеров. Вместе с замером 1080p не пережимал. Замеры делал раз 5, результаты были +-2-10ms
        Но в любом случае за наводку спасибо. По мере свободного времени — попробую разобраться с ссылкой, что Вы дали.
          +5
          Ознакомьтесь, пожалуйста: shipilev.net/talks/j1-April2013-benchmarking-II.pdf и shipilev.net/talks/jeeconf-May2014-benchmarking.pdf
          Серьёзно, сделайте это. Если после этого не поймёте всего масштаба заблуждений, которые можно наблюдать в этом посте, пишите.
            +1
            Ну не знаю, с точностью до «array или linked?» результаты-то правильные, хотя и очевидные в основном. Вопрос скорее в том, что ни одна система не занимается тем, что добавляет элементы в list в определенное место с утра до вечера. А еще в постановке вопроса, я считаю, что LinkedList должен быть deprecated и муссирование его даже лишь как потенциальной альтернативы ArrayList все равно подталкивает людей к его использованию:
            github.com/search?l=java&q=arraydeque&ref=searchresults&type=Code
            github.com/search?l=java&q=linkedlist&ref=searchresults&type=Code
            — печальное соотношение.
          +2
          jmh-фетишизм детектед :)
          0
          Чем отличается «add» от «insert to end», кроме диаметрально противоположных результатов по скорости?
          Add elements ( 6kk )
          ArrayList is faster

          Insert elements to end( 1kk )
          LinkedList is faster
            –1
            Если вопрос мне — то я надеялся, что кто-то из людей с опытом как раз на этот вопрос ответит…
            Я объяснить, к сожалению, не могу. То что написано в статье про работу ArrayList — то по логике процедура одинакова…
              0
              А покажите код, который использовался в обоих случаях, для обоих типов листов…
                –3
                Пожалуйста.
                .add
                LinkedList<Integer> linkedList = new LinkedList<Integer>(); ArrayList<Integer> arrayList = new ArrayList<Integer>(); int value = 123456; System.out.println("---Add elements ( 6kk )"); Date startAddLinkedTime = new Date(); for(int i = 0; i < 6000000; i++) { linkedList.add(value); } Date finishAddLinkedTime = new Date(); long addLinkedTime = finishAddLinkedTime.getTime() - startAddLinkedTime.getTime(); Date startAddArrayTime = new Date(); for(int i = 0; i < 6000000; i++) { arrayList.add(value); } Date finishAddArrayTime = new Date(); long addArrayTime = finishAddArrayTime.getTime() - startAddArrayTime.getTime();

                .add(index.value)
                LinkedList<Integer> linkedList = new LinkedList<Integer>(); linkedList.add(0); ArrayList<Integer> arrayList = new ArrayList<Integer>(); arrayList.add(0); int value = 123456; System.out.println("---Insert elements to end( 1kk )"); Date startLinked = new Date(); for(int i = 0; i < 1000000; i++) { linkedList.add(linkedList.size()-1, value); } Date finishLinked = new Date(); long linkedTime = finishLinked.getTime() - startLinked.getTime(); Date startArray = new Date(); for(int i = 0; i < 1000000; i++) { arrayList.add(arrayList.size()-1, value); } Date finishArray = new Date();
                  0
                  Пожалуйста, пользуйтесь тегом <source>:

                  LinkedList<Integer> linkedList = new LinkedList<Integer>();
                  // и т.д.
                  
                    –1
                    Извиняюсь, совсем недавно… Еще и думаю: «странно, что код так криво форматируется».
                0
                Выложите тестовый код здесь или на github.
                «add» — добавляет в конец
                «insert to end» — добавляет в конец
                в чем разница в вашем тестовом коде для этих двух операций?
                  0
                  ArrayList имеет внутри собственно array, который имеет ограниченный размер. Если не влезает — приходится пересоздавать массив и копировать содержимое. А добавление в начало или конец LinkedList делается за фиксированне время. Подозреваю, отсюда и разница. Если создавать ArrayList с запасом он будет побыстрее, потому что не нужна обёртка.
                    0
                    .add(list.size() - 1, value) вставляет элемент предпоследним. В ArrayList это вызывает копирование всего массива:

                    // from java.util.ArrayList
                    public void add(int index, E e) {
                    	checkBoundInclusive(index);
                    	modCount++;
                    	if (size == data.length)
                    		ensureCapacity(size + 1);
                    	if (index != size)
                    		System.arraycopy(data, index, data, index + 1, size - index);
                    	data[index] = e;
                    	size++;
                    }
                    
                    private void checkBoundInclusive(int index) {
                    	if (index > size)
                    		throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
                    }
                    

                      0
                      Сейчас займусь. Спасибо!
                      p.s. т.к. через index,value вставить в конец списка мы не можем — данный пункт убираю.
                        0
                        Можно. list.add(list.size(), item).
                          –1
                          Результат по скорости тот же, что и для .add
                          ---Add elements ( 6kk )
                          LinkedList: 2363 ms
                          ArrayList: 495 ms
                          ArrayList is faster
                          
                          ---Insert elements to end( 1kk )
                          LinkedList: 149 ms
                          ArrayList: 34 ms
                          ArrayListis faster
                          
                            0
                            Неудивительно, потому что по умолчанию там и есть вставка в конец.
                        0
                        Только в том случае, если capacity недостаточно, и нужно увеличить размер массива.
                        В противном случае копируется только часть справа от вставляемого элемента (фактически сдвиг вправо на 1 элемент) — в случае последнего элемента копировать нечего, в случае предпоследнего — копируется 1 последний элемент.
                          –1
                          Действительно. Но всё же arraycopy даже для одного элемента — лишние накладные расходы.
                    +4
                    tl;dr:

                    LinkedList представляет собой неиндексированную цепочку, которая быстро работает при операциях с концами цепочки. Оптимальное использование — очередь, на что намекает имплементация интерфейса Deque.

                    ArrayList представляет собой массив в обёртке, поэтому лучше при необходимости произвольного доступа.
                      +3
                      +1.

                      Я поставил минус статье и вот почему: Вы сравниваете слона с китом. Априори известна О-сложность операций для контейнеров типа «Элементы размещены в памяти последовательно» и «Связной список». Поэтому и нет никакого смысла сравнивать скорость их работы.

                      Вот кстати отличный пост на эту тему: habrahabr.ru/post/188010/
                        0
                        Судя по всему, вы программируете уже давно, так понимаю на Питоне, поэтому для Вас данная статья покажется «детской», оно так и есть, но для начинающих — будет полезной. Я до сего теста считал, что LinkedList при добавлении в конец списка(.add(value)) — вне конкуренции, или как минимум на ровне с ArrayList(судя по материалам, что я читал). Оказалось, что ArrayList с этим справляется быстрее.

                        Всем спасибо за замечания. Постарался их все учесть и подкорректировать статью.
                          0
                          Я сам когда-то так считал :) ArrayList и ему подобные контейнеры захватывает кучу памяти наперёд, оттуда и скорость добавления в конец. Кстати, вот неплохой синтетический случай: в цикле создаётся большой ArrayList, к которому добавляют один элемент. Что-то вроде:

                          for (...) {
                              N = 1024*1024*1024; 
                              ArrayList<int> arr = new ArrayList<int>(N);
                              arr.add(0);  
                          }
                          


                          И вот после этой операции, размер arr в памяти увеличиться в полтора раза! LinkedList был бы чуточку экономнее.
                          См. grow() в hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/util/ArrayList.java
                            0
                            Я не очень понял причину, почему размер увеличивается в полтора раза? Почему в полтора, это понятно, у нас срабатывает функция увеличения размера внутреннего массива, но почему увеличивается? Мы ведь создали пустой лист, и добавляем туда единственный объект Integer.
                              0
                              Гм… Прошу прощения, не дописал строку с гипотетическим заполнением массива. Да, я имелл ввиду что после объявления массив заполняется включительно до N-1 го элемента. И уже потом вызывается add()
                                0
                                ИМХО, если мы достигли такого размера ArrayList, то захват половины памяти от заполненной своей, вполне оправдано.
                                Хотя было бы неплохо позволять юзеру подсовывать свой алгоритм расширения массива.
                              0
                              А grow тут не вызовется. Если использовать конструктор с указанием размера, то память занимается сразу (при дефолтном конструкторе — при добавлении первого объекта). Расти ему незачем — места хватает. И даже arraycopy будет вызван только на реально занятом диапазоне (то есть на нулевом).
                                0
                                Ваш ответ не совсем верный. При дефолтном конструкторе создается массив в 10 элементов
                                /**
                                     * Constructs an empty list with an initial capacity of ten.
                                     */
                                    public ArrayList() {
                                        this(10);
                                    }
                                
                                  0
                                  При таких ответах стоит указать версию java на которой это было подсмотрено.
                                    0
                                    Так я скопировал с той ссылки, что в данной ветке. ( hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/util/ArrayList.java )
                                    Однако спасибо, я понял о чем вы. Посмотрел исходники, в JDK до 7 версии (посмотрел правда 6 и 7 только, но думаю ниже по версии тоже самое) стоит 10 элементов по дефолту, а вот в 8 версии, сначала 0, а после добавления первого элемента, становится DEFAULT_CAPACITY, которая равна 10.
                          +1
                          Для очереди лучше ArrayDeque.
                          –2
                          Косяк LinkedList'а в Java в том, что нет итератора, допускающего хотя бы частичное изменение списка. Т.е. нельзя кэшировать позицию в списке. С другой стороны. Кэшировать позицию на чтение можно запросто, только при изменении нужно кэш сбрасывать.
                          В общем, уметь нужно с этим работать. А так — да, если в середину списка каждый раз по индексу бездумно вставлять, то будет медленнее чем даже ArrayList, да ещё и скорость от индекса зависеть будет.
                            +2
                            У итератора LinkedList вообще-то есть add, remove и set. Другой вопрос что нет потокобезопасности, но это совсем другой вопрос.
                              0
                              Add, remove, set одного итератора делают недействительными все остальные итераторы. Дело не в потокобезопасности. Допустим, Вы закэшировали позицию (или набор позиций) в списке (для частого обращения). В случае, если список будет изменён иным способом (а не через кэшированый итератор), кэш станет бесполезен. Даже если всё в одном потоке. Это сильно ограничивает возможности по быстрому поиску в списке. Т.е. если есть кэш позиции в списке, то его нужно сбрасывать/обновлять после каждого изменения списка, если оно было выполнено не через кэшированый итератор. Вне зависимости от потоков.
                                +1
                                Это довольно опасный подход, и его не зря не допускает стандартный механизм. Если очень надо — можно сделать свою реализацию путем банального копипаста и вырезания проверки на комодификацию.
                            +4
                            1) ничего не сказано про разогрев JVM или бенчмарки
                            2) не протестирован последоветльный перебор в коллекциях (предполагаю, что за счет большого количества cache miss линкед лист просядет)
                            3) почему используется Date() а не System.currentTimeMillis() или System.nanoTime()? первый раз такое вишу в тестах.
                              –2
                              Не знаю как в JAVA, но в .NET LinkedList по сравнению с листом имеет ещё и такое преимущество (хотя скорее особенность): он никогда не попадет целеком с элементами в LOH (Large Object Heap) из-за количества объектов, в то время как лист очень даже может, что может привести к фрагментации и т.п.
                                0
                                1) в свободное время попробую сделать…
                                2) имеете ввиду get(0), get(1), get(2)...? Если да:
                                Date startLinked = new Date();
                                        for(int i = 0; i < k; i++) {
                                            linkedList.get(i);
                                        }
                                        Date finishLinked = new Date();
                                        long linkedTime = finishLinked.getTime() - startLinked.getTime();
                                
                                        Date startArray = new Date();
                                        for(int i = 0; i < k; i++) {
                                            arrayList.get(i);
                                        }
                                


                                ---Get elements line ( 100k )
                                LinkedList: 11096 ms
                                ArrayList: 0 ms
                                


                                3) Это мой первый тест. Почитал про System.currentTimeMillis(). Может его было и правильно использовать, но в данном случае на результат оно не повлияло.
                                  +2
                                  get(0), get(1), get(2) — отличная демонстрация того, как списки не надо использовать. Обязательно отметьте это в статье, тогда она действительно поможет новичкам не обходить списки за квадратичное время.
                                  Ведь get работает за линейное время
                                  public E More ...get(int index) {
                                      return entry(index).element;
                                  }
                                  
                                  private Entry<E> More ...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;
                                  }
                                  

                                  Крайне полезно было бы извлечь из комментариев Sap_ru, Oblitus и culvert пользу и добавить в статью:
                                  1. Перебор с get (который Вы упомянули в комментарии, на который я отвечаю)
                                  2. Перебор с итераторами
                                  3. Для каждого случая с серединой списка получить итератор, указывающий на середину списка и провести k операций, используя итератор.
                                    +1
                                    Надо отметить, что get(i) в ArrayList будет работать даже быстрее итератора, там из накладных расходов всего одна проверка на выход за границы массива. А вот в LinkedList всё плохо, каждый раз надо идти по цепочке.
                                  +6
                                  Нельзя же так. :(
                                    +2
                                    Когда использовать LinkedList:
                                    1. Необходимо много данных добавлять в начало списка
                                    2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
                                    3. .set в конце списка

                                    Плохая рекомендация. Во всех этих случаях лучшую скорость и потребление памяти покажет ArrayDeque.
                                      –2
                                      Скорость операций вставки в ArrayList очень сильно завязана на соотношения размера кэша(ей) и расстояния точки вставки от конца.
                                        +2
                                        Почему?
                                          0
                                          Из-за System.arrayCopy() которая сдвигает отрезок массива с сылками. Если он помещается в кеш то завершение метода не упирается в запись в память. А на последовательных вставках (как я полагаю сделаны тесты автора) — и в чтение тоже.
                                            0
                                            Первый раз слышу, чтобы скорость memcpy зависела от размера кеша. И интуиция мне говорит об обратном. Можно ссылку на пруфы какие-нибудь?
                                              0
                                              Как раз звучит логично. Если данные помещаются в кэш, то скорость доступа будет ограничивать скоростью кэша, а не памяти. Вы никогда не видели график скорости линейного чтения/записи от размера блока? Там чётко видны уровни всех кэшей. Во приличных бенчмарках есть. А график копирования будет средним между чтением/записью.
                                                0
                                                Ссылку-то можно? Хоть на один такой бенч?
                                        +2
                                        Вставка и удаление ListIterator'ом. Шах и мат, товарищи…

                                        ArrayList add : 1166 ms
                                        LinkedList add: 13 ms
                                        ArrayList remove : 3558 ms
                                        LinkedList remove: 3 ms


                                        Код:
                                        
                                                final int count = 100000;
                                        
                                                ArrayList<Object> arrayList = new ArrayList<>();
                                                LinkedList<Object> linkedList = new LinkedList<>();
                                                for ( int i = 0 ; i < count ; i++ ) {
                                                    arrayList.add(new Object());
                                                    linkedList.add(new Object());
                                                }
                                        
                                                ListIterator iterator;
                                                long start;
                                        
                                                iterator = arrayList.listIterator();
                                                start = System.currentTimeMillis();
                                                for ( int i = 0 ; i < count ; i++ ) {
                                                    iterator.add(new Object());
                                                    iterator.next();
                                                }
                                                System.out.println("ArrayList add : " + ( System.currentTimeMillis() - start ) + " ms");
                                        
                                                iterator = linkedList.listIterator();
                                                start = System.currentTimeMillis();
                                                for ( int i = 0 ; i < count ; i++ ) {
                                                    iterator.next();
                                                    iterator.add(new Object());
                                                }
                                                System.out.println("LinkedList add: " + ( System.currentTimeMillis() - start ) + " ms");
                                        
                                                iterator = arrayList.listIterator();
                                                start = System.currentTimeMillis();
                                                for ( int i = 0 ; i < count ; i++ ) {
                                                    iterator.next();
                                                    iterator.remove();
                                                }
                                                System.out.println("ArrayList remove : " + ( System.currentTimeMillis() - start ) + " ms");
                                        
                                                iterator = linkedList.listIterator();
                                                start = System.currentTimeMillis();
                                                for ( int i = 0 ; i < count ; i++ ) {
                                                    iterator.next();
                                                    iterator.remove();
                                                }
                                                System.out.println("LinkedList remove: " + ( System.currentTimeMillis() - start ) + " ms");
                                        

                                          +2
                                          Вы так говорите, как будто открыли Америку. У вас были какие-то сомнения насчет того, что перенаправить несколько ссылок будет на порядки быстрее, чем копировать массивы с десятками тысяч элементов?

                                          Вы еще возьмите не сто тысяч элементов а миллион, миллиард… Уверяю Вас, там разница будет еще сильнее :)
                                            +1
                                            Этого очевидного теста нет в статье (и ни в одном комментарии), а использовать LinkedList для рандомного доступа в список с миллионом элементов — это извращенство. У него другие задачи.
                                            0
                                            arrayList.add без итератора на 100к элементов показал результат
                                            ArrayList: 23 ms
                                            


                                            Удаление с начала списка LinkedList вне конкуренции даже без итератора

                                          Only users with full accounts can post comments. Log in, please.