Temat: [C++] Tworzenie tablicy dwuwymiarowej (komentarz)
----------------------------------------------
Post dotyczy tego posta w
CUO.
W po?cie jest napisane, ?e przy korzystaniu z metody z
alokacj? ci?g?ego obszaru
pami?ci trudniej jest tworzy? tablice dwuwymiarowe o nietypowych
kszta?
tach. Wbrew pozorom w wi?
kszo?ci przypadków tak nie jest. Je?
eli mamy kod
alokuj?cy wiersze ró?
nej d?
ugo?ci metod? alokacji ka?
dego wiersza oddzielnie, to bez problemu zwykle mo?na to prze?o?y?
bezpo?
rednio na
wersj? z
pojedyncz?
alokacj?. Schemat jest prosty. Rozmiar wymaganego obszaru ci?g?ego jest równy sumie d?
ugo?ci wszystkich wierszy. Oprócz tego musimy wiedzie?, gdzie zaczyna si? ka?dy z wierszy w
zaalokowanym obszarze. Nietrudno si? domy?li?, ?e
przesuni?cie jest sum? d?
ugo?ci wszystkich poprzednich wierszy.
Dla osób lubi?
cych wzorki:
Przy za?o?
eniu, ?e jest n oraz s(i) oznacza rozmiar i-tego wiersza:
Rozmiar
alokowanego obszaru
[tex:bc00a4de92]
size=\sum_{i=1}^n{s(i)}[/tex:bc00a4de92]
Przesuni?cie dla k-tego wiersza
[tex:bc00a4de92]offset(k)=\sum_{i=1}^k{s(i)}[/tex:bc00a4de92]
Przek?
adaj?c te wzorki
bezpo?
rednio na kod:
Oczywi?cie jest to niewydajne (linia 8: ci?g?e przeliczanie tego samego) i mo?na to
zapisa? przynajmniej tak: W wi?
kszo?ci przypadków mo?na (nawet wypada)
napisa? to
optymalniej,
zast?
puj?c wyra?
enie s[n] lub sum? s[n] innymi,
prostszymi wyra?
eniami. Np. dla tablicy
prostok?
tnej suma s[n] to po prostu iloczyn d?
ugo?ci wiersza i indeksu aktualnego wiersza: Dla tablicy
trójk?
tnej s[i] mo?na
zast?pi? po prostu i. D?
ugo?ci wierszy tworz? ci?g arytmetyczny, wi?c nietrudno równie?
zauwa?y?, jak policzy? sum? d?
ugo?ci wierszy. Itd.
Dodaj do słownika