java什么工作得更快：二维数组还是列表

Question

我手头有一个表演情况

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

你认为哪一个会更快，如果你能回答，为什么？还有没有办法加快执行速度

我的java -version给出：
java version "1.6.0_29"
Java(TM) SE Runtime Environment (build 1.6.0_29-b11)
Java HotSpot(TM) Client VM (build 20.4-b02, mixed mode, sharing)
操作系统是WindowsVista

Answer 1

这取决于您使用的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 2

阵列几乎肯定会更快

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

编辑以总结评论

• 名单的规模正在重新调整。这可能是个问题，也可能不是
• 性能差异趋于最小
• 应该对其进行基准测试，以便确定

对于这个用例，我相信阵列会更快。它是否能足够快地起作用是另一个问题，我对正在解决的实际问题知之甚少，无法对此做出判断

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

。。。当然，int[]也会占用更少的内存。如果可能，尝试使用字节[]或短[]来进一步减少内存使用

假设采用32位体系结构，12000x2000相当于91MB。如果字节足够，那么它将是大小的1/4。此外，可能还会有性能改进（取决于体系结构）

Answer 5

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

列表给你带来了一个非常重要的好处：它们可以自动增长。列表是指从一个集合复制到另一个集合（例如从地图复制到列表等）的集合

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

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

Answer 6

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

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

3）在处理了最重要瓶颈的应用程序中，许多应用程序的性能状况主要取决于处理器一级缓存未命中的数量。您可以将此视为您的应用程序经过合理优化的时刻。然而，你的算法可能仍然很糟糕，系统中可能仍有大量的繁忙工作在进行，你可以摆脱它们

4）假设你的算法不烂，你没有可以摆脱的主要工作，如果数组/列表的差异对你来说真的很重要，那么在这一点上，你将开始在性能数字中看到它

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

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