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

Question

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

Рейтинг: 4Ответов: 3Опубликовано: 25.04.2011

Что работает быстрее? Прогнал тест 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);
    }
  }
}

java

Источник: Stack Overflow на русском

Answer 1

▲ 11Принят

Обычный массив почти наверняка будет выигрывать в скорости как при доступе, так и при записи. Хотя бы потому, что при обращении к 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: как видно, частая ненужная сборка мусора приводит к двухкратному снижению производительности в данном тесте.

Answer 2

▲ 5

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

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

Answer 3

▲ 4

В данном тесте больше времени уходит на создание новых объектов во время теста

array[i] = new Object();

или

list.add(new Object());

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

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

Ответы