Когда использовать LinkedList поверх ArrayList в Java?
Как дополнение к ответу Рафаэля , я считаю, что эта более короткая процедура может обнаруживать размеры BMP:
function GetBitmapDimensions(const FileName: string; out Width,
Height: integer): boolean;
const
BMP_MAGIC_WORD = ord('M') shl 8 or ord('B');
var
f: TFileStream;
header: TBitmapFileHeader;
info: TBitmapInfoHeader;
begin
result := false;
f := TFileStream.Create(FileName, fmOpenRead);
try
if f.Read(header, sizeof(header)) <> sizeof(header) then Exit;
if header.bfType <> BMP_MAGIC_WORD then Exit;
if f.Read(info, sizeof(info)) <> sizeof(info) then Exit;
Width := info.biWidth;
Height := abs(info.biHeight);
result := true;
finally
f.Free;
end;
end;
12 ответов
Сводка ArrayList с ArrayDeque предпочтительны в [1 147] многие [еще 1147] примеры использования, чем LinkedList. Если Вы не sure — только запустите с ArrayList.
LinkedList и ArrayList две различных реализации интерфейса List. LinkedList реализации это с двунаправленным связанным списком. ArrayList реализации это с динамично изменяющим размеры массивом.
Как со стандартным связанным списком и операциями над массивом, различные методы будут иметь различное алгоритмическое время выполнения.
-
get(int index), O (n) (с [1 149] шаги n/4 в среднем) -
add(E element), O (1) -
add(int index, E element)O (n) (с [1 152] шаги n/4 в среднем), но O (1) когдаindex = 0<---, который основное преимущество [1 113] -
remove(int index)O (n) (с [1 155] шаги n/4 в среднем) -
Iterator.remove(), O (1) . <---, который основное преимущество [1 116] -
ListIterator.add(E element)O (1) , Это - одно из основных преимуществ [1 118]
<глоток> Примечание: для Многих операций нужно шаги n/4 в среднем, постоянный количество шагов в лучшем случае (например, индекс = 0), и , шаги n/2 в худшем случае (середина списка)
-
get(int index)O (1) <---основное преимущество [1 121] -
add(E element)O (1) амортизировано, но O (n) худший случай, так как массив должен быть изменен и скопировал -
add(int index, E element), , O (n) (с [1 165] шаги n/2 в среднем) -
remove(int index), O (n) (с [1 167] шаги n/2 в среднем) -
Iterator.remove(), O (n) (с [1 169] шаги n/2 в среднем) -
ListIterator.add(E element)O (n) (с [1 171] шаги n/2 в среднем)
<глоток> Примечание: для Многих операций нужно шаги n/2 в среднем, постоянный количество шагов в лучшем случае (конец списка), шаги n в худшем случае (запустите списка)
LinkedList<E> допускает постоянно-разовые вставки или удаления итераторы использования , но только последовательный доступ элементов. Другими словами, можно обойти список вперед или назад, но нахождение положения в списке занимает время пропорциональное размеру списка. Javadoc заявляет "операции, что индекс в список пересечет список с начала или конца, какой бы ни ближе" , таким образом, те методы O (n) ( шаги n/4) в среднем, хотя O (1) для [1 128].
ArrayList<E>, с другой стороны, позволяют быстро случайный доступ для чтения, таким образом, можно захватить любой элемент в постоянное время. Но добавление или удаление отовсюду, но конец требуют, чтобы смещение всех последних элементов, или сделало открытие или заполнило разрыв. Кроме того, если Вы добавляете больше элементов, чем способность основного массива, новый массив (1.5 раза размер) выделяется, и старый массив копируется в новый, таким образом добавление к ArrayList O (n) в худшем случае, но постоянно в среднем.
Так в зависимости от операций Вы намереваетесь сделать, необходимо выбрать реализации соответственно. Итерация по любому виду Списка является практически одинаково дешевой. (Выполняющий итерации по ArrayList технически быстрее, но если Вы не делаете что-то действительно чувствительное к производительности, Вы не должны волноваться об этом - они - оба константы.)
основные преимущества использования LinkedList возникают, когда Вы снова используете существующие итераторы, чтобы вставить и удалить элементы. Эти операции могут тогда быть сделаны в [1 181] O (1) путем изменения списка локально только. В списке массива остаток от массива должен быть , переместился (т.е. скопировал). С другой стороны, ища в LinkedList средства, переходящие по ссылкам в [1 183] O (n) ( шаги n/2) для худшего случая, тогда как в ArrayList желаемое положение может быть вычислено математически и получено доступ в [1 185] O (1) .
Другое преимущество использования LinkedList возникает, когда Вы добавляете или удаляете из заголовка списка, так как те операции O (1) , в то время как они O (n) для [1 136]. Обратите внимание, что ArrayDeque может быть хорошая альтернатива [1 138] для добавления и удаления от главы, но это не List.
кроме того, если у Вас есть большие списки, имеют в виду, что использование памяти также отличается. Каждый элемент LinkedList имеет больше служебное, так как указатели на следующие и предыдущие элементы также хранятся. ArrayLists не имеют этих издержек. Однако ArrayLists поднимают столько памяти, сколько выделяется для способности, независимо от того, были ли элементы на самом деле добавлены.
начальная способность по умолчанию ArrayList довольно мала (10 от Java 1.4 - 1.8). Но так как конкретная реализация является массивом, массив должен быть изменен, если Вы добавляете много элементов. Для предотвращения высокой стоимости изменения размеров, когда Вы знаете, что собираетесь добавить много элементов создайте ArrayList с более высокой начальной мощностью.
Это зависит, на какие операции Вы будете делать больше в Списке.
ArrayList быстрее для доступа к индексируемому значению. Это намного хуже при вставке или удалении объектов.
Для обнаружения больше прочитайте любую статью, которая говорит о различии между массивами и связанными списками.
В дополнение к другим хорошим аргументам выше, необходимо заметить ArrayList реализации RandomAccess интерфейс, в то время как LinkedList реализации Queue.
Так, так или иначе они решают немного отличающиеся проблемы с различием эффективности и поведения (см. их список методов).
ArrayList то, что Вы хотите. LinkedList почти всегда (производительность) ошибка.
, Почему LinkedList сосет:
- Это использует много маленьких объектов памяти, и поэтому влияет на производительность через процесс.
- Партии маленьких объектов плохи для местности кэша.
- Любая индексируемая операция требует обхода, т.е. имеет O (n) производительность. Это не очевидно в исходном коде, ведя к алгоритмам O (n) медленнее, чем если бы
ArrayListиспользовался. - Получение хорошей производительности хитро.
- , Даже когда большая-O производительность совпадает с
ArrayList, это, вероятно, будет значительно медленнее так или иначе. - Это издает неприятный звук для наблюдения
LinkedListв источнике, потому что это - вероятно, неправильный выбор.
Это - вопрос об эффективности. LinkedList является быстрым для добавления и удаления элементов, но медленным для доступа к определенному элементу. ArrayList быстро для доступа к определенному элементу, но может не спешить добавлять к любому концу, и особенно медленный для удаления в середине.
Массив по сравнению с ArrayList по сравнению с LinkedList по сравнению с Вектором идет больше подробно, как делает Связанный список .
ArrayList случайным образом доступно, в то время как LinkedList является действительно дешевым, чтобы развернуть и удалить элементы из. Для большинства случаев, ArrayList прекрасен.
, Если Вы не создали большие списки и измерили узкое место, Вы никогда не должны будете, вероятно, волноваться о различии.
Если Ваш код имеет add(0) и remove(0), используйте LinkedList, и это более симпатично addFirst() и removeFirst() методы. Иначе используйте ArrayList.
И конечно, Гуава ImmutableList является Вашим лучшим другом.
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
ArrayLists хороши для однократной записи и многократного чтения или добавлений, но плохи при добавлении / удалении спереди или с середины.
Да, я знаю, это старый вопрос, но я добавлю два цента:
LinkedList почти всегда неправильный выбор , по производительности. Есть несколько очень специфических алгоритмов, для которых требуется LinkedList, но они очень, очень редки, и алгоритм обычно конкретно зависит от способности LinkedList относительно быстро вставлять и удалять элементы в середине списка, как только вы туда переместитесь. с ListIterator.
Существует один распространенный вариант использования, в котором LinkedList превосходит ArrayList: это очередь. Однако если ваша цель - производительность, вместо LinkedList вам также следует рассмотреть возможность использования ArrayBlockingQueue (если вы можете заранее определить верхнюю границу размера своей очереди и можете позволить себе выделить всю память заранее) или эту реализацию CircularArrayList . (Да, это с 2001 года, так что вам нужно обобщить его, но у меня есть сопоставимые показатели производительности с тем, что цитируется в статье только что в недавней JVM)
Важной особенностью связного списка (которую я не прочитал в другом ответе) является конкатенация двух списков. С массивом это O(n) (+ накладные расходы на некоторые перераспределения), со связанным списком это только O(1) или O(2) ;-)
Важно: Для Java ее LinkedList это не так! Смотрите Есть ли в Java быстрый метод конкатенации для связного списка?
Список массивов - это, по сути, массив с методами для добавления элементов и т.д. (и вместо него следует использовать общий список). Это коллекция элементов, к которым можно получить доступ через индексатор (например, [0]). Он подразумевает переход от одного элемента к другому.
Связный список определяет последовательность от одного элемента к другому (элемент a -> элемент b). Того же эффекта можно добиться с помощью списка массивов, но в связанном списке абсолютно точно указано, какой элемент должен следовать за предыдущим.
Мое эмпирическое правило - то, если мне нужно Collection (т.е. не должен быть List), затем используют ArrayList, если Вы знаете размер заранее, или можете знать размер уверенно или знать, что это не будет варьироваться очень. Если Вам нужен произвольный доступ (т.е. Вы используете get(index)), затем избегают LinkedList. В основном используйте LinkedList, только если Вы не должны индексировать доступ и не знаете (приблизительного) размера набора, который Вы выделяете. Также, если Вы собираетесь быть созданием большого количества дополнений и удалений (снова через эти Collection интерфейс) затем, LinkedList может быть предпочтительным.