Preallocazione di matrice cellulare in MATLAB

Question

Questa è più una domanda per comprendere un comportamento piuttosto che un problema specifico.

Mathworks afferma che i numeri sono memorizzati in modo continuo, il che rende importante la preallocazione. Questo non è il caso degli array di celle.

Sono qualcosa di simile al vettore o alla matrice di puntatori in C++?

Ciò significherebbe che la prealocazione non è così importante poiché un puntatore è la metà delle dimensioni di un doppio (a seconda di chi - ma c'è sicuramente un sovraccarico da qualche parte per memorizzare il tipo di dati del mxArray).

esecuzione di questo codice:

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) 

rendimenti: numerici senza preallocazione 0,429,24 mila s numerica con preallocazione 0,025,236 mila s cellulare senza preallocazione 4,960,297 mila s cellulare con preallocazione 0,554,257 mila s

Non c'è sorpresa per i valori numerici. Ma la cosa mi ha sorpreso dato che solo il contenitore dei puntatori e non i dati stessi avrebbero bisogno di riallocazione. Quale dovrebbe (poiché il puntatore è più piccolo di un doppio) conduce alla differenza di < .2s. Da dove viene questo overhead?

Una domanda correlata sarebbe, se desidero creare un contenitore di dati per dati eterogenei in Matlab (la preallocazione non è possibile poiché la dimensione finale non è nota all'inizio). Penso che le classi di handle non siano buone dato che anche le spese generali sono enormi.

già impaziente di imparare qualcosa

magu_

Edit: ho provato la lista collegata proposta da Eitan T, ma penso che l'overhead da MATLAB è ancora piuttosto grande. Ho provato qualcosa con un doppio array come dati (rand (200000,1)).

Ho fatto un piccolo pezzo di illustrare: codice

per il grafico: (I utilizzarlo classe dlnode dalla homepage MATLAB come indicato nel post segreteria)

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'}) 

Non fraintendetemi Mi piace l'idea di lista collegata, dato che ci sono piuttosto flessibili, ma penso che la testa potrebbe essere quello grande.

Answer 1

Gli array di celle sono qualcosa di simile a un vettore o una matrice di puntatori in C++?

array cellulare permettono la memorizzazione dei dati di diversi tipi e formati in effetti, ma ogni cella aggiunge anche un overhead costante di 112 byte (vedi this other answer of mine). Questo è molto più di un doppio di 8 byte, e questo non è trascurabile, specialmente quando si tratta di array di celle di grandi dimensioni come nel tuo esempio.

È ragionevole presumere che un array di celle sia implementato come un array continuo di puntatori, ciascuno dei quali punta al contenuto effettivo della cella.

Ciò significa che è possibile modificare il contenuto di ogni cella singolarmente senza ridimensionare effettivamente il contenitore dell'array cellulare stesso. Tuttavia, ciò significa anche che l'aggiunta di nuove celle all'array di celle richiede un'assegnazione dinamica dello storage ed è per questo motivo che la preallocazione della memoria per un array di celle migliora le prestazioni.

Una questione collegata sarebbe, se mi piacerebbe fare un contenitore di dati per i dati eterogenei in Matlab (preallocazione non è possibile in quanto la dimensione finale non è nota in principio)

Non sapendo la dimensione finale potrebbe effettivamente essere un problema, ma si potrebbe sempre preallocare un array di celle con la dimensione massima supportata necessaria (se ce n'è una) e rimuovere le celle vuote alla fine. Suggerisco anche di esaminare implementing linked lists in MATLAB.