Prealokacja macierzy komórek w programie matlab

Question

To jest raczej pytanie, aby zrozumieć zachowanie, a nie konkretny problem.

Mathworks stwierdza, że ​​wartości numeryczne są przechowywane w sposób ciągły, co sprawia, że ​​wstępna alokacja jest ważna. Nie dotyczy to tablic komórkowych.

Czy są one podobne do wektora lub tablicy wskaźników w C++?

Oznaczałoby to, że prealokacja nie jest tak ważna, ponieważ wskaźnik jest o połowę mniejszy od podwójnego (w zależności od tego, kto z pewnością jest gdzieś na górze, aby przechowywać typ danych mxArray).

Running ten kod:

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) 

powraca: numeryczne bez preallocation 0,429240 s numeryczna z preallocation 0,025236 s komórkowych bez preallocation 4.960297 s komórki z preallocation 0,554257 s

Nie jest niespodzianką dla wartości liczbowe. Ale zaskoczyło mnie to, ponieważ tylko pojemnik wskaźników, a nie same dane, wymagałyby realokacji. Które powinny (ponieważ wskaźnik jest mniejszy niż podwójne) prowadzić do różnicy < .2s. Skąd bierze się ten narzut?

Podobne pytanie byłoby, jeśli chciałbym utworzyć kontener danych dla heterogenicznych danych w Matlab (wstępna alokacja nie jest możliwa, ponieważ ostateczny rozmiar nie jest znany na początku). Myślę, że klasy obsługi nie są dobre, ponieważ mają również ogromny narzut.

już doczekać się czegoś

magu_

Edit: Próbowałem się z połączonej listy zaproponowanej przez Eitan T, ale myślę, narzut z Matlab jest nadal dość duże. Próbowałem coś z podwójną tablicą jako danymi (rand (200000,1)).

że wykonany mały wykres zilustrować: kod

na wykresie: (I stosowane klasy dlnode z glównej Matlab jak podano na stanowisku odbierania)

D = LOS (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'}) 

Nie zrozum mnie źle Kocham ideę połączonej listy, ponieważ nie są dość elastyczne, ale myślę, że nad głową może być zbyt duża.

Answer 1

Czy tablice komórek są podobne do wektora lub tablicy wskaźników w C++?

Komórki macierzy umożliwiają przechowywanie danych o różnych typach i rozmiarach, ale każda komórka dodaje również stały narzut 112 bajtów (patrz this other answer of mine). Jest to znacznie więcej niż 8-bajtowe podwójne, a to nie jest bez znaczenia, zwłaszcza gdy mamy do czynienia z dużymi tablicami komórek, jak w twoim przykładzie.

Rozsądnie jest założyć, że tablica komórek jest zaimplementowana jako ciągła tablica wskaźników, z których każda wskazuje na rzeczywistą zawartość komórki.

Oznacza to, że można modyfikować zawartość każdej komórki indywidualnie, bez faktycznego zmieniania rozmiaru samego kontenera macierzy komórek. Oznacza to jednak również, że dodawanie nowych komórek do macierzy komórek wymaga dynamicznego przydzielania pamięci i dlatego wcześniejsze przydzielanie pamięci dla macierzy komórkowej poprawia wydajność.

Powiązane pytanie byłoby, jeśli chciałbym, aby kontener danych dla danych heterogenicznych w Matlab (preallocation nie jest możliwe, ponieważ ostateczna wielkość nie jest znana na początku)

Nie wiedząc, ostateczny rozmiar może rzeczywiście stanowić problem, ale zawsze można wstępnie przydzielić macierz komórek o maksymalnym obsługiwanym rozmiarze (jeśli taki istnieje) i usunąć puste komórki na końcu. Sugeruję również, abyś spojrzał na implementing linked lists in MATLAB.