为什么我的嵌套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个组合,并且An过度警告猜测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的障碍,随着i每个CACHE规模障碍的增加,减缓甚至更多.

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

不确定Matlab有这个选项,但是每个项目需要一个/两个指针(32/64位值),这会使你的数组2+时间变大.

如果你需要更快的速度,那么有方法(可能不适用于Matlab):

1. 使用多线程进行数组填充是完全可并行的
2. 使用内存块copy(rep movsd)或DMA,数据会定期重复
3. 您还可以考虑在运行时计算i中的值,而不是记住整个数组,具体取决于使用情况,在某些情况下可以更快...