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

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

我有一个代码可以生成 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 的警告,但这不会影响它吗?

正如@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):

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