Czym jest tablica w programowaniu?

Aplikacja pogodowa, która pokazuje temperatury z całego tygodnia, potrzebuje siedmiu liczb. Mogłaby użyć siedmiu osobnych zmiennych, monday, tuesday i tak dalej, ale wtedy żadna pętla nie mogłaby ich przejść, a dodanie ósmego dnia wymagałoby pisania nowego kodu. Tablica umieszcza wszystkie siedem liczb pod jedną nazwą, temperatures, w ponumerowanych miejscach od 0 do 6.

Jak działa tablica

Tablica trzyma elementy obok siebie w jednym bloku pamięci, a każdy element zajmuje tyle samo bajtów. Taki układ pozwala komputerowi znaleźć dowolny element jednym obliczeniem:

address of element i = start address + i × element size

Załóżmy, że tablica 32-bitowych liczb całkowitych (po 4 bajty każda) zaczyna się pod adresem pamięci 1000. Element 0 jest pod adresem 1000, element 1 pod 1004, element 2 pod 1008, a element 3 pod 1012. Dojście do elementu 3 albo do elementu 3 000 000 zajmuje ten sam jeden krok, dlatego odczyt z tablicy po indeksie nazywa się operacją w czasie stałym, zapisywanym jako O(1).

Moduł array w Pythonie przechowuje surowe liczby właśnie w ten sposób, więc możesz sprawdzić te obliczenia:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

Ten wzór wyjaśnia też, dlaczego większość języków liczy od 0. Indeks to przesunięcie: ile elementów trzeba pominąć od początku. Pierwszy element jest 0 elementów od początku, więc ma indeks 0, a ostatni element tablicy o długości n ma indeks n − 1. Kilka języków, takich jak Lua, MATLAB, R i Fortran, zaczyna od 1.

Tablica w Pythonie

Większość kodu w Pythonie używa wbudowanej list jako tablicy. Tworzysz ją nawiasami kwadratowymi, odczytujesz i zmieniasz elementy po indeksie, a długość sprawdzasz przez len():

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

Ujemny indeks liczy od końca, więc temperatures[-1] to ostatni element. Ten skrót jest cechą Pythona; C i Java nie mają ujemnych indeksów.

Ile kosztują operacje na tablicy

Ciągły układ sprawia, że niektóre operacje są szybkie, a inne wolne. Koszt rośnie wraz z n, czyli liczbą elementów:

Wstawianie na początku jest wolne, bo każdy element musi przesunąć się o jedną pozycję, żeby zrobić miejsce. Szukanie w nieposortowanej tablicy oznacza wyszukiwanie liniowe przez kolejne elementy, a posortowana tablica pozwala na wyszukiwanie binarne, które na każdym kroku dzieli pozostały zakres na pół.

Przechodzenie przez tablicę w pętli

Tablice i pętle idą w parze: pętla odwiedza kolejno każdy element, co nazywa się iteracją. Te same kilka linii obsłuży tablicę z 5 elementami albo z 5 milionami.

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Tablice w innych językach

W C tablica ma stały rozmiar ustalany przy deklaracji i przechowuje surowe wartości jednego typu. sizeof podaje jej rozmiar w bajtach:

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Tablice w Javie też mają stałą długość, a nowe elementy dostają wartość domyślną, na przykład 0 dla liczb. Gdy w Javie potrzebujesz tablicy, która rośnie, używasz ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

Tablice w JavaScripcie swobodnie rosną i maleją, a także mogą mieszać typy, jak w [1, "two", true].

Tablice, które rosną, takie jak list w Pythonie, ArrayList w Javie i std::vector w C++, nazywa się tablicami dynamicznymi. Rezerwują dodatkowe miejsce na końcu. Gdy to miejsce się kończy, przydzielają większy blok, kopiują do niego wszystkie elementy i działają dalej. Kopiowanie zdarza się na tyle rzadko, że dodawanie na końcu pozostaje średnio szybkie.

Tablica może też przechowywać inne tablice. grid[row][col] odczytuje jedną komórkę tablicy dwuwymiarowej, czyli układu używanego w planszach do gier, arkuszach kalkulacyjnych i obrazach. Przewodnik po tablicach wielowymiarowych w C pokazuje, jak leżą one w pamięci.

Częste błędy

Pomyłka o jeden. Tablica z 3 elementami ma indeksy 0, 1 i 2, więc indeks 3 wychodzi poza koniec. Python zatrzymuje się z błędem:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java rzuca wyjątek ArrayIndexOutOfBoundsException, a JavaScript po cichu zwraca undefined. C nie sprawdza niczego: odczyt poza końcem to niezdefiniowane zachowanie, które może zwrócić śmieci albo przerwać program błędem segmentacji.

Kopiowanie przez przypisanie. W Pythonie, Javie i JavaScripcie b = a nie kopiuje tablicy; obie nazwy wskazują na tę samą tablicę, więc zmiana b zmienia a. Prawdziwą kopię daje a.copy() w Pythonie albo [...a] w JavaScripcie. Strona o zmiennych wyjaśnia dlaczego.

Co dalej

Tablica jest przydatna tylko z pętlą, która ją przechodzi, więc przeczytaj teraz, czym jest iteracja, a także czym jest bajt, czyli jednostka stojąca za rozmiarami elementów powyżej. Przewodnik po listach w Pythonie omawia wycinanie, sortowanie i metody list, a wizualizacja listy wiązanej pokazuje strukturę, która zamienia szybkie indeksowanie na szybkie wstawianie.