Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 55
---Set elements at end ( 3kk )
LinkedList: 40 ms
ArrayList: 267 ms
ArrayList is faster
Все таки LinkedList…
Ну, по хорошему, для микробенчмарков стоит использовать что-нибудь вроде jhm. А так вы намеряли заодно кучу лишнего.
Согласен, но для цели — определить что в какой ситуации быстрее, то решил пренебречь этой кучей. Т.к. она была +-одинакова для обоих списков и всех замеров. Вместе с замером 1080p не пережимал. Замеры делал раз 5, результаты были +-2-10ms
Но в любом случае за наводку спасибо. По мере свободного времени — попробую разобраться с ссылкой, что Вы дали.
Но в любом случае за наводку спасибо. По мере свободного времени — попробую разобраться с ссылкой, что Вы дали.
Ну не знаю, с точностью до «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
— печальное соотношение.
github.com/search?l=java&q=arraydeque&ref=searchresults&type=Code
github.com/search?l=java&q=linkedlist&ref=searchresults&type=Code
— печальное соотношение.
jmh-фетишизм детектед :)
Чем отличается «add» от «insert to end», кроме диаметрально противоположных результатов по скорости?
Add elements ( 6kk )
ArrayList is faster
Insert elements to end( 1kk )
LinkedList is faster
Если вопрос мне — то я надеялся, что кто-то из людей с опытом как раз на этот вопрос ответит…
Я объяснить, к сожалению, не могу. То что написано в статье про работу ArrayList — то по логике процедура одинакова…
Я объяснить, к сожалению, не могу. То что написано в статье про работу ArrayList — то по логике процедура одинакова…
А покажите код, который использовался в обоих случаях, для обоих типов листов…
Пожалуйста.
.add
.add(index.value)
.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();
Выложите тестовый код здесь или на github.
«add» — добавляет в конец
«insert to end» — добавляет в конец
в чем разница в вашем тестовом коде для этих двух операций?
«add» — добавляет в конец
«insert to end» — добавляет в конец
в чем разница в вашем тестовом коде для этих двух операций?
ArrayList имеет внутри собственно array, который имеет ограниченный размер. Если не влезает — приходится пересоздавать массив и копировать содержимое. А добавление в начало или конец LinkedList делается за фиксированне время. Подозреваю, отсюда и разница. Если создавать ArrayList с запасом он будет побыстрее, потому что не нужна обёртка.
.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);
}
Сейчас займусь. Спасибо!
p.s. т.к. через index,value вставить в конец списка мы не можем — данный пункт убираю.
p.s. т.к. через index,value вставить в конец списка мы не можем — данный пункт убираю.
Только в том случае, если capacity недостаточно, и нужно увеличить размер массива.
В противном случае копируется только часть справа от вставляемого элемента (фактически сдвиг вправо на 1 элемент) — в случае последнего элемента копировать нечего, в случае предпоследнего — копируется 1 последний элемент.
В противном случае копируется только часть справа от вставляемого элемента (фактически сдвиг вправо на 1 элемент) — в случае последнего элемента копировать нечего, в случае предпоследнего — копируется 1 последний элемент.
tl;dr:
LinkedList представляет собой неиндексированную цепочку, которая быстро работает при операциях с концами цепочки. Оптимальное использование — очередь, на что намекает имплементация интерфейса Deque.
ArrayList представляет собой массив в обёртке, поэтому лучше при необходимости произвольного доступа.
LinkedList представляет собой неиндексированную цепочку, которая быстро работает при операциях с концами цепочки. Оптимальное использование — очередь, на что намекает имплементация интерфейса Deque.
ArrayList представляет собой массив в обёртке, поэтому лучше при необходимости произвольного доступа.
+1.
Я поставил минус статье и вот почему: Вы сравниваете слона с китом. Априори известна О-сложность операций для контейнеров типа «Элементы размещены в памяти последовательно» и «Связной список». Поэтому и нет никакого смысла сравнивать скорость их работы.
Вот кстати отличный пост на эту тему: habrahabr.ru/post/188010/
Я поставил минус статье и вот почему: Вы сравниваете слона с китом. Априори известна О-сложность операций для контейнеров типа «Элементы размещены в памяти последовательно» и «Связной список». Поэтому и нет никакого смысла сравнивать скорость их работы.
Вот кстати отличный пост на эту тему: habrahabr.ru/post/188010/
Судя по всему, вы программируете уже давно, так понимаю на Питоне, поэтому для Вас данная статья покажется «детской», оно так и есть, но для начинающих — будет полезной. Я до сего теста считал, что LinkedList при добавлении в конец списка(.add(value)) — вне конкуренции, или как минимум на ровне с ArrayList(судя по материалам, что я читал). Оказалось, что ArrayList с этим справляется быстрее.
Всем спасибо за замечания. Постарался их все учесть и подкорректировать статью.
Всем спасибо за замечания. Постарался их все учесть и подкорректировать статью.
Я сам когда-то так считал :) 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
Я не очень понял причину, почему размер увеличивается в полтора раза? Почему в полтора, это понятно, у нас срабатывает функция увеличения размера внутреннего массива, но почему увеличивается? Мы ведь создали пустой лист, и добавляем туда единственный объект Integer.
А grow тут не вызовется. Если использовать конструктор с указанием размера, то память занимается сразу (при дефолтном конструкторе — при добавлении первого объекта). Расти ему незачем — места хватает. И даже arraycopy будет вызван только на реально занятом диапазоне (то есть на нулевом).
Ваш ответ не совсем верный. При дефолтном конструкторе создается массив в 10 элементов
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
При таких ответах стоит указать версию java на которой это было подсмотрено.
Так я скопировал с той ссылки, что в данной ветке. ( 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.
Однако спасибо, я понял о чем вы. Посмотрел исходники, в JDK до 7 версии (посмотрел правда 6 и 7 только, но думаю ниже по версии тоже самое) стоит 10 элементов по дефолту, а вот в 8 версии, сначала 0, а после добавления первого элемента, становится DEFAULT_CAPACITY, которая равна 10.
Для очереди лучше ArrayDeque.
Косяк LinkedList'а в Java в том, что нет итератора, допускающего хотя бы частичное изменение списка. Т.е. нельзя кэшировать позицию в списке. С другой стороны. Кэшировать позицию на чтение можно запросто, только при изменении нужно кэш сбрасывать.
В общем, уметь нужно с этим работать. А так — да, если в середину списка каждый раз по индексу бездумно вставлять, то будет медленнее чем даже ArrayList, да ещё и скорость от индекса зависеть будет.
В общем, уметь нужно с этим работать. А так — да, если в середину списка каждый раз по индексу бездумно вставлять, то будет медленнее чем даже ArrayList, да ещё и скорость от индекса зависеть будет.
У итератора LinkedList вообще-то есть add, remove и set. Другой вопрос что нет потокобезопасности, но это совсем другой вопрос.
Add, remove, set одного итератора делают недействительными все остальные итераторы. Дело не в потокобезопасности. Допустим, Вы закэшировали позицию (или набор позиций) в списке (для частого обращения). В случае, если список будет изменён иным способом (а не через кэшированый итератор), кэш станет бесполезен. Даже если всё в одном потоке. Это сильно ограничивает возможности по быстрому поиску в списке. Т.е. если есть кэш позиции в списке, то его нужно сбрасывать/обновлять после каждого изменения списка, если оно было выполнено не через кэшированый итератор. Вне зависимости от потоков.
1) ничего не сказано про разогрев JVM или бенчмарки
2) не протестирован последоветльный перебор в коллекциях (предполагаю, что за счет большого количества cache miss линкед лист просядет)
3) почему используется Date() а не System.currentTimeMillis() или System.nanoTime()? первый раз такое вишу в тестах.
2) не протестирован последоветльный перебор в коллекциях (предполагаю, что за счет большого количества cache miss линкед лист просядет)
3) почему используется Date() а не System.currentTimeMillis() или System.nanoTime()? первый раз такое вишу в тестах.
Не знаю как в JAVA, но в .NET LinkedList по сравнению с листом имеет ещё и такое преимущество (хотя скорее особенность): он никогда не попадет целеком с элементами в LOH (Large Object Heap) из-за количества объектов, в то время как лист очень даже может, что может привести к фрагментации и т.п.
1) в свободное время попробую сделать…
2) имеете ввиду get(0), get(1), get(2)...? Если да:
3) Это мой первый тест. Почитал про System.currentTimeMillis(). Может его было и правильно использовать, но в данном случае на результат оно не повлияло.
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(). Может его было и правильно использовать, но в данном случае на результат оно не повлияло.
get(0), get(1), get(2) — отличная демонстрация того, как списки не надо использовать. Обязательно отметьте это в статье, тогда она действительно поможет новичкам не обходить списки за квадратичное время.
Крайне полезно было бы извлечь из комментариев Sap_ru, Oblitus и culvert пользу и добавить в статью:
1. Перебор с get (который Вы упомянули в комментарии, на который я отвечаю)
2. Перебор с итераторами
3. Для каждого случая с серединой списка получить итератор, указывающий на середину списка и провести k операций, используя итератор.
Ведь 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 операций, используя итератор.
Нельзя же так. :(
Когда использовать LinkedList:
1. Необходимо много данных добавлять в начало списка
2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
3. .set в конце списка
Плохая рекомендация. Во всех этих случаях лучшую скорость и потребление памяти покажет ArrayDeque.
Скорость операций вставки в ArrayList очень сильно завязана на соотношения размера кэша(ей) и расстояния точки вставки от конца.
Почему?
Из-за System.arrayCopy() которая сдвигает отрезок массива с сылками. Если он помещается в кеш то завершение метода не упирается в запись в память. А на последовательных вставках (как я полагаю сделаны тесты автора) — и в чтение тоже.
Первый раз слышу, чтобы скорость memcpy зависела от размера кеша. И интуиция мне говорит об обратном. Можно ссылку на пруфы какие-нибудь?
Как раз звучит логично. Если данные помещаются в кэш, то скорость доступа будет ограничивать скоростью кэша, а не памяти. Вы никогда не видели график скорости линейного чтения/записи от размера блока? Там чётко видны уровни всех кэшей. Во приличных бенчмарках есть. А график копирования будет средним между чтением/записью.
Вы так говорите, как будто открыли Америку. У вас были какие-то сомнения насчет того, что перенаправить несколько ссылок будет на порядки быстрее, чем копировать массивы с десятками тысяч элементов?
Вы еще возьмите не сто тысяч элементов а миллион, миллиард… Уверяю Вас, там разница будет еще сильнее :)
Вы еще возьмите не сто тысяч элементов а миллион, миллиард… Уверяю Вас, там разница будет еще сильнее :)
arrayList.add без итератора на 100к элементов показал результат
Удаление с начала списка LinkedList вне конкуренции даже без итератора
ArrayList: 23 ms
Удаление с начала списка LinkedList вне конкуренции даже без итератора
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сравнение скорости работы ArrayList и LinkedList на практике