通过空matrix乘法初始化数组更快的方法？ （Matlab的）
我偶然发现了奇怪的方式（在我看来）Matlab正在处理空matrix 。 例如，如果两个空matrix相乘，结果是：
zeros(3,0)*zeros(0,3) ans = 0 0 0 0 0 0 0 0 0 现在，这已经让我吃惊了，但是，一个快速的search让我看到了上面的链接，并且解释了为什么会发生这种有些扭曲的逻辑。
但是 ，没有任何东西准备好我的观察。 我问自己，这种types的乘法与仅使用zeros(n)函数有多高效，比如初始化的目的呢？ 我用timeit来回答这个问题：
f=@() zeros(1000) timeit(f) ans = 0.0033
VS：
g=@() zeros(1000,0)*zeros(0,1000) timeit(g) ans = 9.2048e-06
两者的结果都是1000×1000的二级零matrix，但是空matrix乘法一个是〜350倍！ （类似的结果发生使用tic和toc和一个循环）
这怎么可能？ 是timeit或tic,toc虚张声势还是我find了一个更快的方法来初始化matrix？ （这是用matlab 2012a完成的，在win7-64机器上，intel-i5 650 3.2Ghz …）
编辑：
在阅读您的反馈之后，我更仔细地研究了这个特性，并在两台不同的计算机（相同的matlab ver 2012a）上testing了一个代码，用于检查运行时间与matrixn的大小。 这是我得到的：
与以前一样生成这个使用的timeit的代码，但是一个循环与tic和toc看起来是一样的。 所以，对于小尺寸， zeros(n)是可比较的。 然而，在n=400左右，空matrix乘法的性能有所提高。 我用来生成该图的代码是：
n=unique(round(logspace(0,4,200))); for k=1:length(n) f=@() zeros(n(k)); t1(k)=timeit(f); g=@() zeros(n(k),0)*zeros(0,n(k)); t2(k)=timeit(g); end loglog(n,t1,'b',n,t2,'r'); legend('zeros(n)','zeros(n,0)*zeros(0,n)',2); xlabel('matrix size (n)'); ylabel('time [sec]');
你们有没有经历过这个？
编辑＃2：
顺便说一句，空matrix乘法不需要得到这个效果。 人们可以简单地做：
z(n,n)=0;
其中n>在前面的图中看到一些阈值matrix大小，并且与空matrix乘法（再次使用timeit）一样得到确切的效率分布。
下面是一个提高代码效率的例子：
n = 1e4; clear z1 tic z1 = zeros( n ); for cc = 1 : n z1(:,cc)=cc; end toc % Elapsed time is 0.445780 seconds. %% clear z0 tic z0 = zeros(n,0)*zeros(0,n); for cc = 1 : n z0(:,cc)=cc; end toc % Elapsed time is 0.297953 seconds.
但是，使用z(n,n)=0; 而是产生与zeros(n)情况类似的结果。
这很奇怪，我看到f比g更慢，g比你看到的要慢。 但是他们两个对我来说都是一样的。 也许是不同版本的MATLAB？
>> g = @() zeros(1000, 0) * zeros(0, 1000); >> f = @() zeros(1000) f = @()zeros(1000) >> timeit(f) ans = 8.5019e-04 >> timeit(f) ans = 8.4627e-04 >> timeit(g) ans = 8.4627e-04
编辑可以为f和g的结尾添加+ 1，看看你得到的是什么时间。
编辑2013年1月6日7:42美国东部时间
我正在远程使用一台机器，所以很抱歉低质量的graphics（不得不盲目生成）。
机器configuration：
i7 920. 2.653 GHz。 Linux操作系统。 12 GB RAM。 8MBcaching。
它看起来即使我有权访问的机器显示这种行为，除了在一个较大的大小（1979年至2073年之间）。 我现在没有理由想到空matrix乘法在更大的尺寸上更快。
在回来之前我会再调查一下。
编辑2013年1月11日
在@ EitanT的post后，我想做更多的挖掘。 我写了一些C代码来看看matlab如何创build一个零matrix。 这是我使用的C ++代码。
int main(int argc, char **argv) { for (int i = 1975; i <= 2100; i+=25) { timer::start(); double *foo = (double *)malloc(i * i * sizeof(double)); for (int k = 0; k < i * i; k++) foo[k] = 0; double mftime = timer::stop(); free(foo); timer::start(); double *bar = (double *)malloc(i * i * sizeof(double)); memset(bar, 0, i * i * sizeof(double)); double mmtime = timer::stop(); free(bar); timer::start(); double *baz = (double *)calloc(i * i, sizeof(double)); double catime = timer::stop(); free(baz); printf("%d, %lf, %lf, %lf\n", i, mftime, mmtime, catime); } }
这是结果。
$ ./test 1975, 0.013812, 0.013578, 0.003321 2000, 0.014144, 0.013879, 0.003408 2025, 0.014396, 0.014219, 0.003490 2050, 0.014732, 0.013784, 0.000043 2075, 0.015022, 0.014122, 0.000045 2100, 0.014606, 0.014480, 0.000045
正如你所看到的calloc （第四列）似乎是最快的方法。 在2025年和2050年之间，这个数字也会大大加快（我假设它将在2048年左右？）。
现在我回到MATLAB来检查相同的。 这是结果。
>> test 1975, 0.003296, 0.003297 2000, 0.003377, 0.003385 2025, 0.003465, 0.003464 2050, 0.015987, 0.000019 2075, 0.016373, 0.000019 2100, 0.016762, 0.000020
它看起来像f（）和g（）使用calloc在较小的尺寸（<2048？）。 但是在较大的尺寸下，f（）（零（m，n））开始使用malloc + memset ，而g（）（零，（m，0）*零（0，n））继续使用calloc 。
所以分歧解释如下
- 零（..）开始在较大的尺寸上使用不同的（较慢的？）scheme。
-
callocperformance也有些出乎意料，导致了性能的提高。
这是Linux上的行为。 有人可以在不同的机器（也可能是不同的操作系统）上做同样的实验，看看实验是否成立？
结果可能有点误导。 当你乘两个空matrix时，matrix不会立即“分配”和“初始化”，而是推迟到你第一次使用它（有点像懒惰评估）。
索引越界扩大一个variables，这在数值数组的情况下用零填充任何缺失的条目（我后面讨论非数字情况）。 当然，以这种方式增长matrix不会覆盖现有的元素。
所以，虽然看起来更快，但你只是延迟分配时间，直到你真的第一次使用matrix。 最后你会有类似的时机，就好像你从一开始就进行了分配。
显示此行为的示例与其他一些替代方法相比较：
N = 1000; clear z tic, z = zeros(N,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = zeros(N,0)*zeros(0,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(N,N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = full(spalloc(N,N,0)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(1:N,1:N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z val = 0; tic, z = val(ones(N)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = repmat(0, [NN]); toc tic, z = z + 1; toc assert(isequal(z,ones(N)))
结果显示，如果在每种情况下总结两条指令的运行时间，则最终的总计时间类似：
// zeros(N,N) Elapsed time is 0.004525 seconds. Elapsed time is 0.000792 seconds. // zeros(N,0)*zeros(0,N) Elapsed time is 0.000052 seconds. Elapsed time is 0.004365 seconds. // z(N,N) = 0 Elapsed time is 0.000053 seconds. Elapsed time is 0.004119 seconds.
其他时间是：
// full(spalloc(N,N,0)) Elapsed time is 0.001463 seconds. Elapsed time is 0.003751 seconds. // z(1:N,1:N) = 0 Elapsed time is 0.006820 seconds. Elapsed time is 0.000647 seconds. // val(ones(N)) Elapsed time is 0.034880 seconds. Elapsed time is 0.000911 seconds. // repmat(0, [NN]) Elapsed time is 0.001320 seconds. Elapsed time is 0.003749 seconds.
这些测量在毫秒内太小，可能不是很准确，所以你可能想在几千次的循环中运行这些命令并取平均值。 有时运行保存的M函数比运行脚本或命令提示符更快，因为某些优化只能以这种方式发生…
无论哪种方式分配通常是做一次，所以谁在乎，如果需要额外的30ms 🙂
单元arrays或结构数组可以看到类似的行为。 考虑下面的例子：
N = 1000; tic, a = cell(N,N); toc tic, b = repmat({[]}, [N,N]); toc tic, c{N,N} = []; toc
这使：
Elapsed time is 0.001245 seconds. Elapsed time is 0.040698 seconds. Elapsed time is 0.004846 seconds.
请注意，即使它们全部相等，它们也占用不同的内存量：
>> assert(isequal(a,b,c)) >> whos abc Name Size Bytes Class Attributes a 1000x1000 8000000 cell b 1000x1000 112000000 cell c 1000x1000 8000104 cell
实际上这里的情况有点复杂，因为MATLAB可能为所有单元共享相同的空matrix，而不是创build多个副本。
单元arraysa实际上是一个未初始化的单元arrays（一个NULL指针数组），而b是一个单元arrays，其中每个单元都是一个空数组[] （在内部，由于数据共享，只有第一个单元b{1}指向[]而其余的都有第一个单元格的引用）。 最后一个数组c类似于a （未初始化的单元格），但是最后一个数组包含一个空的数字matrix[] 。
我从libmx.dll （使用Dependency Walker工具）中查看导出的C函数列表，并且发现了一些有趣的事情。
-
有用于创build未初始化的数组的未
mxCreateUninitDoubleMatrix函数：mxCreateUninitDoubleMatrix，mxCreateUninitNumericArray和mxCreateUninitNumericMatrix。 事实上，在文件交换中有一个提交使用这些函数来提供一个更快的替代zerosfunction。 -
有一个名为
mxFastZeros的未mxFastZeros函数。 在网上search，我可以看到你在MATLAB的答案，以及在那里一些优秀的答案交叉张贴这个问题。 詹姆斯·图尔萨（同前的UNINIT作者）给出了一个如何使用这个无证函数的例子 。 -
libmx.dll链接到tbbmalloc.dll共享库。 这是Intel TBB可扩展内存分配器。 该库为并行应用程序提供了等效的内存分配函数（malloc，calloc，free）。 请记住，很多MATLAB函数都是自动multithreading的 ，所以如果zeros(..)线程zeros(..)是multithreading的，并且在matrix大小足够大的情况下使用了英特尔的内存分配器（这是Loren Shure最近的评论证实了这一点） 。
关于内存分配器的最后一点，你可以用C / C ++编写类似于@PavanYalamanchili所做的类似的基准testing，并比较各种可用的分配器。 像这样的东西。 请记住，MEX文件的内存pipe理开销略高，因为MATLAB使用mxCalloc ， mxMalloc或mxRealloc函数自动释放在MEX文件中分配的任何内存。 对于它的价值，它曾经有可能改变旧版本的内部内存pipe理器 。
编辑：
这是比较所讨论的替代scheme更彻底的基准。 它具体说明，一旦你强调整个分配matrix的使用，三种方法都是平等的，差别是可以忽略的。
function compare_zeros_init() iter = 100; for N = 512.*(1:8) % ZEROS(N,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, ZEROS = %.9f\n', N, mean(sum(t,2))) % z(N,N)=0 t = zeros(iter,3); for i=1:iter clear z tic, z(N,N) = 0; t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, GROW = %.9f\n', N, mean(sum(t,2))) % ZEROS(N,0)*ZEROS(0,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,0)*zeros(0,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, MULT = %.9f\n\n', N, mean(sum(t,2))) end end
下面是按照matrix大小递增的100次迭代的平均时间。 我在R2013a进行了testing。
>> compare_zeros_init N = 512, ZEROS = 0.001560168 N = 512, GROW = 0.001479991 N = 512, MULT = 0.001457031 N = 1024, ZEROS = 0.005744873 N = 1024, GROW = 0.005352638 N = 1024, MULT = 0.005359236 N = 1536, ZEROS = 0.011950846 N = 1536, GROW = 0.009051589 N = 1536, MULT = 0.008418878 N = 2048, ZEROS = 0.012154002 N = 2048, GROW = 0.010996315 N = 2048, MULT = 0.011002169 N = 2560, ZEROS = 0.017940950 N = 2560, GROW = 0.017641046 N = 2560, MULT = 0.017640323 N = 3072, ZEROS = 0.025657999 N = 3072, GROW = 0.025836506 N = 3072, MULT = 0.051533432 N = 3584, ZEROS = 0.074739924 N = 3584, GROW = 0.070486857 N = 3584, MULT = 0.072822335 N = 4096, ZEROS = 0.098791732 N = 4096, GROW = 0.095849788 N = 4096, MULT = 0.102148452
在做了一些研究之后，我在“未logging的Matlab”中find了这篇文章 ，其中Yair Altman先生已经得出结论： MathWork的使用zeros(M, N) 预分配matrix的方法确实不是最有效的方式。
他定时x = zeros(M,N)与clear x, x(M,N) = 0 ，发现后者快500倍。 根据他的解释，第二种方法简单地创build一个M×N的matrix，其元素被自动初始化为0.然而，第一种方法创buildx （ x具有自动零元素），然后为每个元素指定一个零元素再次，这是一个冗余的操作，需要更多的时间。
在空matrix乘法的情况下，例如您在问题中所展示的内容，MATLAB预期产品是M×Nmatrix，因此它将分配一个M×Nmatrix。 因此，输出matrix自动初始化为零。 由于原始matrix是空的，因此不执行进一步的计算，因此输出matrix中的元素保持不变并且等于零。
有趣的问题，显然有几种方法来“击败”内置的zerosfunction。 我唯一的猜测就是为什么会发生这种情况，因为它可能会更有效率的内存（毕竟， zeros(LargeNumer)会使Matlab更快地达到内存限制，而不是在大多数代码中形成一个严重的速度瓶颈），或者更强大。
这里是另一种使用稀疏matrix的快速分配方法，我已经添加了常规的零点函数作为基准：
tic; x=zeros(1000,1000); toc Elapsed time is 0.002863 seconds. tic; clear x; x(1000,1000)=0; toc Elapsed time is 0.000282 seconds. tic; x=full(spalloc(1000,1000,0)); toc Elapsed time is 0.000273 seconds. tic; x=spalloc(1000,1000,1000000); toc %Is this the same for practical purposes? Elapsed time is 0.000281 seconds.
看来matlab决定使用稀疏matrix，当它收到一个命令如z(n,n)=0; 当n足够大时。 内部实现可能是这样一个条件的forms：（如果newsize> THRESHOLD + oldsize则使用稀疏…），其中THRESHOLD是你的“阈值大小”。
然而，尽pipeMathworks声称：“Matlab从不会自动创build稀疏matrix”（ 链接 ）
我没有Matlab来testing这个。 不过，使用稀疏matrix（内部）是一个较短的解释（奥卡姆剃刀），因此是更好的，直到伪造。
