Предопределение ячейки массива в matlab

Question

Это скорее вопрос понимания поведения, а не конкретной проблемы.

Mathworks утверждает, что числовые данные сохраняются непрерывными, что делает предварительное распределение важным. Это не относится к массивам ячеек.

Являются ли они чем-то похожими на вектор или массив указателей в C++?

Это означало бы, что преалокация не так важна, поскольку указатель имеет половину размера двойника (по словам 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 х Численный с предраспределения 0,025236 s Cell без предраспределения 4.960297 сек Cell с Предварительное выделение 0,554257 s

Там нет ничего удивительного для числовые значения. Но меня это удивило, так как только контейнер указателей, а не сами данные, нуждался бы в перераспределении. Который должен (поскольку указатель меньше двойника) приводит к разнице < .2s. Откуда взялись эти накладные расходы?

Связанный вопрос был бы, если бы я хотел бы создать контейнер данных для разнородных данных в Matlab (preallocation невозможен, так как конечный размер неизвестен в начале). Я думаю, что классы обработки не очень хорошие, так как у них также есть огромные накладные расходы.

уже с нетерпением жду, чтобы узнать что-то

magu_

Edit: Я опробовал связанный список, предложенный Эйтан T, но я думаю, что накладные расходы от MATLAB еще довольно большой. Я попробовал что-то с двойным массивом в качестве данных (rand (200000,1)).

Я сделал небольшой участок для иллюстрации:

код графа: (я использовал класс dlnode из Matlab Hompage, как указано в ответном посте)

D = RAND (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 байт (см this other answer of mine). Это намного больше, чем 8-байтовый двойной, и это не имеет значения, особенно при работе с массивами больших ячеек, как в вашем примере.

Разумно предположить, что массив ячеек реализован как непрерывный массив указателей, каждый из которых указывает на фактическое содержимое ячейки.

Это означает, что вы можете изменять содержимое каждой ячейки отдельно, не изменяя размер самого контейнера массива ячеек. Однако это также означает, что для добавления новых ячеек в массив ячеек требуется динамическое распределение хранилища, и поэтому предварительная выделение памяти для массива ячеек повышает производительность.

Родственный вопрос будет, если я хотел бы сделать контейнер данных для гетерогенных данных в Matlab (Предварительное выделение не представляется возможным, так как конечный размер не известен в начале)

Не зная, конечный размер действительно может быть проблемой, но вы всегда можете предварительно распределить массив ячеек с максимальным поддерживаемым размером, необходимым (если есть), и удалить пустые ячейки в конце. Я также предлагаю вам посмотреть на implementing linked lists in MATLAB.