Array or List in Java. Which is faster?

Я должен хранить тысячи строк в памяти для последовательного доступа в Java. Должен ли я хранить их в массиве или мне следует использовать какой-то список?

Поскольку массивы хранят все данные в непрерывном фрагменте памяти (в отличие от списков), вызовет ли проблемы использование массива для хранения тысяч строк ?

Я предлагаю вам использовать профилировщик, чтобы проверить, что быстрее.

Мое личное мнение таково, что вам следует использовать списки.

Я работаю над большой базой кода, и предыдущая группа разработчиков везде использовала массивы. Это сделало код очень негибким. После замены больших фрагментов на списки мы не заметили разницы в скорости.

Способ Java заключается в том, что вы должны решить, какая абстракция данных наиболее соответствует вашим потребностям. Помните, что в Java список - это абстрактный, а не конкретный тип данных. Вы должны объявить строки как список, а затем инициализировать его с помощью реализации ArrayList .

List<String> strings = new ArrayList<String>();

Такое разделение абстрактного типа данных и конкретной реализации является одним из ключевых аспектов объектно-ориентированного программирования.

ArrayList реализует абстрактный тип данных List, используя массив в качестве своей базовой реализации. Скорость доступа практически идентична скорости доступа к массиву, с дополнительными преимуществами в виде возможности добавлять и вычитать элементы из списка (хотя это O (n) операция с ArrayList) и что, если вы решите изменить базовую реализацию позже, вы сможете. Например, если вы понимаете, что вам нужен синхронизированный доступ, вы можете изменить реализацию на вектор, не переписывая весь свой код.

Фактически, ArrayList был специально разработан для замены низкоуровневой конструкции array в большинстве контекстов. Если бы Java разрабатывалась сегодня, вполне возможно, что массивы были бы вообще исключены в пользу конструкции ArrayList .

Поскольку массивы хранят все данные в непрерывном фрагменте памяти (в отличие от списков), вызовет ли проблемы использование массива для хранения тысяч строк ?

В Java все коллекции хранят только ссылки на объекты, а не сами объекты. И arrays, и ArrayList будут хранить несколько тысяч ссылок в непрерывном массиве, поэтому они по сути идентичны. Вы можете считать, что непрерывный блок из нескольких тысяч 32-битных ссылок всегда будет легко доступен на современном оборудовании. Это, конечно, не гарантирует, что у вас не закончится память полностью, просто требование к непрерывному блоку памяти выполнить несложно.

Хотя ответы, предлагающие использовать ArrayList, действительно имеют смысл в большинстве сценариев, фактический вопрос об относительной производительности на самом деле не получил ответа.

Есть несколько вещей, которые вы можете сделать с массивом:

• создайте его


• задайте элемент


• получить элемент


• клонировать / копировать

Общий вывод

Хотя операции get и set выполняются несколько медленнее в ArrayList (соответственно 1 и 3 наносекунды на вызов на моей машине), накладные расходы при использовании ArrayList очень невелики по сравнению с массив для любого неинтенсивного использования. Однако следует иметь в виду несколько вещей:

• операции изменения размера списка (при вызове list.add(...)) являются дорогостоящими, и следует попытаться установить начальную емкость на адекватном уровне, когда это возможно (обратите внимание, что такая же проблема возникает при использовании массива)


• при работе с примитивами массивы могут быть значительно быстрее, поскольку они позволят избежать многих преобразований упаковки / распаковки


• приложение, которое получает / устанавливает значения только в ArrayList (не очень распространенное!) может получить прирост производительности более чем на 25% при переключении на массив

Подробные результаты

Вот результаты, которые я измерил для этих трех операций, используя библиотеку бенчмаркинга jmh (время в наносекундах) с JDK 7 на стандартном настольном компьютере x86. Обратите внимание, что размеры списков массивов никогда не изменяются в тестах, чтобы убедиться в сопоставимости результатов. Тестовый код доступен здесь.

Создание массива / ArrayList

Я провел 4 теста, выполнив следующие инструкции:

• createArray1: Integer[] array = new Integer[1];


• createList1: List<Integer> list = new ArrayList<> (1);


• createArray10000: Integer[] array = new Integer[10000];


• createList10000: List<Integer> list = new ArrayList<> (10000);

Результаты (в наносекундах на вызов, достоверность 95%):

a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]

Вывод: заметной разницы нет.

операции получения

Я провел 2 теста, выполнив следующие инструкции:

• Получить список: return list.get(0);


• getArray: return array[0];

Результаты (в наносекундах на вызов, достоверность 95%):

a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
a.p.g.a.ArrayVsList.getList    [3.841, 3.874]

Вывод: получение данных из массива примерно на 25% быстрее, чем получение данных из ArrayList, хотя разница составляет всего порядка одной наносекунды.

операции набора

Я провел 2 теста, выполнив следующие инструкции:

• setList: list.set(0, value);


• setArray: array[0] = value;

Результаты (в наносекундах за вызов):

a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
a.p.g.a.ArrayVsList.setList    [6.783, 6.877]

Вывод: операции set с массивами выполняются примерно на 40% быстрее, чем со списками, но, что касается get, каждая операция set занимает несколько наносекунд - поэтому, чтобы разница достигла 1 секунды, нужно было бы устанавливать элементы в списке / массиве сотни миллионов раз!

клонировать / копировать

Конструктор копирования ArrayList делегирует на Arrays.copyOf поэтому производительность идентична копированию массива (копирование массива через clone, Arrays.copyOf или System.arrayCopy не имеет существенного значения с точки зрения производительности).

Вам следует предпочесть универсальные типы массивам. Как упоминалось другими, массивы негибки и не обладают выразительной силой универсальных типов. (Однако они поддерживают проверку типов во время выполнения, но это плохо сочетается с универсальными типами.)

Но, как всегда, при оптимизации вы всегда должны следовать этим шагам:

• Не проводите оптимизацию, пока у вас не будет хорошей, чистой и рабочей версии вашего кода. Переход на универсальные типы вполне может быть мотивирован уже на этом этапе.


• Когда у вас есть хорошая и чистая версия, решите, достаточно ли она быстра.


• Если это недостаточно быстро, измерьте его производительность. Этот шаг важен по двум причинам. Если вы не будете измерять, вы не будете (1) знать влияние любых выполняемых вами оптимизаций и (2) знать, где оптимизировать.


• Оптимизируйте самую горячую часть вашего кода.


• Измерьте еще раз. Это так же важно, как и предыдущее измерение. Если оптимизация не улучшила ситуацию, отмените ее. Помните, код без оптимизации был чистым, приятным и работающим.