Nahoru
 

Jak funguje pole v programování

Pokud jste programátor, pravděpodobně používáte pole. Pole je jeden z elementárních prvků vyšších programovacích jazyků umožňující práci nad neurčeným nebo velkým počtem elementů, a to velmi jednoduše. Jak však takové pole funguje?

Nejprve si rychle zopakujme, jak pole funguje: Pole je nějaký počet boxů, do kterých můžeme ukládat nebo z nich vybírat data. Amatérsky si jej lze představit jako spoustu proměnných (anebo krabiček). Jejich počet může být řádově velký nebo klidně neurčitý.

//Následující kód je pseudokód
Mojepole = pole o délce 4 slova;
Mojepole[0] = "Ahoj"; //Ulož slovo „Ahoj“ na pozici 0 (do první krabičky)
Print(Mojepole[0]); //Vypiš slovo uložené na pozici 0, tedy slovo „Ahoj“

Pole a krabičky
Obrázek č. 1: Pole je jako hromada vzestupně očíslovaných proměnný (krabic), kam můžeme ukládat data.

Za zmínku stojí důležitá věc: Pokud vytvoříme (alokujeme) nové pole, jeho položky jsou nedefinované (tedy alespoň ve většině jazycích), dokud do nich něco neuložíme. Pokud bychom se například v jazyku C++ snažili vypsat nedefinovanou hodnotu, dostali bychom naprosto náhodnou odpověď, v horším případě segmentation fault error. Proč tomu tak je a jak vlastně programovací jazyk pole reprezentuje/alokuje?

Intuitivně bychom mohli tipnout, že zkompilovaný kód si při vytvoření pole uloží pozice všech „krabiček“ a pokud nějakou krabičku vyžádáme, pak ji z paměti „vyhrabe“. Takhle však pole nefunguje, jelikož by to bylo zbytečně složité. Kompilátory na to jdou chytřeji a mazaněji.

Není potřeba si pamatovat polohu všech krabiček. Kód si pamatuje pouze polohu první krabičky a všechny další vloží hned za ní ve vzestupném pořadí. Z toho plyne, že musíme vědět přesně kolik krabiček máme, abychom „nepřestřelili“ a nešáhli do paměti kam nemáme.

Znázornění fungování pole
Obrázek č. 2: Znázornění, jak je pole uloženo a co potřebujeme pro práci s polem

Touto implementací se stane práce s polem efektivní. Pamatovat si místo v paměti zvládneme hravě a pamatovat si počet krabiček taktéž. Bohužel, nelze míchat různé datové typy, tedy nelze ukládat čísla a písmena do jednoho pole. Je tomu tak proto, že potřebujeme identickou velikost krabiček, jinak bychom se do nich nemohli „trefovat“.

Příklad pole: Čísla mají tradičně velikost 4 bajty, takže pole o velikosti čtyř čísel bude mít 16 bajtů a na x-tou pozici se dostaneme pomocí vzorečku: „první krabička + (x * 4 bajty)“. Prvky samozřejmě počítáme od nultého indexu.

Jazyk C dokonce žádný objekt reprezentující pole nemá, takže v podstatě neumí pole. Jediné, co umí, je vyhradit si místo v paměti. O vše ostatní se musí programátor postarat sám. Kód v C by mohl vypadat nějak takto:

int delka = 4;
int *pole = (int*) malloc(delka * sizeof(int)); //Funkce malloc alokuje (vyhradí) na haldě místo pro 4 čísla a vrátí ukazatel na místo v paměti (ukazatel na první krabičku)

pole [0] = 10; //Uloží číslo 10 do prvního boxu (na indexu 0)
pole [1] = 20; //Uloží číslo 20 do druhého boxu (na indexu 1)
*(pole + 1) = 30; //Přepíše číslo 20 na číslo 30 – tento zápis má identický význam jako pole[1], avšak je zde krásně vidět, jak proměnná pole je ve skutečnosti pouze ukazatel do paměti, nikoliv nějaký abstraktní kontejner. Kompilátor C ví, že přičtením jedničky ve skutečnosti přičítáme 4 bajty (neboli robustněji sizeof(int)).

pole[4] = 10; //Zasahujeme mimo vyhrazenou paměť – nemáme tušení, co se stane
*(pole + 4) = 10; //Zasahujeme mimo vyhrazenou paměť – nemáme tušení, co se stane

Nyní se můžeme zeptat na další důležitou otázku: „Jak pole rozšířit?“. Velice často narážíme na situace, kde nevíme, kolik místa potřebujeme. Odpověď někoho může překvapit, protože řešení je velice jednoduché: Pro rozšíření pole vytvoříme nové a delší, staré kratší do něj nakopírujeme a zrušíme ho. Neexistuje však něco efektivnějšího? Paměť za polem již může být použita a jelikož potřebujeme všechny krabičky za sebou, není jiné řešení, než si na jiném místě v paměti vytvořit nové delší pole a data do něj překopírovat.

Pole není hromada náhodně umístěných krabiček, kde si kód pamatuje jejich randomizované pozice. Ve skutečnosti je pole pouze ukazatel na první položku a všechny ostatní elementy jsou v paměti hned za ní. Z toho důvodu musíme mít přesně danou velikost pole a jednotný datový typ, nebo alespoň datový typ o stejné velikosti (pro fajnšmekry). Díky tak triviální myšlence mají pole extrémně jednoduchou a efektivní implementaci.