读取/存储大量多维数据的最快方法？（Java）

Question

关于三个嵌套循环，我有三个问题：

for (int x=0; x<400; x++)
{
    for (int y=0; y<300; y++)
    {
        for (int z=0; z<400; z++)
        {
             // compute and store value
        }
    }
}

而且我需要存储所有计算值。我的标准方法是使用3D阵列：

values[x][y][z] = 1; // test value

但是事实证明这很慢：完成此循环需要192毫秒，其中需要一个int分配

int value = 1; // test value

仅需66毫秒。

1）为什么数组这么慢？
2）为什么当我将其放入内部循环时它变得更慢：

values[z][y][x] = 1; // (notice x and z switched)

这需要4秒钟以上！

3）最重要的是：我可以使用一种数据结构，该结构与分配单个整数一样快，但是可以存储与3D数组一样多的数据？

Answer 1

1）为什么数组这么慢？

正如其他人指出的那样，您正在将苹果与橙子进行比较。三重数组很慢，因为它需要解引用三次（至少在内部-是的，“
Java中没有指针”）。但是再一次，您不能引用单个整数变量…

2）为什么当我将其放入内部循环时它变得更慢：

values[z][y][x] = 1; // (notice x and z switched)

因为您降低了缓存一致性。变化最快的索引应该是最后一个索引，以便大多数内存访问在同一缓存块内彼此相邻发生，而不是强迫处理器等待直到从主RAM中读取这些块。

3）最重要的是：我可以使用一种数据结构，该结构与分配单个整数一样快，但是可以存储与3D数组一样多的数据？

否。没有这样的结构，因为整数变量适合机器寄存器（甚至比处理器的内存高速缓存还快），并且始终可以比您要提及的任何其他事物更快地访问。处理器速度比主存储器速度快得多。如果您的“工作集”（您需要对其进行操作的数据）不适合寄存器或高速缓存，则您将不得不付出一定的代价才能从RAM（或更糟的是从磁盘）中获取数据。

话虽这么说，Java会对每个数组访问进行边界检查，而且似乎对优化边界检查并不聪明。以下比较可能是有趣的：

public static long test1(int[][][] array) {
    long start = System.currentTimeMillis();
    for ( int x = 0; x < 400; x++ ) {
        for ( int y = 0; y < 300; y++ ) {
            for ( int z = 0; z < 400; z++ ) {
                array[x][y][z] = x + y + z;
            }
        }
    }
    return System.currentTimeMillis() - start;
}

public static long test2(int [] array) {
    long start = System.currentTimeMillis();
    for ( int x = 0; x < 400; x++ ) {
        for ( int y = 0; y < 300; y++ ) {
            for ( int z = 0; z < 400; z++ ) {
                array[z + y*400 + x*400*300] = x + y + z;
            }
        }
    }
    return System.currentTimeMillis() - start;
}

public static void main(String[] args) {

    int[][][] a1 = new int[400][300][400];
    int[] a2 = new int[400*300*400];
    int n = 20;

    System.err.println("test1");
    for (int i=0; i<n; i++) {
        System.err.print(test1(a1) + "ms ");
    }
    System.err.println();
    System.err.println("test2");
    for (int i=0; i<n; i++) {
        System.err.print(test2(a2) + "ms ");
    }
    System.err.println();
}

在我的系统上，输出是

test1
164ms 177ms 148ms 149ms 148ms 147ms 150ms 151ms 152ms 154ms 151ms 150ms 148ms 148ms 150ms 148ms 150ms 148ms 148ms 149ms 
test2
141ms 153ms 130ms 130ms 130ms 133ms 130ms 130ms 130ms 132ms 129ms 131ms 130ms 131ms 131ms 130ms 131ms 130ms 130ms 130ms

因此，仍有一些改进的余地…但是我真的不认为这值得您花时间。