Массив или Список в Java. Что быстрее?

Question

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

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

Answer 1

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

Answer 2

«Тысячи» - это не большое количество. Несколько тысяч строк длиной абзаца имеют размер порядка нескольких мегабайт. Если все, что вы хотите сделать, это обращаться к ним последовательно, используйте неизменный односвязный список .

Answer 3

В зависимости от реализации. Возможно, что массив примитивных типов будет меньше и эффективнее, чем ArrayList. Это связано с тем, что массив будет хранить значения непосредственно в непрерывном блоке памяти, а простейшая реализация ArrayList будет хранить указатели на каждое значение. Особенно на 64-битной платформе это может иметь огромное значение.

Конечно, реализация jvm может иметь специальный случай для этой ситуации, и в этом случае производительность будет такой же.

Answer 4

Многие микробенчмарки, приведенные здесь, нашли числа в несколько наносекунд для таких вещей, как чтение массива / ArrayList. Это вполне разумно, если все находится в вашем кеше L1.

Доступ к кэшу более высокого уровня или доступу к основной памяти может иметь порядок времен порядка примерно от 10 нс до 100 нс, по сравнению с 1 нс для кеша L1. Доступ к ArrayList имеет дополнительное косвенное обращение к памяти, и в реальном приложении вы можете заплатить эту стоимость почти всегда, в зависимости от того, что ваш код делает между доступами. И, конечно, если у вас много маленьких списков ArrayList, это может увеличить использование памяти и повысить вероятность пропадания кэша.

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

Строки Java, однако, ужасно расточительны, особенно если вы храните много маленьких (просто посмотрите на них с помощью анализатора памяти, кажется, что> 60 байт для строки из нескольких символов). Массив строк имеет косвенную ссылку на объект String, а другой - от объекта String на char [], который содержит саму строку. Если что-то и взорвет ваш кэш L1, то это в сочетании с тысячами или десятками тысяч строк. Так что, если вы серьезно - действительно серьезно - о том, чтобы снизить как можно большую производительность, то вы можете посмотреть на это иначе. Вы могли бы, скажем, содержать два массива, char [] со всеми строками в нем, одну за другой, и int [] со смещениями в начале. Это будет PITA, чтобы делать что-нибудь, и вам почти наверняка это не нужно. И если вы это сделаете, вы выбрали не тот язык.

Answer 5

Не попадитесь в ловушку оптимизации без надлежащего бенчмаркинга. Как другие предложили использовать профилировщик, прежде чем делать какие-либо предположения.

Различные структуры данных, которые вы перечислили, имеют разные цели. Список очень эффективен при вставке элементов в начале и в конце, но сильно страдает при доступе к случайным элементам. Массив имеет фиксированное хранилище, но обеспечивает быстрый произвольный доступ. Наконец, ArrayList улучшает интерфейс массива, позволяя ему расти. Обычно структура данных, которая будет использоваться, должна быть продиктована тем, как будут храниться или добавляться сохраненные данные.

О потреблении памяти. Вы, кажется, смешиваете некоторые вещи. Массив даст вам непрерывный кусок памяти только для того типа данных, который у вас есть. Не забывайте, что java имеет фиксированные типы данных: логические, char, int, long, float и Object (сюда входят все объекты, даже массив является Object). Это означает, что если вы объявите массив строк String [1000] или MyObject myObjects [1000], вы получите только 1000 ящиков памяти, достаточно больших для хранения местоположения (ссылок или указателей) объектов. Вы не получите 1000 блоков памяти, достаточно больших, чтобы соответствовать размеру объектов. Не забывайте, что ваши объекты сначала создаются с «новым». Это когда распределение памяти сделано, и позже ссылка (их адрес памяти) сохраняется в массиве. Объект не копируется в массив, только его ссылка.

Answer 6

Я не думаю, что это имеет большое значение для строк. Что является непрерывным в массиве строк, так это ссылки на строки, сами строки хранятся в произвольных местах в памяти.

Массивы и списки могут иметь значение для примитивных типов, а не для объектов. ЕСЛИ вы заранее знаете количество элементов и не нуждаетесь в гибкости, массив миллионов целых или двойных чисел будет более эффективен в памяти и незначительно быстрее, чем список, потому что действительно они хранятся непрерывно и доступны сразу. Вот почему Java все еще использует массивы символов для строк, массивы целых для данных изображений и т. Д.

Answer 7

Массив быстрее - вся память заранее выделяется.

Answer 8

Список более гибкий .... так что лучше для List, чем для массива

Answer 9

Массивы - всегда было бы лучше, если бы нам приходилось быстрее получать результаты

Списки - Выполняет результаты по вставке и удалению, так как они могут быть сделаны в O (1), и это также предоставляет методы для добавления, извлечения и удаления данных. Намного проще в использовании.

Но всегда помните, что выборка данных будет быстрой, когда позиция индекса в массиве, где хранятся данные, известна.

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

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

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

Answer 10

ArrayList внутренне использует объект массива для добавления (или сохранения) элементы. Другими словами, ArrayList поддерживается данными Array -структура. Массив ArrayList имеет изменяемый размер (или динамический).

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

В классе ArrayList есть два перегруженных метода add ():
1. add(Object): добавляет объект в конец списка.
2. add(int index , Object ): вставляет указанный объект в указанную позицию в списке.

Как динамически увеличивается размер ArrayList?

public boolean add(E e)        
{       
     ensureCapacity(size+1);
     elementData[size++] = e;         
     return true;
}

Важный момент, который следует отметить из приведенного выше кода, заключается в том, что мы проверяем емкость ArrayList перед добавлением элемента. sureCapacity () определяет, каков текущий размер занятых элементов и каков максимальный размер массива. Если размер заполненных элементов (включая новый элемент, добавляемый в класс ArrayList) превышает максимальный размер массива, увеличьте размер массива. Но размер массива нельзя динамически увеличивать. Итак, что происходит внутри, это новый массив с емкостью

до Java 6

int newCapacity = (oldCapacity * 3)/2 + 1;

(обновление) с Java 7

 int newCapacity = oldCapacity + (oldCapacity >> 1);

также, данные из старого массива копируются в новый массив.

Наличие дополнительных методов в ArrayList, поэтому Array работает быстрее, чем ArrayList.