哪个更快:二维数组或列表的列表

我手头有一个性能问题。

我有大量的数据以二维表格式(12000 X 2000)保存在内存中。现在就我所知，我可以用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)
操作系统是Windows Vista。

数组几乎肯定会更快。

使用ArrayList将使性能更内联，因为它是由一个实际的数组支持的。

编辑总结注释

列表重新调整大小。这可能是个问题，也可能不是。
性能差异趋于最小。
应该进行基准测试以确定。

对于这种情况，我相信数组将明显更快。是否足够快matter是另一个问题，我对正在解决的实际问题了解不够，无法对此做出判断。

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

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

3)在处理了最重要瓶颈的应用程序中，许多应用程序将处于性能配置文件由处理器L1缓存丢失数量主导的状态。您可以将此视为应用程序合理调优的点。然而，你的算法可能仍然很糟糕，系统中可能仍然有大量的工作需要你处理。

4)假设你的算法不糟糕，你没有主要的繁重工作可以摆脱，如果数组/列表的差异对你来说真的很重要，那么在这一点上，你会开始看到它的百分比。

5)在大多数情况下，您会发现L1缓存情况对于数组比对于列表要好。但是，这是一般的建议，不要误认为是实际的性能调优建议。生成你自己的分数并分析它们。

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

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

列表给你带来一个非常重要的好处:它们可以自动增长。列表是集合，在从一个集合复制到另一个集合(例如从map到list等)时，它给你带来了一定的好处。

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

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

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

假设是32位架构，12000x2000等于91MB。如果字节足够，那么它将是大小的1/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));
}

下面是一个简单的基准测试，它显示了原始数组的速度要快得多。装箱的代价会使数组变慢。

结果:

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("nn 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");
   }
}

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

这里有一个广泛的讨论:

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

这是基准结论:

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

相关内容

最新更新

热门标签：