Java中多维数组的遍历性能

在代码和下面的结果中，我们可以看到"Traverse2"比"Traverse1"快得多，实际上它们只是遍历相同数量的元素。

1.这种差异是如何发生的？

2.把较长的迭代放在较短的迭代中会有更好的性能吗？

public class TraverseTest {
    public static void main(String[] args)
    {
        int a[][] = new int[100][10];
        System.out.println(System.currentTimeMillis());
        //Traverse1
        for(int i = 0; i < 100; i++)
        {
            for(int j = 0; j < 10; j++)
                a[i][j] = 1;
        }
        System.out.println(System.currentTimeMillis());
        //Traverse2
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 100; j++)
                a[j][i] = 2;
        }
        System.out.println(System.currentTimeMillis());
    }
}

结果：

1347116569345

1347116569360

如果我把它改成

System.out.println(System.nanoTime());

结果将是：

48888285195629

488285846760

48888285914219

这意味着，如果我们在内部放置更长的交互，将有更好的性能。它似乎与缓存命中理论有一些冲突。

我怀疑您在这个微基准测试中看到的结果中的任何奇怪之处都是由于基准测试本身的缺陷造成的。

例如：

您的基准测试没有考虑"JVM预热"的影响，例如JIT编译器不会立即编译为本机代码。（这种情况只有在代码执行了一段时间后才会发生，JVM已经测量了一些使用次数来帮助优化。）处理这种情况的正确方法是将整个批次放入运行几次的循环中，并丢弃任何看起来"奇怪"的初始时间集。。。由于预热效应。
在理论上，您的基准中的循环可以被优化掉。JIT编译器可能能够推断出它们不做任何影响程序输出的工作。

最后，我只想提醒你，像这样的手动优化通常是个坏主意。。。除非您有令人信服的证据表明值得手动优化，并且此代码确实是应用程序花费大量时间的地方。

首先，始终在一个循环中运行多次微基准测试。然后您会看到这两个时间都是0，因为数组大小太小。若要获得非零时间，请将数组大小增加100倍。我的时间对于Traverse1大约是32毫秒，对于Traverse2大约是250毫秒。区别在于处理器使用高速缓存。访问顺序存储器地址要快得多。

我的输出（原始代码100i/10j与10i/100j）：

1347118083906
1347118083906
1347118083906

您使用了非常糟糕的时间分辨率进行快速计算。

我把I和j的限制都改为1000。

    int a[][] = new int[1000][1000];
    System.out.println(System.currentTimeMillis());
    //Traverse1
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[i][j] = 1;
    }
    System.out.println(System.currentTimeMillis());
    //Traverse2
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[j][i] = 2;
    }
    System.out.println(System.currentTimeMillis());

输出：

1347118210671
1347118210687 //difference is 16 ms
1347118210703 //difference is 16 ms again -_-

两种可能性：

Java热点将第二个循环更改为第一种类型或进行优化交换i和j
时间分辨率仍然不够

所以我将输出更改为System.nanoTime（）

    int a[][] = new int[1000][1000];
    System.out.println(System.nanoTime());
    //Traverse1
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[i][j] = 1;
    }
    System.out.println(System.nanoTime());
    //Traverse2
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[j][i] = 2;
    }
    System.out.println(System.nanoTime());

输出：

16151040043078
16151047859993 //difference is 7800000 nanoseconds
16151061346623 //difference is 13500000 nanoseconds --->this is half speed

1.这种差异是如何发生的？

请注意，即使您只是使用了错误的时间分辨率，您也会对不相等的情况进行错误的比较。第一个是连续访问，而第二个不是。

假设第一个嵌套循环只是为第二个循环做准备的一个加热，那么它会让你认为"第二个更快"的假设更加错误。

不要忘记，2D数组在java中是"数组的数组"。因此，最右边的索引将显示一个连续的区域。第一个版本更快。

2.把较长的迭代放在较短的迭代中会有更好的性能吗？

for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 100; j++)
            a[j][i] = 2;
    }

增加第一个索引的速度较慢，因为下一次迭代会减少千字节，因此您无法再使用缓存线。

绝对不是！

在我看来，数组的大小也会影响结果。类似：

public class TraverseTest {
    public static void main(String[] args)
    {
        int a[][] = new int[10000][2];
        System.out.println(System.currentTimeMillis());
        //Traverse1
        for(int i = 0; i < 10000; i++)
        {
            for(int j = 0; j < 2; j++)
                a[i][j] = 1;
        }
        System.out.println(System.currentTimeMillis());
        //Traverse2
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 10000; j++)
                a[j][i] = 2;
        }
        System.out.println(System.currentTimeMillis());
    }
}

Traverse1需要1000*3+1=30001比较来决定是否退出迭代，然而Traverse2只需要2*10001+1=2003比较。

Traverse1需要Traverse2的1.5倍比较次数。

相关内容

最新更新

热门标签：