什么更快：二维数组或列表列表

Question

我手头有一个绩效情况。

我有大量数据以二维表格式（12000 X 2000）保存在内存中。现在，据我所知，我可以使用 int[][] 或 List> 。当然，我使用 int[i][j] 或 list.get(i).get(j) 访问值。我将整个数据循环至少五次。

您认为哪一种效果更快？如果您能回答，为什么？还有什么办法可以加快执行速度吗？

我的 java -version 给出：
java 版本“1.6.0_29”
Java(TM) SE 运行时环境（内部版本 1.6.0_29-b11）
Java HotSpot(TM) 客户端 VM（版本 20.4-b02，混合模式，共享）
操作系统是Windows Vista。

Answer 1

阵列几乎肯定会更快。

使用 ArrayList 将使性能更加一致，因为它由实际数组支持。

编辑总结评论

• 列表可以调整大小。可能是也可能不是问题。
• 性能差异往往最小。
• 应该对其进行基准测试才能确定。

对于这个用例，我相信数组会明显更快。它是否足够快重要是一个不同的问题，而且我对正在解决的实际问题了解不够，无法对此做出判断。

Answer 2

1) 对整个应用程序进行基准测试。不要假设您知道应用程序中的性能瓶颈在哪里。经验一次又一次地表明，人类在这方面通常很糟糕。在与生产相同的硬件和系统上执行此操作，否则您就是在浪费时间。

2) 不要忘记以 JIT 编译器启动您关心的代码的方式构建您的基准测试。在编译方法之前，通常需要对方法进行 10000 次迭代。对解释模式代码进行基准测试完全是浪费时间。

3) 在已解决最重要瓶颈的应用程序中，许多应用程序将处于性能状况由处理器 L1 高速缓存未命中数主导的状态。您可以将此视为您的应用程序经过合理调整的点。然而，您的算法可能仍然很糟糕，并且系统中可能仍然有大量您可以摆脱的繁忙工作。

4）假设你的算法并不糟糕，并且你没有可以摆脱的大量忙碌工作，如果数组/列表差异对你来说确实很重要，那么此时你将开始看到它在性能数字中。

5）大多数情况下，你会发现数组的一级缓存情况会比列表更好。然而，这是一般建议，不要误认为是实际的性能调整建议。生成您自己的性能数据并对其进行分析。

tl;dr version：阅读长版本。 tl;dr 在 Java 性能讨论中没有地位——这是微妙而复杂的东西，细微差别很重要。

Answer 3

如果列表实现了RandomAccess（例如ArrayList），它几乎不会导致任何性能下降。如果您使用 LinkedList 随机访问其成员可能会非常昂贵。

列表给你带来了一个非常大的好处：它们可以自动增长。列表是一种集合，可以为您从一个集合复制到另一个集合（例如从地图到列表等）提供一定的好处。

因此，您的选择应该取决于您是否需要列表自动增长以及性能问题是否是对你来说确实非常重要。在大多数情况下，情况并非如此。

最后一句话。我认为N维数组和列表都不是最好的选择。如果您需要 N 维，其中 N>1 创建类并将其实例存储到一维数组或集合中。

Answer 4

...当然，int[][]也会使用更少的内存。如果可能的话，尝试使用byte[][]或short[][]来进一步减少内存使用。

假设 32 位架构，12000x2000 相当于 91MB。如果字节足够，则大小将为 1/4。此外，还可能有性能改进（取决于架构）。

Answer 5

这取决于您使用的 List 实现。如果您使用 ArrayList（大多数人使用的），那么性能基本上与数组相同。但如果您使用 LinkedList，那么性能会明显变差，因为 LinkedList 在随机访问时非常慢。

创建数据时，如果您使用 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 6

这是一个简单的基准测试，显示原始数组要快得多。
不过，装箱的成本会让阵列变慢。

结果：

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 7

我认为二维数组在大多数情况下会更快，但为什么不在您的具体问题上测试它呢？

Answer 8

这里有对此进行了广泛的讨论：

Java 中的数组或列表。哪个更快？

这是基准结论：

我写了一个小基准来比较 ArrayList 和 Array。在我的
老式笔记本电脑，遍历 5000 个元素的数组列表的时间，
1000倍，比同等阵列慢约10毫秒
代码。