在matlab中预分配单元格数组

Question

这更像是一个理解行为而不是特定问题的问题.

Mathworks声明数字是连续存储的,这使得预分配很重要.对于单元阵列不是这种情况.

它们与C++中的向量或指针数组类似吗？

这意味着预先定位不是那么重要,因为指针的大小是double的一半(根据whos - 但肯定会在某处存储mxArray数据类型的开销).

运行此代码:

clear all
n = 1e6;

tic
A = [];
for i=1:n
    A(end + 1) = 1;
end
fprintf('Numerical without preallocation %f s\n',toc)

clear A

tic
A = zeros(1,n);
for i=1:n
    A(i) = 1;
end
fprintf('Numerical with preallocation %f s\n',toc)

clear A
tic
A = cell(0);
for i=1:n
    A{end + 1} = 1;
end
fprintf('Cell without preallocation %f s\n',toc)

tic
A = cell(1,n);
for i=1:n
    A{i} = 1;
end
fprintf('Cell with preallocation %f s\n',toc)

返回:没有预分配的数值0.429240 s预分配的数值0.025236 s没有预分配的单元4.960297 s预分配的单元格0.554257 s

数值并不奇怪.但是确实让我感到惊讶,因为只有指针的容器而不是数据本身才需要重新分配.哪个应该(因为指针小于一个双倍)导致<.2s的差异.这个开销来自哪里？

一个相关的问题是,如果我想在Matlab中为异构数据创建一个数据容器(预分配是不可能的,因为最终的大小在开始时是未知的).我认为句柄类不好,因为它也有很大的开销.

已经期待着学到一些东西

magu_

编辑: 我尝试了Eitan T提出的链表,但我认为matlab的开销还很大.我尝试用双数组作为数据(rand(200000,1)).

我做了一个小小的情节来说明:

图表的代码:(我使用了matlab hompage中的dlnode类,如回答帖子中所述)

D =兰特(200000,1);

s = linspace(10,20000,50);
nC = zeros(50,1);
nL = zeros(50,1);

for i = 1:50
a = cell(0);

tic
for ii = 1:s(i)
    a{end + 1} = D;
end
nC(i) = toc;

a = list([]);

tic
for ii = 1:s(i)
    a.insertAfter(list(D));
end
nL(i) = toc;

end

figure
plot(s,nC,'r',s,nL,'g')
xlabel('#iter')
ylabel('time (s)')
legend({'cell' 'list'})

不要误会我的意思我喜欢链表的想法,因为它有相当的灵活性,但我认为开销可能很大.

Answer 1

单元格数组是否类似于C++中的向量或指针数组？

单元阵列确实可以存储不同类型和大小的数据,但每个单元也会增加112字节的常量开销(参见我的另一个答案).这远远超过8字节的双倍,这是不可忽视的,尤其是在处理大型单元阵列时,如您的示例所示.

可以合理地假设单元阵列被实现为连续的指针数组,每个指针指向单元的实际内容.

这意味着您可以单独修改每个单元格的内容,而无需实际调整单元格数组容器本身的大小.但是,这也意味着向单元阵列添加新单元需要动态存储分配,这就是为单元阵列预分配内存可以提高性能的原因.

一个相关的问题是,如果我想在Matlab中为异构数据创建一个数据容器(预分配是不可能的,因为最终的大小在开始时是未知的)

不知道最终大小可能确实是一个问题,但您总是可以预先分配一个具有所需最大支持大小的单元阵列(如果有的话),并在最后删除空单元格.我还建议你研究在MATLAB中实现链表.