Mój głos w sprawie








Mój głos w sprawie...
tablic


Jeśli używaliście w swoich programach
tablic, jedno lub wielowymiarowych, zapewne wiecie jak wygląda deklaracja takiej
struktury danych. Ja jednak nie chcę poruszać tematu deklaracji, a alokację takiej
tablicy w pamięci. W standardowych programach nie jest to przydatne, jednak może okazać
się skuteczne w dużych aplikacjach, gdzie stosuje się optymalizację kodu.

Jako przykładem będę posługiwał się
tablicą zadeklarowaną następująco:

Dim
Tablica(1, 2) As Byte

Jest to tablica dwuwymiarowa, o pierwszym
wymiarze wielkości 2 (indeks 0 i 1) oraz drugim wymiarze wielkości 3. Tutaj pojawia się
pytanie: który z tych wymiarów jest liczbą wierszy, a który liczbą kolumn? Dla
małych tablic jak już wspominałem nie ma to istotnego znaczenia i zależy od
domyślnego przyjęcia przez programistę. Przeszukanie takiej tablicy (sprawdzenie
wartości wszystkich jej elementów) zajmuje znikomą ilość czasu. Jeśli jednak nasza
tablica miałaby rozmiar sięgający np. 20 MB, przeszukiwanie może trwać sporą ilość
czasu.

Weźmy taki kod i załóżmy, że pierwszy
wymiar to kolumny (oś x), a drugi to wiersze (oś y). Tablicę wypełniamy wiersz po
wierszu:

Tablica(0,
0) = 0
Tablica(1, 0) = 1
Tablica(0, 1) = 2
Tablica(1, 1) = 3
Tablica(0, 2) = 4
Tablica(1, 2) = 5

W pamięci nasza tablica zostanie
ulokowana w następujący sposób:

kolumna 0 kolumna 1




0
2
4
 
1
3
5




Dlaczego tak? Otóż wszystkie kompilatory
deklarację:

Dim Tablica(1, 2) As
Byte
odczytują jako
Dim Tablica(1) As (2) As Byte

Oczywiście nie próbujcie wpisywać tak w
VB, spowoduje to z pewnością błąd. Chodzi mi tylko o zobrazowanie tego przykładu.
Kompilator odczyta naszą deklarację jako tablica dwuelementowa(!) tablic
trzyelementowych. Zakręciłem? Podobną strukturę będzie miała deklaracja (podobną co
wcale nie znaczy identyczną):

Type TTab
PodTablica(2) As Byte
End Type
Dim Tablica(1) As TTab

Różnica polega tutaj na tym, że nie
można się bezpośrednio odwołać do żądanego wiersza i kolumny (w odwołaniu
występuje jeszcze dodatkowo nazwa pola PodTablica). Jednak przydział pamięci jest
identyczny jak dla naszej przykładowej tablicy. Przejdźmy teraz do sedna sprawy. System
wczytując pierwszy element tablicy (0,0) ładuje do pamięci podręcznej cache także
kolejne komórki pamięci. Przy deklaracji:

Dim
Tablica2(10000, 20000) as Byte ętaka lub większa

i przyjęciu wymiarów: (kolumny,
wiersze), podczas przeszukiwania tej tablicy wiersz po wierszu, przy wczytaniu każdego
kolejnego elementu zostaje także ponownie przeładowana pamięć cache (patrz przykład
powyżej z alokacją naszej małej tablicy). Gdybyśmy przeszukiwali ją kolumna po
kolumnie, w pamięci podręcznej znajdowałyby się kolejne wczytywane przez nas wartości
(co pozwala na skrócenie czasu przeszukiwania, ponieważ procesor nie wczytuje już z
RAMłu kolejnych bajtów, ale wykorzystuje te przechowywane w cachełu).

Dlatego przy deklaracji większych tablic
należy zwrócić uwagę na to, że w deklaracji wymiarów pierwsze występuje liczba
wierszy, a następnie liczba kolumn. Jeśli nie ma to dla nas znaczenia, należy
pamiętać jedynie o kolejności przeszukiwania tablicy. Dla tablicy Tablica2 możemy
zapisać pętlę:

For i = 0
To 10000 ędla każdego indeksu pierwszego wymiaru
For j = 0 to 20000 ęprzeszukaj wszystkie indeksy drugiego wymiaru
ętutaj sprawdzamy wartość elementu
ęTablica2(i, j)
Next
Next

I to by było na tyle.

Piotrek Mazur vel. Garfield
[e-mail]