D/Tablice

Tablice

W D wyróżniamy kilka rodzajów tablic: tablice statyczne, tablice dynamiczne, tablice w stylu C (wskaźniki) oraz tablice assocjacyjne. Zajmiemy się pierwszymi trzema rodzajami.

Tablice statyczne

Tablica jest to pewien ciągły obszar pamięci komputera, który zawiera elementy takiego samego typu. Tablica tak więc charakteryzuje się typem elementów, które zawiera oraz liczbą tych elementów. Aby zdefiniować tablicę należy użyć nawiasów kwadratowych za typem zmiennej:

int[100] a;       // definiuje tablice statyczną o 100 elementach typu int

Deklaracja taka zdefiniuje zmienną a, która będzie służyła nam do obsługi tablicy. Kompilator dodatkowo zatroszczy się, aby utworzyć gdzieś w pamięci odpowiedni obszar na przechowywanie danych (zapewne o wielkości 100*int.sizeof = 400 bajtów), oraz inicjalizację wszystkich elementów (dla typu int jest to int.init, czyli 0). Zmienna a sama w sobie nie jest tablicą, ale w skrócie będziemy mówili, że a to tablica. Precyzyjnie a jest jedynie wskaźnikiem na pierwszy element tablicy (a typ tego wskaźnika to int*). Aby odczytać wartość tego wskaźnika należy użyć właściowości ptr zmiennej tablicowej (tj. a.ptr), będzie ona zawierała pewien adres maszynowy (o wielkości 32 lub 64 bitów zależności od architektury komputera) wskazujący na przydzieloną pamięć. Drugą ważną właściwością zmiennych tablicowych jest length (tj. a.length), która określa liczbę elementów, które znajdują się w tablicy. Dla tablic statycznych właściwość ta jest tylko do odczytu. Ostatnią ważną właściwością (wyłącznie do odczytu) jest sizeof (tj. a.sizeof), określająca liczbę bajtów zajętych przez całą tablicę.

writefln(a.ptr);
writefln(a.length);
writefln(a.sizeof);

wyświetli

BFB43B10
100
400

przy czym pierwsza wartość może się zmieniać (nawet na tym samym komputerze i kompilatorze).

Dostęp do elementów tablicy odbywa się poprzez indeks, będący liczbą naturalną. Pierwszy element tablicy ma indeks 0, ostatni n-1, gdzie n to łączna liczba elementów.

a[0] = 5;            // 1 element
a[51] = 4;           // 52 element
int i = 5;
a[i] = 6;            // indeksy mogą być oczywiście wyrażeniami typu int

writefln("pierwszy element: ", a[0]);            // 5
writefln("ostatni element: ", a[99]);            // 0 – ponieważ tablica domyślnie jest wypełniania zerami

Poprawne indeksy są określone przez warunek (i < a.length).

Ważne jest, aby pamiętać, iż indeks n (a.length) nie jest już prawidłowy.

writefln("ostatni? element: ", a[100]);   // błędny kod!

Kod taki w przypadku tablic statycznych nie powinien się skompilować:

tab1.d:8: Error: array index 100 is out of bounds a[0 .. 100]

W przypadku tablic dynamicznych kompilator dodaje odpowiedni kod, który sprawdza każde ręczne odwołanie do tablicy czy zawiera poprawne indeksy. Użycie niepoprawnego indeksu spowoduje wystąpienie wyjątku ArrayBoundsError i domyślnie przerwanie programu:

Error: ArrayBoundsError tab1.d(9)

Sprawdzanie poprawności indeksów tablic można wyłączyć podczas kompilacji przy pomocy flagi -release (należy jej używać tylko po przetestowaniu programu i kiedy zależy nam na prędkości).

Często używaną konstrukcją w przypadku tablic jest iterowanie po elementach:

for (int i = 0; i < a.length; i++) {
  a[i] *= 2;            // podwój wszystkie elementy tablicy
}

Notka: W wersji 1.034 oraz 2.018 kompilatora DMD zaimplementowano tzw. wyrażenia wektorowe, pozwala to na zapisanie poprzedniej pętli w krótki sposób:

a[] *= 2; // podwój wszystkie elementy tablicy

Kompilator w miarę możliwości wygeneruje kod korzystający z mechanizmów SIMD (SSE, Alitvec) lub wykonujący się na wielu procesorach. (Nie jest to jeszcze w pełni zaimplementowane)

Więcej o definicji tablic statycznych

Jeśli chcemy zdefiniować kilka tablic o takim samym rozmiarze, wystarczy dopisać je po przecinku w definicji:

int[100] a, b, c;  // trzy tablice każde zawierająca 100 intów

Istnieje również druga forma definiowania tablic:

int a[100];

W przypadku definiowania wielu zmiennych, należy dopisać rozmiar przy każdej zmiennej;

int a[100], b[100], c[100];

Nie jest dozwolone definiowanie w ten sposób tablic o różnych rozmiarach, liczby wymiarów czy wskaźnikach:

int a[100], d[200];     // BŁĄD
int a[100], *e;         // BŁĄD

Liczba (rozmiar) używana przy definiowaniu tablicy musi być stałą znaną podczas kompilacji. Poniższy kod nie jest poprawny:

int rozmiar = 5;                      //  można poprawić poprzez dodanie "const" 
int[rozmiar] a;

Również ten kod nie jest poprawny:

int rozmiar = wczytaj_liczbe();       // wczytaj liczbę z klawiatury
int[rozmiar] a;                       // zdefiniują tablicę o takim rozmiarze

Ponieważ nie da się określić rozmiaru tablicy podczas kompilacji.

Rozmiar tablicy statycznej może wynosić zero. Tablica taka nie zawiera danych i na nic nie wskazuje. Bywa użyteczna jako ostatni element struktur.

Ograniczenia

Pojedyncza tablica statyczna nie może być większa niż 16 MB. Tablice statyczną muszą mieć znany podczas kompilacji rozmiar i nie może się on zmieniać podczas wykonywania programu.

Tablice dynamiczne

Aby obejść ograniczenia tablic statycznych, używa się tablic dynamicznych. Jest to najczęściej używany rodzaj tablic w D. W przeciwieństwie do tablic statycznych, mogą one zawierać zmienną liczbę elementów. Zmienną tego typu deklaruje się bez podawania rozmiaru.

int[] a;

Tablica taka domyślnie zawiera zero elementów. Aby można było jej używać należy zmienić jej rozmiar:

a.length = 100;

To samo można osiągnąć poprzez operator new:

int[] a = new int[100];

W przeciwieństwie do tablic statycznych liczba, która określa nową wielkość tablicy może pochodzić z dowolnego wyrażenia.

Zmiana rozmiaru

Dzięki właściwości length można zwiększyć istniejący rozmiar tablicy:

a.length = 150;

Spowoduje to powiększenie tablicy z 100 na 150 elementów. Może się to wiązać z utworzeniem całkiem nowej tablicy (ponieważ tablica musi być ciągła w pamięci, a za aktualną tablicą nie ma miejsca) i skopiowaniem początku tablicy. Należy pamiętać, że jeśli nie ma wystarczającej ilości pamięci, powiększenie tablicy może się nie powieść (zostanie rzucony wyjątek OutOfMemory).

Możemy również zmniejszyć rozmiar pamięci:

a.length = 50;

Może to również spowodować utworzenie nowej tablicy (ale w obecnych implementacjach tak się zwykle nie dzieje). Dane znajdujące się w końcówce tablicy (która teraz jest niedostępna) są uznawane za nieistniejące (i garbage collector ma prawo je usunąć, czy wywołać destruktory obiektów jeśli nie są dostępne w inny sposób).

Łączenie tablic i dopisywanie do tablic

D posiada dwa operatory (oprócz []), które służą do manipulowania na tablicach. Jest to operator łączenia (ang. concatenation, marge) ~ oraz operator dopisywania (ang. append) ~= .

int[] a, b;

...

int[] c = a ~ b;  // utworzenie nowej tablicy o rozmiarze a.length+b.length, oraz elementach skopiowanych z a oraz b

c ~= 13;             // powiększenie tablicy c o 1 oraz wpisanie na ostatnią pozycję liczby 13
                     // równoważne: c.length = c.length + 1;
                     //             c[c.length-1] = 13;

c ~= [12,13,14];     // powiększenie tablicy c o 3 oraz wpisanie w utworzone miejsce elementów 12, 13, 14

Rezerwowanie tablicy

Ponieważ często zdarza się, że dopisujemy po jednym elemencie do tablic dynamicznych, należy zwrócić uwagę, że może być to nieefektywne.

Jeśli rozpoczynamy od tablicy o małym rozmiarze (albo pustej), a potem zwiększamy ją w każdym kroku (których jest dużo) o jeden (czy inną małą liczbę), to w każdym kroku może nastąpić reallokacja i kopiowanie początkowych elementów tablicy. Powoduje to zwiększenie złożoności algorytmów od dodatkowy czynnik O(n):

int[] a;
a ~= 5;  // reallokacja
a ~= 3;  // reallokacja i skopiowanie 5 oraz 3
a ~= 7;  // reallokacja i skopiowanie 5, 3 oraz 7
...

Są dwa sposoby przezwyciężenia tego problemu zachowując wygodę używania operatora dopisywania. Jeśli wiemy ile będzie zawierać elementów tablica po ukończeniu algorytmu, możemy zawczasu zarezerwować odpowiednią ilość miejsca w tablicy:

int[] a;
a.length = 100;   // rezerwujemy 100 miejsc, jedna reallokacja
a.length = 0;     // ustawiamy długość tablicy na 0. tablica nie zostanie zmniejszona w pamięci
a ~= 5;
a ~= 3;
a ~= 7;

Jeśli nie wiemy, jaki będzie docelowy rozmiar tablicy, czasami warto wykonać algorytm testowo, aby dowiedzieć się, jaki będzie rozmiar (chociaż w przybliżeniu, lub górne oszacowanie), a dopiero przy drugim wywołaniu algorytmu liczyć prawdziwe dane:

int[] a;
a.length = algorytm_przebieg_pierwszy();
a.length = 0;
algorytm_przebieg_drugi(a);

size_t algorytm_przebieg_pierwszy() {
  size_t rozmiar = 0;
  // dodaj 5
  rozmiar++;
  // dodaj 3
  rozmiar++;
  // dodaj 7
  rozmiar++;

  return rozmiar;        // zwróci liczbę 3 – ilość danych, które będziemy mieć
}
void algorytm_przebieg_drugi(int[] a) {
  a ~= 5;   // bez reallokacji
  a ~= 3;   // bez reallokacji
  a ~= 7;   // bez reallokacji
}

Innym sposobem jest nie zwiększanie rozmiaru tablicy o 1 przy każdym dopisywaniu, tylko o pewną dużą liczbę, lub o pewien stały czynnik (zwykle 2).

int[] a;
int rozmiar = 0;
chce_dodac_jeden_element(a);
a ~= 5;
chce_dodac_jeden_element(a);
a ~= 3;
chce_dodac_jeden_element(a);
a ~= 7;

void chce_dodac_jeden_elemnt(ref int[] x) {
  if (rozmiar-1 > x.length) {       // jeśli mamy miejsce w tablicy na dopisanie elementu
    return;                         //   to nic nie robimy
  }
  if (rozmiar == 0) {              // jeśli mamy pustą tablicę
    x.length = 1;                   //   to zmieniamy rozmiar na jeden element
    rozmiar = 1;                    //   zapamiętaj
    x.length = 0;                   //   oraz wyglądaj na pustą tablice
    return;
  }
  x.length = rozmiar*2;            //  w przeciwnym wypadku powiększamy rozmiar dwukrotnie
  x.length = rozmiar;              //  ale wyglądaj na taką samą
}

Dzięki temu reallokacje będą następować jedynie przy dostępie do elementów będących potęgami dwójki. Na przykład, jeśli już tym sposobem dodaliśmy 3000 elementów (wykonało się już jedynie ceil(log_2(3000)) = 12 reallokacji, bo 2^12 = 4096, a 2^11 = 2048), to dodanie kolejnego 1000 nie spowoduje żadnej reallokacji (bo nastąpi dopiero przy 4096, a potem dopiero przy 8192). Taka strategia powoduje zamortyzowanie kosztów reallokacji i co najwyżej dwukrotne zmarnowanie pamięci (w przypadku tablic statycznych musielibyśmy zallokować bardzo dużą tablicę, która pomieści wszystkie możliwe przypadki).

Szczegóły

Kod

writefln(a.ptr);
writefln(a.length);
writefln(a.sizeof);

wyświetli

B7D2BE00
100
8

Wycinki

Wycinki (ang. slice) można pobierać z tablicy za pomocą instrukcji kojarzącej się z deklaracją tablic w Pascalu:

int[] array = new int[5];
int[] slice = array[0..3];

Taki wycinek zawierać będzie elementy tablicy array o indeksach 0, 1 i 2 (indeks 3 nie będzie zawarty w wycinku!).

Konwersja tablic statycznych na dynamiczne

Tablicę statyczną można łatwo skonwertować na tablicę dynamiczną. W tym celu możemy użyć własności dup:

int[100] stArray;
int[] dArray = stArray.dup;

Należy jednak zauważyć, że zostanie utworzona nowa tablica i zużyta dodatkowa pamięć. Niestety D z uwagi na działanie i położenie tablic statycznych w pamięci uniemożliwia konwersję tablicy na dynamiczną bez realokacji danych.

Wewnętrzna reprezentacja

Liczba 8 wiąże się z wewnętrzną reprezentacją tablic dynamicznych. Obecnie jest ona równoważna poniższej strukturze:

struct {
  typ* ptr;           // wskaźnik do pierwszego elementu tablicy, 4 bajty na architekturze 32 bitowej
  size_t length;      // liczba elementów, zwykle 4 bajty
}

W eksperymentalnej wersji D, struktura ta zostanie zapewne zmieniona na poniższą:

struct {
  typ* ptr;           // wskaźnik na pierwszy element
  typ* beyond;        // wskaźnik za ostatni element
}

Wskaźnik beyond wskazuje na nieistniejące dane (zwykle). Użycie samych wskaźników pozwala na efektywniejszą implementacje pętli foreach. Wskaźnik ten nie jest bezpośrednio dostępny dla programisty. Użycie tablic dynamicznych nadal odbywa się poprzez właściwości lenght (równoważny (beyond-ptr)/typ.sizeof) oraz ptr.

Wewnętrzna struktura tablic dynamicznych czasami bywała wykorzystywana przy wywoływaniu funkcji printf. Ponieważ stringi w D nie są zakończone zerem, funkcji printf należy przekazać długość tablicy używając formatu.

printf("%*s\n", a.ptr, a.length);

Kod ten można było zapisać w skrócie jako:

printf("%*s\n", a);

Tego typu użycie jest wysoko niewskazane! Po zmianie wewnętrznej reprezentacji kod taki staje się niepoprawny!

Tablice asocjacyjne

Tablice asocjacyjne są to tablice, w których indeksy są niekoniecznie liczbami. Indeks tablicy asocjacyjnej zwany jest kluczem. Deklaracja tablicy asocjacyjnej oraz dodanie elementu wygląda następująco:

int[char[]] asArray;
asArray["hello"] = 2;

Aby usunąć element, używamy funkcji remove():

asArray.remove("hello");

Długość tablicy pobieramy tak samo, jak w przypadku pozostałych rodzajów tablic. Dodatkowo możemy pobrać listę kluczy oraz wartości w postaci tablic dynamicznych za pomocą własności keys i values.

Wskaźniki

Wskaźniki w D są identyczne jak wskaźniki w C. Istnieją one w języku głównie ze względów na współpracę z bibliotekami w języku C, oraz wykonywanie specjalistycznego kodu systemowego. Używanie ich jest niewskazane w normalnym i czystym kodzie D, głównie ze względu na brak wydajnej możliwości sprawdzenia poprawności użycia wskaźników. Ich istnienie utrudnia pracę garbage collectora oraz maszyn wirtualnych.

W normalnym kodzie praktycznie wszystkie użycia wskaźników można zastąpić poprzez tablice dynamiczne, parametry out i ref funkcji oraz typy referencyjne (te ostatnie w D są tylko dostępne dla obiektów klas).

Więcej szczegółów w rozdziale współpracy z C.