D/Tablice

Z Wikibooks, biblioteki wolnych podręczników.
< D
Przejdź do nawigacji Przejdź do wyszukiwania

Tablice[edytuj]

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[edytuj]

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 ilością 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 wsaź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 ilość elementów które znajdują się w tablicy. Dla tablic statycznych właściwość ta jest tylko do odczytu. Ostatnią ważna właściwością (wyłącznie do odczytu) jest sizeof (tj. a.sizeof), określająca ilość 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 ilość 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 wszyskie elementy tablicy
}

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

a[] *= 2; // podwój wszyskie 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 zaimplemetowane)

Więcej o definicji tablic statycznych[edytuj]

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 defniowanie w ten sposób tablic o różnych rozmiarach, ilości 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ą podaczas 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[edytuj]

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

Tablice dynamiczne[edytuj]

Aby obejść ograniczenia tablic statycznych, używa się tablic dynamicznych. Jest to najcześ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[edytuj]

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

a.length = 150;

Spowoduje 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łąć destruktory obiektów jeśli nie są dostępne w inny sposób).

Łączenie tablic i dopisywanie do tablic[edytuj]

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 utworzeone miejsce elementów 12,13,14

Rezerwowanie tablicy[edytuj]

Ponieważ często zdarza się że dopisujemy po jednym elemencie do tablicy 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 w każdym kroku (których jest dużo) ją 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) {       // jesli mamy miejsce w tablicy na dopisanie elementu
    return;                         //   to nic nie robimy
  }
  if (rozmiar == 0) {              // jesli mamy pusta tablice
    x.length = 1;                   //   to zmieniamy rozmiar na jeden element
    rozmiar = 1;                    //   zapamietaj
    x.length = 0;                   //   oraz wyglądaj na pustą tablice
    return;
  }
  x.length = rozmiar*2;            //  w przeciwnym wypadku powiekszamy rozmiar dwukrotnie
  x.length = rozmiar;              //  ale wyglądaj na taką samą
}

Dzięki temu reallokacje będą następować jedynie przy dostępnie 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óre pomieści wszsytkie możliwe przypadki).

Szczegóły[edytuj]

Kod

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

wyświetli

B7D2BE00
100
8

Wycinki[edytuj]

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[edytuj]

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 reprezetnacja[edytuj]

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;      // ilość 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 zmienie wewnętrznej reprezentacji kod taki staje się niepoprawny!

Tablice asocjacyjne[edytuj]

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[edytuj]

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.