Indeksowanie tabel

W językach C oraz Fortran tabela jest spójnym obszarem pamięci przechowującym "szereg" elementów o jednakowym typie (i rozmiarze).

Aby uzyskać dostęp do elementu w tablicy (odczyt / zapis wartości) w językach C oraz Fortran stosowane są różne strategie.

Tablice alokowane statycznie (na stosie)

Jeżeli w kodzie programu jest zdefiniowana tablica (jedno lub wielowymiarowa), wówczas podczas uruchamiania programu tablica ta jest alokowana na stosie.

Uzyskanie dostępu do elementów tablicy jest możliwe dzięki indeksom. Tablica jednowymiarowa ma jeden indeks, natomiast tablica wielowymiarowa ma kilka indeksów (w zależności od wymiaru tablicy).

Tablice jednowymiarowe

W języku C tablica jednowymiarowa jest zawsze indeksowana od zera do wartości (rozmiar_tablicy - 1). Poniżej zamieściłem przykładowy program w języku ANSI C, gdzie podczas wywoływania programu głównego (funkcja main) na stosie jest alokowana tablica statyczna o zadanym rozmiarze (TAB_SIZE). Następnie tablica ta jest wypełniana w pętli for. Dostęp do elementów tablicy możliwy jest dzięki indeksowi i. Dla pierwszego elementu tablicy indeks ten ma wartość 0, dla drugiego elementu wartość 1 itd. Druga pętla wypisuje na ekranie zawartość wypełnionej tablicy.

/* bilioteka do komunikacji z uzytkownikiem */
#include "stdio.h"

/* rozmiar tablicy zdefiniowany "na sztywno" (makro preprocesora) */
#define TAB_SIZE 10

/* program glowny */
int main(void)
{
    /*w języku ANSI C najpierw są definicje zmiennych a potem instrukcje */

    /* definicja naszej tablicy przechowującej liczby całkowite o rozmiarze TAB_SIZE */
    int tab[TAB_SIZE];

    /* definicja indeksu wykorzystywanego przy operacjach na tablicy */
    unsigned int i = 0;

 
    /* teraz będą instrukcje */

    printf("Program testujący wypełnianie tablicy i wypisujący jej zawartosc.\n");
   
    /* wypełnienie tablicy wartościami 0 .. (TAB_SIZE -1) */

    printf("Wypełnianie tablicy...");

    /* trawersowanie tablicy */
    for(i = 0; i < TAB_SIZE; i++)
    {
       /* Wypełnienie tablicy wartościami równymi wartościom indeksu */
      tab[i] = i;
    }
    /* teraz już tablica została wypełniona*/
   printf("ok\n");

    /* wypisanie zawartości tablicy */

    printf("Wyswietlanie zawartosci tablicy...\n");

    /* trawersowanie tablicy */
    for(i = 0; i < TAB_SIZE; i++)
    {
        /* wypisanie wartości przechowywanej w tablicy */
        printf("tab[%u] == %d\n", i, tab[i]);
    }
    /* teraz już tablica została wyświetlona */
   
    printf("Wyswietlanie zakonczono.\n");

    printf("Koniec programu.\n");

    return 0;
}/* main */

Wynik działania programu:

Program testujący wypełnianie tablicy i wypisujący jej zawartosc.
Wypełnianie tablicy...ok
Wyswietlanie zawartosci tablicy...
tab[0] == 0
tab[1] == 1
tab[2] == 2
tab[3] == 3
tab[4] == 4
tab[5] == 5
tab[6] == 6
tab[7] == 7
tab[8] == 8
tab[9] == 9
Wyswietlanie zakonczono.
Koniec programu.

W języku Fortran tablica jednowymiarowa jest indeksowana domyślnie od jednego. Może być też indeksowana od dowolnej liczby całkowitej (nawet ujemnej). Oczywiście w sensownym zakresie wartości. Na angielskojęzycznej wersji Wikibooks (Fortran 77 Tutorial) są dostępne przykłady takiego indeksowania.

Poniżej napisałem "mini -przykład" (skompilował się na gfortran, więc może jako tako). Tablica WEIRD jest indeksowana od -4 do +5. Dostęp do elementów tablicy jest realizowany przy pomocy indeksu I. Tablica jest wypełniana w pętli DO. Kolejna pętla DO wyświetla zawartość tablicy. Wyświetlanie mieszaniny tekstu i sformatowanych liczb jest realizowane przy pomocy formatu pod etykietą 900.

      PROGRAM P1

      IMPLICIT NONE

      REAL    WEIRD(-4:5)
      INTEGER I
      INTEGER N1
      INTEGER N2

      N1 = -4
      N2 = +5
    
      WRITE(*,*) 'WYPELNIANIE TABLICY WEIRD WARTOSCIAMI I * 10.0 ...'

      DO 100 I = N1, N2
         WEIRD(I) = I * 10.0
100   CONTINUE

      WRITE(*,*) 'OK'


      WRITE(*,*) 'WYPISYWANIE TABLICY WEIRD...'

      DO 200 I = N1, N2
         WRITE(*,900) I, WEIRD(I)
200   CONTINUE

      WRITE(*,*) 'ZAKONCZONO'

      WRITE(*,*) 'KONIEC PROGRAMU'


900   FORMAT('WEIRD(', I2, ')  = ', F6.2)

      ENDPROGRAM P1

Wynik działania programu:

 WYPELNIANIE TABLICY WEIRD WARTOSCIAMI I * 10.0 ...
 OK
 WYPISYWANIE TABLICY WEIRD...
WEIRD(-4)  = -40.00
WEIRD(-3)  = -30.00
WEIRD(-2)  = -20.00
WEIRD(-1)  = -10.00
WEIRD( 0)  =   0.00
WEIRD( 1)  =  10.00
WEIRD( 2)  =  20.00
WEIRD( 3)  =  30.00
WEIRD( 4)  =  40.00
WEIRD( 5)  =  50.00
 ZAKONCZONO
 KONIEC PROGRAMU

Tablice wielowymiarowe

Tablice wielowymiarowe wykorzystują kilka indeksów. Pomiędzy językiem C a Fortranem istnieje różnica.

Jak już napisałem, w programie tablica jest przedstawiona jako struktura, gdzie położenie komórki może zostać wyznaczone przez podanie jej indeksów. Dla tablicy 2 wymiarowej będą to indeksy rzędu i kolumny. W przypadku tablicy 3 wymiarowej będą to indeksy rzędu, kolumny i warstwy.

W zasadzie sposób indeksowania tablicy mógłby być kwestią "formalną" (zależną od jakiejś specyfikacji, standardu). Jest tylko jeden aspekt związany z wydajnością programu. We współczesnych komputerach jednym z podstawowych problemów natury technicznej jest szybkość przekazywania danych pomiędzy rozmaitymi podzespołami. Np. pomiędzy procesorem CPU a pamięcią RAM. To dlatego obecnie procesory posiadają rozmaite pamięci podręczne (np. cache L1, L2, L3). Jeżeli procesor będzie mógł efektywnie wykorzystywać te pamięci, wówczas wydajność aplikacji wzrośnie.

Skupię się na przypadku tablicy przechowującej proste typy danych (np. liczby o podwójnej precyzji). Jeżeli mamy taką tablicę i chcemy wykonywać na niej stosunkowo szybkie operacje, to czas dostępu do pojedynczych elementów może być sprawą ważną. Np. chcemy wyznaczyć średnią arytmetyczną liczb rzeczywistych przechowywanych w tablicy. Operacja dodawania jest wykonywana bardzo szybko, natomiast sięganie do pamięci RAM może zająć ponad 100 taktów procesora (obecnie pewnie jest jeszcze inaczej). Z tego powodu współczesne komputery posiadają funkcjonalność "prefetch" - ładowanie z wyprzedzeniem. Jeżeli kompilator "widzi", że program chce przetwarzać komórki tabeli leżące w pamięci tuż obok siebie, to może efektywniej ładować te dane do pamięci cache procesora (zawczasu). Pozwala to osiągnąć maksymalną wydajność. Generalnie są to sprawy związane z wewnętrznymi układami sterującymi procesorem. Procesorowi łatwiej jest optymalnie wypełnić pamięci cache, jeżeli ma kilka tablic danych "prostych", niż np. jedną tablicę danych złożonych (np. rekord, struktura, obiekt). Zmiana sposobu organizacji pamięci może istotnie wpłynąć na wydajność aplikacji.

W języku C tablice są indeksowane "wierszowo". W każdym wierszu tabeli komórki sąsiadują ze sobą (pod katem posiadanego adresu w pamięci). Jeżeli chcemy szybko przetworzyć tablicę dwuwymiarową, to najefektywniejsze powinno być pobieranie danych wierszami. Generalnie chodzi o "ostatni z indeksów komórki".

Czyli trawersowanie takiej tablicy w C powinno przebiegać następująco. Pętla zewnętrzna przetwarza rzędy. Pętla wewnętrzna przetwarza dany rząd. W przypadku tablicy 3 wymiarowej na samym początku byłaby jeszcze pętla przetwarzająca warstwy.

W języku Fortran tablice są indeksowanie w sposób odmienny. To właśnie "pierwszy z indeksów komórki" (wiersz) wskazuje na grupę komórek sąsiadujących ze sobą ("adresowo"). Zatem "wydajne" trawersowanie tablicy w Fortranie powinno przebiegać następująco. Pętla zewnętrzna wskazuje na kolejne kolumny. Pętla wewnętrzna przetwarza daną kolumnę (iteracja po wierszach przy ustalonej kolumnie). W przypadku tablicy 3-wymiarowej na samym końcu byłby jeszcze indeks wskazujący na warstwę.

Zagadnienie indeksowania jest także ważne w przypadku łączenia ze sobą kodu w różnych językach programowania (np. Fortran i C). W praktyce konieczne jest uwzględnienie kolejności indeksów.

Przykład wzorowany na dokumentacji programu VisItusers.org (C vs Fortran memory order). Demonstruje analogie pomiędzy reprezentacją tablicy statycznej w Fortranie i C. Mamy tablicę 3D o wymiarach NX, NY,NZ. Można utożsamić NX z indeksem kolumny, NY - z adresem wiersza i NZ - z numerem warstwy. Tablica jest zdefiniowana jako VALUES(NX,NY,NZ). Pierwszy indeks (NX) jest przetwarzany w pętli "wewnętrznej". Drugi (NY) w pętli "środkowej", a trzeci (NZ) w pętli "zewnętrznej". Takie przetwarzanie tabeli powoduje ładowanie całego bloku pamięci bez "skakania po indeksach". Tablica jest obszarem pamięci o kolejno rosnących adresach elementów. Przy pomocy wywołania funkcji w C można sprawdzić, że te kolejne (według rosnących adresów w pamięci komputera) komórki pamięci przechowują kolejno rosnące wartości.

Program wypełnia tablicę kolejno rosnącymi wartościami i wyświetla je na ekranie. Indeks NX można utożsamiać z

      PROGRAM P2

      IMPLICIT NONE

      INTEGER NX
      INTEGER NY
      INTEGER NZ
      
      PARAMETER (NX = 3)
      PARAMETER (NY = 4)
      PARAMETER (NZ = 5)

      INTEGER VALUES(NX,NY,NZ)

      INTEGER I
      INTEGER J
      INTEGER K
      INTEGER SIZE
      INTEGER INDEX
 
      SIZE = NX*NY*NZ

      INDEX = 0


      DO 30 K=1, NZ

        DO 20 J=1, NY

          DO 10 I=1, NX

            VALUES(i,j,k) = INDEX
            INDEX = INDEX + 1

10        CONTINUE
20      CONTINUE
30    CONTINUE
 

      DO 60 K=1, NZ

        WRITE(*,700) K

        DO 50 J=1, NY
          
          WRITE(*,800) J

          DO 40 I=1, NX
            
            WRITE(*,*) VALUES(i,j,k)
            
40        CONTINUE
50      CONTINUE
60    CONTINUE

 
      STOP

700   FORMAT('====WARSTWA ', I1)
800   FORMAT('    KOLUMNA ', I1)

      ENDPROGRAM P2

W przypadku języka C w deklaracji takiej tablicy indeksy musiałyby być zapisane w odwrotnej kolejności (indeks i (od 0 do (NX-1)) z prawej strony, 'ostatni').

/*parametry NZ, NY, NX muszą być zdefiniowane. (np makra preprocesora)*/

int index = 0;

/* definicja tablicy */
int values[NZ][NY][NX];

/* przetwarzanie tablicy */
for(k = 0; k < NZ; ++k)
{
    for(j = 0; j < NY; ++j)
    {
        for(i = 0; i < NX; ++i)
        {
            values[k][j][i] = index++;
        }
    }
}

Tablice alokowane dynamicznie (na stercie)

W języku C dynamiczna alokacja pamięci polega na alokacji segmentu pamięci o rozmiarze n elementów określonego typu składowego. Np. 24 elementów typu int. Dostęp do elementów tablicy jest realizowany poprzez wskaźnik. Możemy sobie np. wyobrazić, że taki obszar pamięci przechowuje 4 wierszy po 6 elementów typu int (4 wiersze po 6 kolumn). Pierwsze 6 elementów tego bloku pamięci będzie odpowiadało pierwszemu wierszowi, kolejne 6 elementów będzie odpowiadało drugiemu wierszowi itd. Warto to rozrysować na kartce w kratkę. Reprezentacja pamięci w komputerze jest zawsze "liniowa". Indeksowanie jest sprawą "trochę umowną". Co ciekawe, taką "tablicę 2D" można narysować w konfiguracji "pierwszy wiersz umieszczony najniżej" lub też "pierwszy wiersz umieszczony najwyżej".