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

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

Так как массивы сохраняют все данные в непрерывном блоке памяти (в отличие от Списков), был бы, использование массива для хранения тысяч строк вызывает проблемы?

339
задан Jonas 13 November 2019 в 09:37
поделиться

0 ответов

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

Мое личное мнение - то, что необходимо использовать Списки.

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

350
ответ дан Fortyrunner 23 November 2019 в 00:36
поделиться

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

1
ответ дан Yakov Fain 23 November 2019 в 00:36
поделиться

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

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

1
ответ дан PhiLho 23 November 2019 в 00:36
поделиться

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

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

О потреблении памяти. Вы, кажется, смешиваете некоторые вещи. Массив только даст Вам непрерывный блок памяти для типа данных, которые Вы имеете. Не забывайте, что Java имеет фиксированные типы данных: булевской переменной, символом, интервалом, долго, плаванием и Объектом (это включает все объекты, даже массив, является Объект). Это означает, что, если Вы объявляете массив Строковых строк [1000] или MyObject myObjects [1000], Вы только заставляете 1 000 памятей поля, достаточно большие хранить местоположение (ссылки или указатели) объектов. Вы не заставляете 1 000 памятей поля, достаточно большие соответствовать размеру объектов. Не забывайте, что Ваши объекты сначала создаются с "новым". Это - когда выделение памяти сделано, и позже ссылка (их адрес памяти) хранится в массиве. Объект не становится скопированным в массив, только это - ссылка.

1
ответ дан potyl 23 November 2019 в 00:36
поделиться

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

2
ответ дан Apocalisp 23 November 2019 в 00:36
поделиться

Если Вы будете знать заранее, насколько большой данные являются затем массивом, будет быстрее.

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

3
ответ дан TofuBeer 23 November 2019 в 00:36
поделиться

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

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

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

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

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

Так как массивы сохраняют все данные в непрерывном блоке памяти (в отличие от Списков), был бы, использование массива для хранения тысяч строк вызывает проблемы?

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

160
ответ дан cygil 23 November 2019 в 00:36
поделиться

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

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

  • Не оптимизируйте, пока у Вас не будет хорошей, чистой, и рабочей версии Вашего кода. Изменение на универсальные типы уже могло очень хорошо быть мотивировано на этом шаге.
  • Когда у Вас есть версия, которая является хорошей и чистой, решите, достаточно ли это быстро.
  • Если это не достаточно быстро, измерьте его уровень. Этот шаг важен по двум причинам. Если Вы не будете иметь размеры, то Вы не будете (1) знать влияние никакой оптимизации, которую Вы делаете и (2) знать, где оптимизировать.
  • Оптимизируйте самую горячую часть своего кода.
  • Имейте размеры снова. Это столь же важно как имеющий размеры прежде. Если оптимизация не улучшила вещи, возвращается он. Помните, код без оптимизации был чистым, хорошим, и работа.
94
ответ дан Kelmikra 23 November 2019 в 00:36
поделиться

Я предполагаю, что исходный плакат прибывает из C++ / фон STL, который вызывает некоторый беспорядок. В C++ std::list двунаправленный связанный список.

В Java [java.util.]List интерфейс без реализаций (чистый абстрактный класс в терминах C++). List может быть двунаправленный связанный список - java.util.LinkedList обеспечивается. Однако 99 раз из 100, когда Вы хотите делание нового List, Вы хотите использовать java.util.ArrayList вместо этого, который является грубым эквивалентом C++ std::vector. Существуют другие стандартные реализации, такие как возвращенные java.util.Collections.emptyList() и java.util.Arrays.asList().

С точки зрения производительности существует очень маленький хит из необходимости пройти интерфейс и дополнительный объект, однако встраивание во время выполнения означает, что это редко имеет любое значение. Также помните это String обычно объект плюс массив. Таким образом для каждой записи, у Вас, вероятно, есть два других объекта. В C++ std::vector<std::string>, хотя копируя значением без указателя как такового, символьные массивы сформируют объект для строки (и они не будут обычно совместно использоваться).

Если этот конкретный код действительно чувствителен к производительности, Вы могли бы создать сингл char[] массив (или даже byte[]) для всех символов всех строк и затем массива смещений. IIRC, это - то, как javac реализован.

24
ответ дан Tom Hawtin - tackline 23 November 2019 в 00:36
поделиться

список медленнее, чем массивы. Если Вам нужны массивы использования эффективности. Если Вам нужен список использования гибкости.

4
ответ дан Warrior 23 November 2019 в 00:36
поделиться

Я записал немного сравнительного теста для сравнения ArrayLists с Массивами. На моем староватом ноутбуке время для пересечения через arraylist с 5000 элементами, 1000 раз, было приблизительно 10 миллисекундами медленнее, чем код эквивалентного массива.

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

n.b. Я действительно замечал то использование for String s: stringsList было приблизительно на 50% медленнее, чем использование старого стиля для цикла для доступа к списку. Пойди разберись... Вот две функции, которые я синхронизировал; массив и список были заполнены 5 000 случайных (различных) строк.

private static void readArray(String[] strings) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < strings.length; i++) {
            totalchars += strings[i].length();

        }
    }
}

private static void readArrayList(List<String> stringsList) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < stringsList.size(); i++) {
            totalchars += stringsList.get(i).length();
        }
    }
}
11
ответ дан Chris May 23 November 2019 в 00:36
поделиться

Хорошо во-первых это стоит разъяснить, делают Вы имеете в виду "список" в классическом смысле структур данных науки аккомпанемента (т.е. связанный список) или делаете Вы имеете в виду java.util. Список? Если Вы имеете в виду java.util. Список, это - интерфейс. Если Вы хотите использовать массив, просто используют реализацию ArrayList, и Вы получите подобное массиву поведение и семантику. Проблема решена.

Если Вы имеете в виду массив по сравнению со связанным списком, это - немного отличающийся аргумент, для которого мы возвращаемся к Большому O (вот простое английское объяснение, если это - незнакомый термин.

Массив;

  • Произвольный доступ: O (1);
  • Вставьте: O (n);
  • Удалите: O (n).

Связанный список:

  • Произвольный доступ: O (n);
  • Вставьте: O (1);
  • Удалите: O (1).

Таким образом, Вы выбираете, какой бы ни лучшие иски, как Вы изменяете размер своего массива. Если Вы изменяете размер, вставляете и удаляете много затем, возможно, связанный список является лучшим выбором. То же идет для того, если произвольный доступ редок. Вы упоминаете последовательный доступ. При основном выполнении последовательного доступа с очень небольшой модификацией затем, это, вероятно, не имеет значения, который Вы выбираете.

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

11
ответ дан Community 23 November 2019 в 00:36
поделиться

Если Вы имеете тысячи, рассматриваете использование trie. trie является древовидной структурой, которая объединяет общие префиксы сохраненной строки.

Например, если строки были

intern
international
internationalize
internet
internets

trie сохранил бы:

intern
 -> \0
 international
 -> \0
 -> ize\0
 net
 ->\0
 ->s\0

Строки требуют 57 символов (включая пустой разделитель, '\0') для устройства хранения данных, плюс то, что размер Строкового объекта, который содержит их. (По правде говоря, мы должны, вероятно, вокруг всех размеров до кратных чисел 16, но...), Вызов это 57 + 5 = 62 байта, примерно.

trie требует 29 (включая пустой разделитель, '\0') для устройства хранения данных, плюс sizeof trie узлы, которые являются касательно к массиву и списку дочерних trie узлов.

Для этого примера, который, вероятно, выходит о том же; для тысяч это, вероятно, выходит меньше, пока у Вас действительно есть общие префиксы.

Теперь, при использовании trie в другом коде, необходимо будет преобразовать в Строку, вероятно, с помощью StringBuffer в качестве посредника. Если многие строки используются сразу как Строки вне trie, это - потеря.

Но если Вы только используете некоторых в то время, когда - говорят, для поиска вещей в словаре - trie может сохранить Вас много пространства. Определенно меньше пространства, чем хранение их в HashSet.

Вы говорите доступ к ним "последовательно" - если это означает последовательно в алфавитном порядке, trie также, очевидно, дает Вам алфавитное распоряжение бесплатно при итерации его в глубину.

6
ответ дан tpdi 23 November 2019 в 00:36
поделиться

Помните, что ArrayList инкапсулирует массив, таким образом, существует мало различия по сравнению с использованием примитивного массива (за исключением того, что Список намного легче работать с в Java).

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

4
ответ дан Nuoji 23 November 2019 в 00:36
поделиться

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

  1. Если количество строк является почти постоянным, затем используют массив (или ArrayList). Но если число варьируется слишком много затем, необходимо использовать LinkedList.
  2. Если существует (или будет), потребность в добавлении или удалении элементов в середине, то, конечно, необходимо использовать LinkedList.
4
ответ дан Emre 23 November 2019 в 00:36
поделиться

Нет, потому что технически, массив только хранит ссылку на строки. Сами строки выделяются в другом месте. Для тысячи объектов я сказал бы, что список будет лучше, это медленнее, но это предлагает больше гибкости, и легче использовать, особенно если Вы собираетесь изменить размер их.

6
ответ дан CookieOfFortune 23 November 2019 в 00:36
поделиться

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

-3
ответ дан RV. 23 November 2019 в 00:36
поделиться
Другие вопросы по тегам:

Похожие вопросы: