Что работает быстрее: массив или ArrayList?

#java

Что работает быстрее? Прогнал тест 100 раз. Результаты всегда разные: то один быстрее,
то второй. Так есть ли реальный выигрыш в использовании массива вместо ArrayList? ArrayList
создавал с нужным размером сразу, чтобы время на "расширение" не тратилось.
Проверялось быстродействие команды add. Пытался понять, уменьшит ли замена ArrayList
на обычный массив в "узких местах" время выполнения (часто слышал такое предположение).
Если в моем случае всегда известен заранее размер массива/листа. Результаты получились
случайные. Иногда ArrayList значительно быстрее, иногда массив, иногда они равны.
import java.util.*;

public class Main {
  private static int COUNT = 1000000;

  private static double getPeriod(Runnable r) {
    System.gc();
    Date date = new Date();
    r.run();
    return (new Date().getTime() - date.getTime());
  }

  private static void testList(final List list) {
    double period = getPeriod(new Runnable() {
      public void run() {
        for (int i = 0; i < COUNT; i++) {
          list.add(new Object());
        }
      }
    });
    System.out.println("List " + period);
  }

  private static void testArray(final Object[] array) {
    double period = getPeriod(new Runnable() {
      public void run() {
        for (int i = 0; i < COUNT; i++) {
          array[i] = new Object();
        }
      }
    });
    System.out.println("Array " + period);
  }

  public static void main(String[] args) {
    for (int i = 0; i < 100; i++) {
      List arrayList = new ArrayList(COUNT);
      Object[] array = new Object[COUNT];

      testList(arrayList);
      testArray(array);
    }
  }
}
    

Ответы

Ответ 1

Обычный массив почти наверняка будет выигрывать в скорости как при доступе, так и
при записи. Хотя бы потому, что при обращении к ArrayList у вас лишний вызов метода,
а может и не один. С другой стороны, внутри ArrayList'а тот же самый массив и доступ
вполняется по тому же принципу, поэтому если нет чрезмерной нагрузки на него, то в
общем их производительность примерно одного порядка. 
Разница для вас в том, что с листами работать намного проще и удобнее, чем с массивами.
По этой причине вам не следует заниматься ерундой и гонять какие-то нелепые тесты,
а просто использовать ArrayList, если только у вас нет каких-то ОЧЕНЬ серьёзных оснований
использовать массив. Одно из таких оснований: вы точно знаете заранее размер массива
и вы точно знаете, что использование этого массива в коде ограничено и вам не придётся
городить огород, чтобы гонять потом эти массивы в листы и наоборот.
UPD Что за числа в вашем тесте детские? 1000.000? Это просто смешно. Я прогнал тест
на выполнение 10.000.000.000 добавлений и получил вот что:
primitive array: 78896 ms
array list: 132532 ms

Второй прогон
primitive array: 76832 ms
array list: 124047 ms

Исходный код теста  здесь . Как видно, массив почти вдвое быстрее списка и никакой
инлайнинг, рантайм-оптимизации не помогли, хотя, казалось бы, на большом интервале
вркемени эти все оптимизации должны были бы сработать и время могло бы выровняться. Но нет.
UPD2
Убрал сборку мусора вообще и перегруппировал нули и получил следующее
primitive array: 26177 ms
array list: 54482 ms

Результат очень стабилен. Думаю, на get результаты будут подобные.
UPD3
Кстати, вот показательный пример для любителей вызывать руками System.gc: как видно,
частая ненужная сборка мусора приводит к двухкратному снижению производительности в
данном тесте.


Ответ 2

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


Ответ 3

В данном тесте больше времени уходит на создание новых объектов во время теста
array[i] = new Object();

или
list.add(new Object());

Думаю, погрешность именно отсюда, так как создание объекта гораздо более трудоемкая
работа. 
Впрочем List, конечно, будет медленнее, ведь обращение к методу get (как и к любому
другому) - это сначала обращение к таблице виртуальных методов, затем сохранение регистров
в стеке и т.д. 
Лучше производить тест с заранее подготовленными данными.


Ответ 4

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


Ответ 5

Быстрее всего будет работать массив именно из примитивных типов данных. Большой массив
из обьектов лучше тоже делать просто так, ArrayList же - склоняюсь к тому что это разновидность
синтактического сахара не предназначенна для больших обьемов. Он при увеличении может
вдруг копировать себя, и т.п.
А добавлять в середину ArrayList массива - вообще ересь. Время добавления одного
элемента О(н) , в сумме О(н^^2). Для этого надо самому реализовать Linked List, причем
ссылки на следующий элемент держать не на элемент типа Object (как делают обычно в
Яве)  а на его индекс в массиве (то есть int или другой целый тип), без перемещения
самих обьектов Object.
Хух, надеюсь помог))