Что работает быстрее: двумерные массивы или списки списков

Question

У меня есть ситуация с производительностью под рукой.

У меня есть огромное количество данных, которые должны храниться в памяти в формате двумерной таблицы (12000 X 2000).Теперь, насколько мне известно, я могу использовать int[][] или List<List<Integer>>.И, конечно же, я получаю доступ к значениям, используя int[i][j] или list.get(i).get(j).Я перебираю все данные как минимум пять раз.

Какой из них, по вашему мнению, будет работать быстрее и, если вы можете ответить, почему?Также есть ли способ ускорить выполнение?

My java -version дает:java version "1.6.0_29"<br/> Java(TM) SE Runtime Environment (build 1.6.0_29-b11)<br/> Java HotSpot(TM) Client VM (build 20.4-b02, mixed mode, sharing)ОС Windows Vista.

Answer 1

Массив почти наверняка будет быстрее.

Использование ArrayList повысит производительность, так как поддерживается фактическим массивом.

Изменить, чтобы суммировать комментарии

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

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

Answer 2

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

2) Не забудьте структурировать свой тест таким образом, чтобы компилятор JIT включил код, который вас интересует. 10000 итераций метода обычно необходимы перед компиляцией метода. Сравнительный анализ кода в интерпретируемом режиме - это пустая трата времени.

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

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

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

tl; dr version : Читать длинную версию. Д-ру не место в обсуждении производительности Java - это тонкие и сложные вещи, и нюансы имеют значение.

Answer 3

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

Результаты:

Results summary: 
Geo. Mean Primitive Array time:  0.7010723914083877 ms
Geo. Mean Boxed Array time:  2.517326382701606 ms
Geo. Mean ArrayList time:  1.1690484729741475 ms
Geo. Mean LinkedList time:  2.3522075667709146 ms

Код:

import java.lang.ref.WeakReference;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * User: shams
 * Date: 11/23/11
 * Time: 9:30 AM
 */
public class Benchmark {

   public static void main(String[] args) {

      final int ROW_SIZE = 1200;
      final int COL_SIZE = 200;
      final int numIterations = 10;

      final List<Double> arrayPrimitiveTimes = new LinkedList<Double>();
      final List<Double> arrayBoxedTimes = new LinkedList<Double>();
      final List<Double> linkedListTimes = new LinkedList<Double>();
      final List<Double> arrayListTimes = new LinkedList<Double>();

      for (int i = 0; i < numIterations; i++) {

         {
            tryGarbageCollection();
            startReportingTime();
            final int[][] dataArray = new int[ROW_SIZE][COL_SIZE];
            runPrimitiveArrayCode(dataArray);
            arrayPrimitiveTimes.add(endReportingTime("Primitive Array time: "));
         }
         {
            tryGarbageCollection();
            startReportingTime();
            final Integer[][] dataArray = new Integer[ROW_SIZE][COL_SIZE];
            runBoxedArrayCode(dataArray);
            arrayBoxedTimes.add(endReportingTime("Boxed Array time: "));
         }
         {
            tryGarbageCollection();
            startReportingTime();
            final List<List<Integer>> arrayList = new ArrayList<List<Integer>>(ROW_SIZE);
            for (int r = 0; r < ROW_SIZE; r++) {
               arrayList.add(new ArrayList<Integer>(COL_SIZE));
            }
            runListCode(arrayList);
            arrayListTimes.add(endReportingTime("ArrayList time: "));
         }
         {
            tryGarbageCollection();
            startReportingTime();
            final List<List<Integer>> arrayList = new LinkedList<List<Integer>>();
            for (int r = 0; r < ROW_SIZE; r++) {
               arrayList.add(new LinkedList<Integer>());
            }
            runListCode(arrayList);
            linkedListTimes.add(endReportingTime("LinkedList time: "));
         }
      }

      System.out.println("\n\n Results summary: ");
      printResult("Geo. Mean Primitive Array time: ", getMiddleGeoMeanTime(arrayPrimitiveTimes));
      printResult("Geo. Mean Boxed Array time: ", getMiddleGeoMeanTime(arrayBoxedTimes));
      printResult("Geo. Mean ArrayList time: ", getMiddleGeoMeanTime(arrayListTimes));
      printResult("Geo. Mean LinkedList time: ", getMiddleGeoMeanTime(linkedListTimes));
   }

   private static void runPrimitiveArrayCode(final int[][] dataArray) {
      for (int i = 0; i < dataArray.length; i++) {
         int[] cached = dataArray[i];
         for (int j = 0; j < cached.length; j++) {
            cached[j] = cached[j] + i + j;
         }
      }
   }

   private static void runBoxedArrayCode(final Integer[][] dataArray) {
      for (int i = 0; i < dataArray.length; i++) {
         Integer[] cached = dataArray[i];
         for (int j = 0; j < cached.length; j++) {
            Integer oldData = cached[j]; // dummy read
            cached[j] = i + j + (oldData == null ? 0 : 1);
         }
      }
   }

   private static void runListCode(final List<List<Integer>> dataArray) {
      for (int i = 0; i < dataArray.size(); i++) {
         final List<Integer> cached = dataArray.get(i);
         for (int j = 0; j < cached.size(); j++) {
            cached.set(j, cached.get(j) + i + j);
         }
      }
   }


   public static void tryGarbageCollection() {
      int count = 0;
      int limit = 2;
      while (count < limit) {
         count += 1;
         // println("enforceGarbageCollection: starting enforce of GC")

         int attempts = 0;
         WeakReference<Object> wr = new WeakReference<Object>(new Object());
         while (wr.get() != null && attempts < 25) {
            // add some delay
            int busy = 0;
            while (busy < 100) {
               busy += 1;
               wr.get();
            }
            new Object();
            System.out.print(".");
            System.gc();
            attempts += 1;
         }
         // println("enforceGarbageCollection: done GC")
      }
   }

   private static long startTime = 0;

   public static void startReportingTime() {
      startTime = System.nanoTime();
   }

   public static double endReportingTime(String msg) {
      long newTime = System.nanoTime();
      double execTime = (newTime - startTime) / 1e6;
      System.out.println(msg + execTime + "ms");
      return execTime;
   }

   public static double getBestTime(List data) {
      if (data.isEmpty()) {
         return 0;
      } else {
         java.util.Collections.sort(data);
         return ((Double) data.get(0)).doubleValue();
      }
   }

   public static double getMiddleGeoMeanTime(List<Double> data) {
      java.util.Collections.sort(data);
      List<Double> sortedResult = data;
      double midValuesProduct = 1.0;
      int midValuesCount = 0;
      for (int i = 1; i < sortedResult.size() - 1; i++) {
         midValuesCount += 1;
         midValuesProduct *= sortedResult.get(i).doubleValue();
      }
      final double average;
      if (midValuesCount > 0) {
         average = Math.pow(midValuesProduct, 1.0 / midValuesCount);
      } else {
         average = 0.0;
      }
      return average;
   }

   public static void printResult(String msg, double timeInMs) {
      System.out.println(msg + " " + timeInMs + " ms");
   }
}

Answer 4

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

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

int list[][] = new int[12000][2000];
//--or--
List<List<Integer>> list = new ArrayList<List<Integer>>(12000);
for (int i = 0; i < 12000; i++){
  list.add(new ArrayList<Integer>(2000));
}

Answer 5

... конечно, int [] [] тоже будет использовать меньше памяти.Если возможно, попробуйте использовать byte [] [] или short [] [] для дальнейшего сокращения использования памяти.

При условии 32-разрядной архитектуры, 12000x2000 соответствует 91 МБ.Если байтов достаточно, то это будет 1/4 размера.Кроме того, могут быть и улучшения производительности (в зависимости от архитектуры).

Answer 6

Если в списке реализовано RandomAccess (например, ArrayList), это почти не приводит к снижению производительности.Если вы используете LinkedList, произвольный доступ к его членам может быть очень дорогим.

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

И последнее замечание.Я думаю, что и N-мерные массивы, и список не лучший выбор.Если вам нужно N измерений, где N> 1, создайте класс и сохраните его экземпляры в одномерном массиве или коллекции.

Answer 7

Здесь идет обширное обсуждение:

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

Вот вывод теста:

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

Answer 8

Я думаю, что двумерный массив будет быстрее в большинстве случаев, но почему бы вам не проверить его на вашей конкретной проблеме?