为什么我的嵌套 for 循环需要这么长时间来计算？

Question

我有一个代码可以生成 0 到 36 之间的 4 个整数的所有可能组合。

这将是 37^4 个数字 = 1874161。

我的代码是用 MATLAB 编写的：

i=0;
for a = 0:36
    for b= 0:36
        for c = 0:36
            for d = 0:36
                i=i+1;
                combination(i,:) = [a,b,c,d];             
            end          
        end
    end
end

我已经使用数字 3 而不是数字 36 对此进行了测试，并且效果很好。

如果有 1874161 种组合，并且过度谨慎地猜测 100 个时钟周期来进行加法和写入值，那么如果我有一台 2.3GHz PC，则为：

1874161 * (1/2300000000) * 100 = 0.08148526086

几分之一秒。但是到现在已经运行半个小时了。

我确实收到了 combination changes size every loop iteration, consider predefining its size for speed 的警告，但这不会影响它吗？

Answer 1

正如@horchler 建议的那样，您需要预先分配目标数组

这是因为您的程序 O(N^4) 没有预分配。每次向数组添加新行时都需要调整大小，因此会创建更大的新数组（因为 matlab 不知道数组有多大，它可能只增加 1 项），然后将旧数组复制到其中，最后旧数组被删除。所以当你在数组中有 10 个项目并添加第 11 个时，然后将 10 个项目的副本添加到迭代中......如果我没记错的话会导致像 O(N^12) 这样的东西要大得多

估计为(N^4)*(1+2+3+...+N^4)=((N^4)^3)/2

此外，重新分配过程的大小也在增加，突破 CACHE 障碍随着每个 CACHE 大小障碍的增加 i 而减慢得更多。

没有预分配的唯一解决方案是将结果存储在链表中

不确定 Matlab 是否有此选项，但每个项目需要 one/two 个指针（32/64 位值），这会使您的数组 2+ 倍大。

如果你需要更快的速度，那么有一些方法（可能不适用于 Matlab）：

使用多线程进行数组填充是完全可并行化的
使用内存块复制（rep movsd）或 DMA 数据周期性重复
您还可以考虑从运行上的 i 计算值而不是记住整个数组，根据使用情况，在某些情况下它可能更快...

为什么我的嵌套 for 循环需要这么长时间来计算？

Why are my nested for loops taking so long to compute?

algorithm

matlab

time

big-o

nested-loops