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

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

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

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

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

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

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

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

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

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

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

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

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

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

• создать это
• установить предмет
• получить предмет
• клонировать / скопировать

Общий вывод

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

• операции по изменению размера списка (при вызове list.add(...)) являются дорогостоящими, и по возможности следует попытаться установить начальную емкость на адекватном уровне (обратите внимание, что та же проблема возникает при использовании массива)
• при работе с примитивами массивы могут быть значительно быстрее, поскольку они позволяют избежать многих преобразований в бокс / распаковку
• приложение, которое получает / устанавливает значения только в ArrayList (не очень часто!), может получить прирост производительности более чем на 25%, переключившись на массив

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

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

Array / 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 теста, выполнив следующие утверждения:

• GetList: 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 теста, выполнив следующие утверждения:

• Сет-лист: 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]

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

Клон / копия

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

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

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

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

Я предполагаю, что оригинальный постер взят из 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.

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

Однако, если вы выполняете постоянную, тяжелую итерацию с небольшими структурными изменениями (без добавления и удаления), например, для рендеринга программной графики или пользовательской виртуальной машины, мои сравнительные тесты с последовательным доступом показывают, что ArrayLists в 1,5 раза медленнее массивов на моем система (Java 1.6 на моем годовалом iMac).

Некоторый код:

import java.util.*;

public class ArrayVsArrayList {
    static public void main( String[] args ) {

        String[] array = new String[300];
        ArrayList<String> list = new ArrayList<String>(300);

        for (int i=0; i<300; ++i) {
            if (Math.random() > 0.5) {
                array[i] = "abc";
            } else {
                array[i] = "xyz";
            }

            list.add( array[i] );
        }

        int iterations = 100000000;
        long start_ms;
        int sum;

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += array[j].length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
        // Prints ~13,500 ms on my system

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += list.get(j).length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
        // Prints ~20,800 ms on my system - about 1.5x slower than direct array access
    }
}

Ну, во-первых, стоит уточнить, имеете ли вы в виду «список» в классическом понимании структур данных компа (т. Е. Связанный список) или вы имеете в виду java.util.List? Если вы имеете в виду java.util.List, это интерфейс. Если вы хотите использовать массив, просто используйте реализацию ArrayList, и вы получите поведение и семантику, подобные массиву. Задача решена.

Если вы имеете в виду массив против связанного списка, это немного другой аргумент, для которого мы возвращаемся к Big O (вот простое объяснение на английском, если это незнакомый термин.

Массив;

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

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

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

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

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

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

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

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

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();
        }
    }
}

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

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

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

intern
international
internationalize
internet
internets

Три будет хранить:

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

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

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

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

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

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

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

ОБНОВИТЬ:

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

Еще первые 1-2 прохода простой массив в 2-3 раза быстрее.

ОРИГИНАЛЬНАЯ ПОЧТА:

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

import java.util.List;
import java.util.Arrays;

public class IterationTest {

    private static final long MAX_ITERATIONS = 1000000000;

    public static void main(String [] args) {

        Integer [] array = {1, 5, 3, 5};
        List<Integer> list = Arrays.asList(array);

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i) {
//            for (int e : array) {
            for (int e : list) {
                test_sum += e;
            }
        }
        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }
}

И вот ответ:

На основе массива (строка 16 активна):

Time: 7064

На основании списка (строка 17 активна):

Time: 20950

Есть еще комментарии по поводу «быстрее»? Это вполне понятно. Вопрос в том, когда примерно в 3 раза быстрее, чем гибкость List. Но это другой вопрос. Кстати, я проверил это тоже на основе созданного вручную ArrayList. Почти тот же результат.

Поскольку здесь уже есть много хороших ответов, я хотел бы дать вам некоторую другую практическую информацию, а именно сравнение производительности вставки и итерации: примитивный массив против Linked-list в Java.

Это простая проверка производительности.
Таким образом, результат будет зависеть от производительности машины.

Исходный код, используемый для этого ниже:

import java.util.Iterator;
import java.util.LinkedList;

public class Array_vs_LinkedList {

    private final static int MAX_SIZE = 40000000;

    public static void main(String[] args) {

        LinkedList lList = new LinkedList(); 

        /* insertion performance check */

        long startTime = System.currentTimeMillis();

        for (int i=0; i<MAX_SIZE; i++) {
            lList.add(i);
        }

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");

        int[] arr = new int[MAX_SIZE];

        startTime = System.currentTimeMillis();
        for(int i=0; i<MAX_SIZE; i++){
            arr[i] = i; 
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        /* iteration performance check */

        startTime = System.currentTimeMillis();

        Iterator itr = lList.iterator();

        while(itr.hasNext()) {
            itr.next();
            // System.out.println("Linked list running : " + itr.next());
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        startTime = System.currentTimeMillis();

        int t = 0;
        for (int i=0; i < MAX_SIZE; i++) {
            t = arr[i];
            // System.out.println("array running : " + i);
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    }
}

Результат производительности ниже:

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

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

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

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

1. Если количество строк почти постоянно, используйте массив (или ArrayList). Но если число меняется слишком сильно, вам лучше использовать LinkedList.
2. Если есть (или будет) необходимость в добавлении или удалении элементов посередине, то вам обязательно нужно использовать LinkedList.

Я пришел сюда, чтобы лучше понять влияние использования списков на массивы на производительность. Мне пришлось адаптировать код здесь для моего сценария: массив / список ~ 1000 дюймов, используя в основном геттеры, то есть массив [j] против list.get (j)

Принимая лучшее из 7, чтобы быть ненаучным об этом (первые несколько со списком, где в 2,5 раза медленнее) я получаю это:

array Integer[] best 643ms iterator
ArrayList<Integer> best 1014ms iterator

array Integer[] best 635ms getter
ArrayList<Integer> best 891ms getter (strange though)

- так, примерно на 30% быстрее с массивом

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

Допустим, у вас есть три вложенных уровня, а внутренний цикл в два раза медленнее, чем при 8-кратном снижении производительности. То, что будет работать через день, теперь занимает неделю.

* РЕДАКТИРОВАТЬ Довольно шокирован здесь, для ударов я попытался объявить int [1000], а не Integer [1000]

array int[] best 299ms iterator
array int[] best 296ms getter

Использование Integer [] и int [] представляет двойной удар по производительности, ListArray с итератором в 3 раза медленнее, чем int []. Реально думал, что реализации списка Java были похожи на нативные массивы ...

Код для справки (звоните несколько раз):

    public static void testArray()
    {
        final long MAX_ITERATIONS = 1000000;
        final int MAX_LENGTH = 1000;

        Random r = new Random();

        //Integer[] array = new Integer[MAX_LENGTH];
        int[] array = new int[MAX_LENGTH];

        List<Integer> list = new ArrayList<Integer>()
        {{
            for (int i = 0; i < MAX_LENGTH; ++i)
            {
                int val = r.nextInt();
                add(val);
                array[i] = val;
            }
        }};

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i)
        {
//          for (int e : array)
//          for (int e : list)          
            for (int j = 0; j < MAX_LENGTH; ++j)
            {
                int e = array[j];
//              int e = list.get(j);
                test_sum += e;
            }
        }

        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }

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

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

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

Если вам нужна гибкость интерфейса List с добавлением и удалением элементов, остается вопрос, какую реализацию вы должны выбрать. Часто 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 - это способ объявить массив с обобщениями, и он может динамически расти. Но если удаление и вставка используются чаще, то связанный список - самая быстрая структура данных, которая будет использоваться.

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

Ознакомьтесь с рекомендациями Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056.

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

Ни один из ответов не содержал информацию, которая меня интересовала - многократное сканирование одного и того же массива много раз. Пришлось создать тест JMH для этого.

Результаты (Java 1.8.0_66 x32, итерация простого массива как минимум в 5 раз быстрее, чем ArrayList):

Benchmark                    Mode  Cnt   Score   Error  Units
MyBenchmark.testArrayForGet  avgt   10   8.121 ? 0.233  ms/op
MyBenchmark.testListForGet   avgt   10  37.416 ? 0.094  ms/op
MyBenchmark.testListForEach  avgt   10  75.674 ? 1.897  ms/op

Тестовое задание

package my.jmh.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Fork(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class MyBenchmark {

    public final static int ARR_SIZE = 100;
    public final static int ITER_COUNT = 100000;

    String arr[] = new String[ARR_SIZE];
    List<String> list = new ArrayList<>(ARR_SIZE);

    public MyBenchmark() {
        for( int i = 0; i < ARR_SIZE; i++ ) {
            list.add(null);
        }
    }

    @Benchmark
    public void testListForEach() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( String str : list ) {
                if( str != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testListForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( list.get(j) != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testArrayForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( arr[j] != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

}

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

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

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

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

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

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

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

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

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

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

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

Это зависит от того, как вы должны получить к нему доступ.

После сохранения, если вы в основном хотите выполнить операцию поиска, практически без вставки / удаления, перейдите к массиву (так как поиск выполняется в O (1) в массивах, тогда как для добавления / удаления может потребоваться переупорядочение элементов) ,

После сохранения, если ваша основная цель состоит в добавлении / удалении строк, практически без операции поиска, перейдите к списку.

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

Массив быстрее, чем Массив потому что ArrayList внутренне использует массив. Если мы можем напрямую добавить элементы в Array и косвенно добавить элемент в Array через 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) превышает максимальный размер массива, увеличьте размер массива. Но размер массива нельзя динамически увеличивать. Итак, что происходит внутри, это новый массив, созданный с емкостью

До Явы 6

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

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

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

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

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

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

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

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

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

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

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