读取/存储大量多维数据的最快方法？(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-assignment

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

因此，还有一些改进的空间......但我真的不认为这值得你花时间。