В java массивы и динамические списки типа arraylist отличаются тем что
Массив против ArrayList в Java
В Java следующие два разных способа создания массива.
Различия между Array и ArrayList
// Java-программа для демонстрации различий между массивами
// и ArrayList
public static void main(String args[])
int [] arr = new int [ 2 ];
// Создать arrayList с начальной емкостью 2
ArrayList arrL = new ArrayList ( 2 );
// Добавить элементы в ArrayList
// Доступ к элементам ArrayList
// Java-программа для демонстрации различий между массивами
// и ArrayList
public static void main(String args[])
// Нужно указать размер для массива
int [] arr = new int [ 3 ];
// Мы не можем добавить больше элементов в массив arr []
// Не нужно указывать размер
ArrayList arrL = new ArrayList ();
// Мы можем добавить больше элементов в arrL
public static void main(String args[])
int [] array = new int [ 3 ];
// разрешено, однако, нужно инициализировать
Test[] array1 = new Test[ 3 ];
// не допускается (раскомментирование ниже строки вызывает
// ArrayList arrL = new ArrayList ();
ArrayList arrL1 = new ArrayList<>();
ArrayList arrL2 = new ArrayList<>();
ArrayList arrL3 = new ArrayList<>();
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Добавление элемента в массив Java по сравнению с ArrayList
Узнайте, как добавить элемент в массив Java по сравнению с ArrayList
1. Обзор
2. Массивы Java и ArrayList
2.1. Доступ к элементам и их изменение
Мы можем получить доступ к элементам массива и изменить их, используя обозначения в квадратных скобках:
С другой стороны, ArrayList имеет набор методов для доступа и изменения элементов:
2.2. Фиксированный и динамический размер
Массив и ArrayList выделяют память кучи аналогичным образом, но разница заключается в том, что массив имеет фиксированный размер, в то время как размер ArrayList динамически увеличивается.
Поскольку массив Java имеет фиксированный размер, нам необходимо указать его размер при создании экземпляра. Невозможно увеличить размер массива после его создания. Вместо этого нам нужно создать новый массив с измененным размером и скопировать все элементы из предыдущего массива.
Операция добавления имеет постоянную амортизированную временную стоимость. Другими словами, добавление n элементов в ArrayList требует O(n) времени.
2.3. Типы элементов
3. Добавление элемента
Как мы уже видели, массивы имеют фиксированный размер.
Итак, чтобы добавить элемент, сначала нам нужно объявить новый массив, который больше старого массива, и скопировать элементы из старого массива во вновь созданный массив. После этого мы можем добавить новый элемент в этот вновь созданный массив.
Давайте рассмотрим его реализацию в Java без использования каких-либо служебных классов:
После того, как мы создали новый массив, мы можем легко добавить новый элемент в массив:
С другой стороны, добавление элемента в ArrayList довольно просто :
4. Вставка элемента в индекс
Вставка элемента в заданный индекс без потери ранее добавленных элементов-непростая задача в массивах.
Прежде всего, если массив уже содержит количество элементов, равное его размеру, то сначала нам нужно создать новый массив большего размера и скопировать элементы в новый массив.
Кроме того, нам нужно сдвинуть все элементы, которые идут после указанного индекса, на одну позицию вправо:
Однако класс ArrayUtils дает нам более простое решение для вставки элементов в массив :
Мы должны указать индекс, в который мы хотим вставить значение, исходный массив и значение для вставки.
Метод insert() возвращает новый массив, содержащий большее количество элементов, при этом новый элемент имеет указанный индекс, а все остальные элементы сдвинуты на одну позицию вправо.
Обратите внимание, что последний аргумент метода insert() является переменным аргументом, поэтому мы можем вставить любое количество элементов в массив.
А остальные элементы будут сдвинуты на три места вправо.
Кроме того, это может быть достигнуто тривиально для ArrayList :
ArrayList сдвигает элементы и вставляет элемент в нужное место.
5. Заключение
Что работает быстрее: массив или ArrayList?
Что работает быстрее? Прогнал тест 100 раз. Результаты всегда разные: то один быстрее, то второй. Так есть ли реальный выигрыш в использовании массива вместо ArrayList? ArrayList создавал с нужным размером сразу, чтобы время на «расширение» не тратилось.
Проверялось быстродействие команды add. Пытался понять, уменьшит ли замена ArrayList на обычный массив в «узких местах» время выполнения (часто слышал такое предположение). Если в моем случае всегда известен заранее размер массива/листа. Результаты получились случайные. Иногда ArrayList значительно быстрее, иногда массив, иногда они равны.
5 ответов 5
Обычный массив почти наверняка будет выигрывать в скорости как при доступе, так и при записи. Хотя бы потому, что при обращении к ArrayList у вас лишний вызов метода, а может и не один. С другой стороны, внутри ArrayList’а тот же самый массив и доступ вполняется по тому же принципу, поэтому если нет чрезмерной нагрузки на него, то в общем их производительность примерно одного порядка.
Разница для вас в том, что с листами работать намного проще и удобнее, чем с массивами. По этой причине вам не следует заниматься ерундой и гонять какие-то нелепые тесты, а просто использовать ArrayList, если только у вас нет каких-то ОЧЕНЬ серьёзных оснований использовать массив. Одно из таких оснований: вы точно знаете заранее размер массива и вы точно знаете, что использование этого массива в коде ограничено и вам не придётся городить огород, чтобы гонять потом эти массивы в листы и наоборот.
UPD Что за числа в вашем тесте детские? 1000.000? Это просто смешно. Я прогнал тест на выполнение 10.000.000.000 добавлений и получил вот что:
UPD2
Убрал сборку мусора вообще и перегруппировал нули и получил следующее
Результат очень стабилен. Думаю, на get результаты будут подобные.
Массив или список в Java. Что быстрее?
ответ: общий консенсус заключается в том, что разница в производительности незначительна. Интерфейс списка обеспечивает большую гибкость.
30 ответов
Я предлагаю вам использовать профайлер, чтобы проверить что быстрее.
мое личное мнение, что вы должны использовать списки.
Я работаю над большой кодовой базой, а предыдущая группа разработчиков использовала массивы везде. Это делает код очень сложно. После изменения больших кусков его в списки мы не заметили никакой разницы в скорости.
путь Java заключается в том, что вы должны рассмотреть, какие данные абстрагирование наиболее соответствует вашим потребностям. Помните, что в Java список является абстрактным, а не конкретным типом данных. Вы должны объявить строки как список, а затем инициализировать его с помощью реализации ArrayList.
такое разделение абстрактного типа данных и конкретной реализации является одним из ключевых аспектов объектно-ориентированного программирования.
ArrayList реализует абстрактные данные списка Тип, использующий массив в качестве базовой реализации. Скорость доступа практически идентична массиву, с дополнительными преимуществами возможности добавления и вычитания элементов в список(хотя это операция O (n) с ArrayList), и что если вы решите изменить базовую реализацию позже, вы можете. Например, если вы понимаете, что вам нужен синхронизированный доступ, вы можете изменить реализацию на вектор без перезаписи всего кода.
в самом деле, ArrayList был специально разработан для замены низкоуровневой конструкции массива в большинстве контекстов. Если бы Java разрабатывался сегодня, вполне возможно, что массивы были бы полностью исключены в пользу конструкции ArrayList.
в Java все коллекции хранят только ссылки на объекты, а не сами объекты. Оба массива и ArrayList будут хранить несколько тысяч ссылок в непрерывном массиве, поэтому они по существу идентичны. Вы можете считать, что непрерывный блок из нескольких тысяч 32-битных ссылок всегда будет легко доступен на современном оборудовании. Это не гарантирует, что у вас не закончится память полностью, конечно, только то, что требование смежного блока памяти не сложно выполнить.
вы должны предпочесть общие типы массивам. Как упоминалось другими, массивы являются негибкими и не обладают выразительной силой общих типов. (Однако они поддерживают проверку типов во время выполнения, но это плохо сочетается с универсальными типами.)
но, как всегда, при оптимизации вы всегда должны следовать этим шагам:
хотя ответы, предлагающие использовать ArrayList, имеют смысл в большинстве сценариев, фактический вопрос относительной производительности на самом деле не был дан ответ.
есть несколько вещей, которые вы можете сделать с массивом:
общий вывод
хотя операции get и set несколько медленнее на Коллекция ArrayList (респ. 1 и 3 наносекунды за вызов на моем компьютере),существует очень мало накладных расходов на использование ArrayList против массива для любого неинтенсивного использования. есть несколько вещей, чтобы иметь в виду:
подробные результаты
вот результаты, которые я измерил для этих трех операций с помощью jmh бенчмаркинг библиотека (раз в наносекундах) с JDK 7 на a стандартной архитектуры x86 компьютере. Обратите внимание, что ArrayList никогда не изменяется в тестах, чтобы убедиться, что результаты сопоставимы. контрольный код доступен здесь.
Создание Массива / ArrayList
я провел 4 теста, выполнив следующие инструкции:
результаты (в наносекундах на вызов, 95% доверительный):
вывод: нет заметной разницы.
операции get
я провел 2 теста, выполнив следующие инструкции:
результаты (в наносекундах на вызов, 95% доверительный):
вывод: получение из массива примерно на 25% быстрее чем получение от ArrayList, хотя разница составляет только порядка одной наносекунды.
набор операций
я провел 2 теста, выполнив следующие инструкции:
результаты (в наносекундах на один вызов):
клон/копию
Я предполагаю, что оригинальный плакат исходит из фона C++/STL, который вызывает некоторую путаницу. В C++ std::list представляет собой двухсвязный список.
если этот конкретный код действительно чувствителен к производительности, вы можете создать один char[] массив (или даже byte[] ) для всех символов всех строк, а затем массив смещений. IIRC, вот как реализуется javac.
Ну, во-первых, стоит уточнить, Вы имеете в виду» список » в классическом смысле структуры данных comp sci (т. е. связанный список) или вы имеете в виду java.утиль.Список? Если вы имеете в виду java.утиль.Лист, это интерфейс. Если вы хотите использовать массив, просто используйте реализацию ArrayList, и вы получите поведение и семантику, подобные массиву. Проблема решена.
Если вы имеете в виду массив против связанного списка, это немного другой аргумент, для которого мы возвращаемся к Big O (вот простом английском языке объяснение если это незнакомый термин.
поэтому вы выбираете тот, который лучше всего подходит для изменения размера массива. Если вы изменяете размер, вставляете и удаляете много, то, возможно, связанный список хороший выбор. То же самое происходит, если случайный доступ редок. Вы упомянули серийный доступ. Если вы в основном делаете последовательный доступ с очень небольшой модификацией, то, вероятно, не имеет значения, какой вы выбираете.
связанные списки имеют немного более высокие накладные расходы, так как, как вы говорите, вы имеете дело с потенциально несмежными блоками памяти и (эффективно) указателями на следующий элемент. Это, вероятно,не является важным фактором, если вы не имеете дело с миллионами записей.
Я написал небольшой тест для сравнения ArrayLists с массивами. На моем старом ноутбуке время прохождения через 5000-элементный arraylist, 1000 раз, было примерно на 10 миллисекунд медленнее, чем эквивалентный код массива.
Итак, если вы ничего не делаете, кроме повторения списка, и вы делаете это много, то может быть это стоит оптимизации. В противном случае я бы использовал список, потому что это облегчит вам do нужно оптимизировать код.
Н.б. Я сделал обратите внимание, что с помощью for String s: stringsList был примерно на 50% медленнее, чем использование старого стиля for-loop для доступа к списку. Иди разберись. Вот две функции, которые я синхронизировал; массив и список были заполнены 5000 случайными (разными) строками.
однако, если вы делаете постоянную, тяжелую итерацию с небольшим структурным изменением (без добавления и удаления) для, скажем, рендеринга программного обеспечения или пользовательской виртуальной машины, мои тесты последовательного доступа показывают, что ArrayLists на 1.5 x медленнее, чем arrays в моей системе (Java 1.6 на моем годовалом iMac).
нет, потому что технически, массив хранит только ссылки на строки. Сами строки располагаются в другом месте. Для тысячи элементов я бы сказал, что список будет лучше, он медленнее, но он предлагает большую гибкость и проще в использовании, особенно если вы собираетесь изменить их размер.
Если у вас есть тысячи, рассмотрите возможность использования дерева. Trie-это древовидная структура, которая объединяет общие префиксы хранимой строки.
например, если строки были
trie будет хранить:
строки требуют 57 символов (включая нулевой Терминатор, ‘\0’) для хранения, а также независимо от размера строкового объекта, который их содержит. (На самом деле, мы, вероятно, должны округлить все размеры до кратных 16, но. ) Призывать это 57 + 5 = 62 байт, грубо говоря.
trie требует 29 (включая нулевой Терминатор, ‘\0’) для хранения, плюс размер узлов trie, которые являются ссылкой на массив и список дочерних узлов trie.
для этого примера это, вероятно, выходит примерно одинаково; для тысяч это, вероятно, выходит меньше, пока у вас есть общие префиксы.
теперь, при использовании trie в другом коде, вам придется преобразовать в String, вероятно, используя StringBuffer в качестве промежуточный. Если многие строки используются сразу как строки, вне trie, это потеря.
но если вы используете только несколько в то время-скажем, чтобы посмотреть вещи в словаре-trie может сэкономить вам много места. Наверняка меньше места, чем хранение их в HashSet.
как отметил Марк, после прогрева JVM нет существенной разницы (несколько тестовых проходов). Проверено с повторно созданным массивом или даже новым пропуском, начинающимся с новой строки матрицы. С большой вероятностью этот знаковый простой массив с индексным доступом не должен использоваться в пользу коллекций.
еще первый 1-2 проходит простой массив в 2-3 раза быстрее.
слишком много слов для предмета, слишком простого для проверки. без каких-либо вопросов массив в несколько раз быстрее, чем любой контейнер класса. Я бегу по этому вопросу, ища Альтернативы для моего критического раздела производительности. Вот прототип кода, который я построил, чтобы проверить реальную ситуацию:
на основе массива (строка 16 активна):
на основе списка (строка 17 активна):
поскольку здесь уже есть много хороших ответов, я хотел бы дать вам некоторую другую информацию практического вида, которая сравнение производительности вставки и итерации : примитивный массив против связанного списка в Java.
это фактическая простая проверка производительности.
таким образом, результат будет зависеть от производительности машины.
исходный код, используемый для этого ниже:
результат производительности ниже :
помните, что ArrayList инкапсулирует массив, поэтому есть небольшая разница по сравнению с использованием примитивного массива (за исключением того, что список намного проще работать с java).
выбор массива против списка не так важен (учитывая производительность) в случае хранения строковых объектов. Поскольку и массив, и список будут хранить ссылки на строковые объекты, а не фактические объекты.
Если вы заранее знаете, как большие данные, то массив будет быстрее.
список более гибкий. Вы можете использовать ArrayList, который поддерживается массивом.
список медленнее массивов.Если вам нужна эффективность, используйте массивы.Если вам нужна гибкость, используйте список.
Это вы можете жить с фиксированным размером, массивы будут быстрее и потребуется меньше памяти.
Если вам нужна гибкость интерфейса списка с добавлением и удалением элементов, остается вопрос, какую реализацию Вы должны выбрать. Часто ArrayList рекомендуется и используется для любого случая, но также ArrayList имеет проблемы с производительностью, если элементы в начале или в середине списка должны быть удалены или вставлены.
поэтому вы можете захотеть иметь посмотрите наhttp://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list который вводит GapList. Эта новая реализация списка сочетает в себе сильные стороны ArrayList и LinkedList, что приводит к очень хорошей производительности почти для всех операций.
в зависимости от реализации. возможно, что массив примитивных типов будет меньше и эффективнее, чем ArrayList. Это связано с тем, что массив будет хранить значения непосредственно в непрерывном блоке памяти, а простейшая реализация ArrayList будет хранить указатели на каждое значение. Особенно на 64-битной платформе это может иметь огромное значение.
конечно, реализация jvm может иметь особый случай для этой ситуации, в которой если производительность будет такой же.
список является предпочтительным способом в java 1.5 и за его пределами, поскольку он может использовать дженерики. Массивы не могут иметь дженериков. Также массивы имеют заранее определенную длину, которая не может динамично развиваться. Инициализация массива с большим размером не является хорошей идеей. ArrayList-это способ объявить массив с дженериками, и он может динамически расти. Но если delete и insert используются чаще, то linked list является самой быстрой структурой данных.
массивы, рекомендуемые везде, где вы можете использовать их вместо списка, особенно если вы знаете, что количество и размер элементов не будут меняться.
конечно, если вам нужно добавить или удалить объекты из коллекции много раз легко использовать списки.
ArrayList хранит свои элементы в Object[] массив и использовать нетипизированные toArray метод, который намного быстрее (синяя полоса), чем типизированный. Это typesafe, так как нетипизированный массив завернут в универсальный тип ArrayList Это проверяется компилятором.
на этой диаграмме показан тест с n = 5 на Java 7. Однако изображение не сильно меняется с большим количеством элементов или другой виртуальной машиной. Накладные расходы CPU не могут показаться радикальными,но это складывается. Скорее всего, потребители массива должны преобразовать его в коллекцию, чтобы что-то с ним сделать, а затем преобразовать результат обратно в массив, чтобы передать его в другой метод интерфейса и т. д. Используя простой ArrayList вместо массива улучшает производительность, не добавляя много места. ArrayList добавляет постоянные накладные расходы в 32 байта к обернутому массиву. Например, array десять объектов требует 104 байт ArrayList 136 байт.
эта операция выполняется в постоянное время, поэтому оно намного быстрее, чем любое из вышеперечисленных (желтая полоса). Это не то же самое, что защитная копия. Неизменяемая коллекция изменится при изменении внутренних данных. Если это произойдет, клиенты могут столкнуться с ConcurrentModificationException при повторении элементов. Можно считать плохим дизайном, что интерфейс предоставляет методы, которые бросают UnsupportedOperationException во время выполнения. Однако, по крайней мере для внутреннего использования, этот метод может быть высокопроизводительной альтернативой защитной копии-то, что не является возможно с массивами.
ни один из ответов не имел информации, которая меня интересовала-повторяющееся сканирование одного и того же массива много-много раз. Пришлось создать тест JMH для этого.
результаты (Java 1.8.0_66 x32, итерация простого массива по крайней мере в 5 раз быстрее, чем ArrayList):
тест
Не попадайте в ловушку оптимизации без надлежащего бенчмаркинга. Как и другие предложили использовать профилировщик, прежде чем делать какие-либо предположения.
различные структуры данных, которые вы перечислили, имеют разные цели. Список очень эффективен при вставке элементов в начале и в конце, но сильно страдает при доступе к случайным элементам. Массив имеет фиксированное хранилище, но обеспечивает быстрый случайный доступ. Наконец, ArrayList улучшает интерфейс к массиву с помощью позволяя ему расти. Обычно используемая структура данных должна быть продиктована тем, как будут доступны или добавлены хранимые данные.
о потреблении памяти. Вы, кажется, смешивая некоторые вещи. Массив даст вам только непрерывный кусок памяти для типа данных, которые у вас есть. Не забывайте, что java имеет фиксированные типы данных: boolean, char, int, long, float и Object (это включает все объекты, даже массив является объектом). Это означает, что если вы объявляете массив string strings [1000] или MyObject myObjects [1000] вы получаете только 1000 ячеек памяти, достаточно больших для хранения местоположения (ссылок или указателей) объектов. Вы не получаете 1000 ящиков памяти, достаточно больших, чтобы соответствовать размеру объектов. Не забывайте, что ваши объекты сначала создаются «новые». Это когда распределение памяти сделано и позже ссылка (их адрес памяти) хранится в массиве. Объект не копируется в массив, только это ссылка.
массивы и списки могут иметь значение для примитивных типов, а не для объектов. Если вы заранее знаете количество элементов и не нуждаетесь в гибкости, массив из миллионов целых чисел или двойников будет более эффективным в памяти и незначительно в скорости, чем список, потому что действительно они будут храниться непрерывно и доступны мгновенно. Вот почему Java по-прежнему использует массивы символов для строк, массивы ints для данных изображений и т. д.
много микробных меток, приведенных здесь, нашли числа в несколько наносекунд для таких вещей, как чтение массива/ArrayList. Это вполне разумно, если все в кэше L1.
кэш более высокого уровня или доступ к основной памяти может иметь порядок раз что-то вроде 10nS-100nS, против больше, как 1nS для кэша L1. Доступ к ArrayList имеет дополнительную косвенную память, и в реальном приложении вы можете заплатить эту стоимость от почти никогда до каждого раза, в зависимости о том, что ваш код делает между доступами. И, конечно, если у вас много маленьких ArrayLists, это может добавить к вашей памяти и сделать его более вероятным, у вас будут промахи кэша.
оригинальный плакат, похоже, использует только один и получает доступ к большому количеству содержимого за короткое время, поэтому это не должно быть большим трудом. Но это может быть по-другому для других людей, и вы должны следить за интерпретацией микробных меток.
Я пришел сюда, чтобы получить лучшее представление о влиянии на производительность использования списков над массивами. Мне пришлось адаптировать код здесь для моего сценария: массив / список
1000 ints, используя в основном геттеры, что означает array[j] против list.get (j)
принимая лучшее из 7, чтобы быть ненаучным об этом (первые несколько со списком, где 2.5 x медленнее), я получаю это:
— итак, очень примерно на 30% быстрее с array
вторая причина публикации сейчас заключается в том, что никто не упоминает влияние, если вы делаете математику / матрицу / моделирование / оптимизационный код с вложенные петли.
скажем, у вас есть три вложенных уровня, и внутренний цикл в два раза медленнее, чем вы смотрите на 8 раз. Что-то, что будет работать в день, теперь занимает неделю.
*редактировать Довольно шокирован здесь, для пинков я попытался объявить int[1000] а не Integer[1000]
код для справки (звоните несколько раз):
Это зависит от того, как вы должны получить к нему доступ.
после хранения, Если вы в основном хотите выполнить операцию поиска, с небольшим количеством или без вставки / удаления, перейдите к массиву(как поиск выполняется в O (1) в массивах, тогда как добавление/удаление может потребовать повторного упорядочения элементов).
после хранения, Если ваша основная цель-добавить / удалить строки, с небольшим или без операции поиска, перейдите к списку.
Array быстрее, чем Array потому что ArrayList внутренне использует массив. если мы можем напрямую добавлять элементы в массив и косвенно добавлять элемент в Массив через ArrayList всегда напрямую механизм быстрее, чем косвенно механизм.
как размер ArrayList растет динамически?
(Обновление) С Java 7
кроме того, данные из старого массива копируются в новый массив.