V dnešním desátém dílu navážeme na díl předchozí a ukážeme si, jak vytvořit natahovací (dynamické) pole – kolekci ArrayList. Tato struktura je již v Javě připravena (a na lepší úrovni, než k jaké se dnes dostaneme), ale i tak je velmi vhodné, abychom si ukázali, jak přesně uvnitř funguje, protože bez pochopení základních principů jednotlivých kolekcí je takřka nemožné napsat efektivní program.
Zároveň si touto malou exkurzí do skutečného světa programování procvičíme některé konstrukty z minulých dílů, které zůstaly v pozadí (zejména pak vytváření instancí (klíčové slovo new) a instančních metod a proměnných).
Dynamické pole
Dynamické pole ukládá veškeré prvky do bězného pole, které jak víme z minulého dílu, má neměnnou délku. V okamžiku, kdy překročíme délku tohoto pole, tak ArrayList vytvoří nové pole dvojnásobné délky, překopíruje do něj veškeré prvky a původní pole zahodí.
V případě, že je značná část pole nevyužívaná, tak ArrayList vytvoří nové menší pole, do nejž opět veškerá překopíruje a původní pole zahodí (čímž nám ušetří paměť).
Složitost operace vkládání
Asymptotická složitost vkládání
Každého ihned napadne, že je tento postup poměrně neefektivní, protože v okamžiku, kdy dojde místo, tak musíme vše zkopírovat – asymptotická složitost operace vkládání prvku je proto . Asymptotická složitost jednoduše řečeno označuje počet elementárních operací, které je nutné vykonat vzhledem k datům velikosti n (v
notaci se jedná o počat operací v nejhorším případě). Pro podrobnější a přesnější výklad si přečtěte tento článek.
Amortizovaná složitost vkládání
Druhou stranou mince je tzv. amortizovaná složitost, která počítá s tím, že program nějakou dobu běží a tato operace se proto může určitým způsobem splatit.
Představme si, že každému prvku dáme mincí (kde k je nějaká konstanta), kterými může platit za operace, které s ním nakládají. První minci prvek utratí při vložení do pole,
si jich může ponechat v banku na horší časy.
V okamžiku, kdy je pole velikosti n plné, tak je v banku přesně mincí (pole bylo po minulé realokaci pouze z poloviny prázdné, protože bylo nataženo dvojnásobně). Nyní ArrayList vytvoří nové pole a kopíruje veškeré prvky, za každé přenesení prvku z banku sebere k mincí (stojí k operací). Po překopírování všech prvků je sice bank prázdný, ale celou tuto proceduru vkládání a přenášení můžeme znovu opakovat.
Protože je konstanta (k je konstanta), tak je amortizovaná složitost
, jelikož jak amortizovaná, tak asymptotická složitost, ignorují multiplikativní konstanty (tím dochází k normování složitosti na libovolně rychlý počítač – pokud použijeme 2x výkonnější stroj, tak samotný výpočet sice proběhne 2x rychleji, ale informace o efektivitě algoritmu vzhledem k velikosti dat zůstane totožná).
Závěr
Z tohoto teoretického exkurzu si odnášíme jedno významné poučení. Neexistuje výkonový (asymptotický) rozdíl v tom, zda-li v dlouho běžícím programu použijeme pole nebo ArrayList, protože se náklady jeho realokace ztratí. Rozdíl existuje pouze pokud nám jde o okamžitou odezvu aplikace (real-time systémy), kdy u ArrayListu nejsme schopni garantovat, že nedojde k onomu nejhoršímu případu s asymptotickou složitostí .
Implementace ArrayListu
Nyní, když už známe všechny souvislosti, tak můžeme přistoupit k samotné implementaci struktury. Všechny metody budou instanční, jelikož se budou vztahovat k datům uloženým v konkrétním dynamickém poli. Samotou třídu nazveme MyArrayList, aby nedocházelo ke kolizi názvu s třídou java.util.ArrayList (oficiální implementace – dokumentace).
Fieldy a konstruktory
/**
* Dynamicke pole
* @author Pavel Micka
*/
public class MyArrayList {
private final int defaultSize;
private int size;
private int[] array;
/**
* Konstruktor - vychozi kapacita listu je 4
*/
public MyArrayList() {
this(4);
}
/**
* Konstruktor, lze nastavit vychozi delku listu, pod tuto nebude nikdy zkracen
* @param size
*/
public MyArrayList(int size) {
this.size = 0;
this.defaultSize = size;
array = new int[size];
}
V dynamickém poli umožníme uživateli, aby specifikoval výchozí hodnotu velikosti pole, pod kterou se již ArrayList nikdy nesmrští (defaultSize). Toto je zapotřebí, aby když uživatel ví, že budou uloženy miliony prvků, nedocházelo k neustálému natahovaní pole (sice jsme si řekli, že nám to amortizovaně nevadí, tj. čas to zabere maximálně násobně delší, ale tento násobek chceme maximálně snížit). Tato instanční proměnná je konečná (final), aby ji již nešlo změnit.
Druhou proměnnou je size – počet aktuálně uložených prvků. Poslední a nejdůležitejší součástí je samotné pole, do kterého budeme jednotlivé prvky ukládat (v tomto případě celočíselné hodnoty int).
Konstruktory má třída dva. Jeden bezparametrický pro vyšší pohodlí uživatele, který pouze volá druhý konstruktor s parametrem výchozí hodnoty délky pole. Druhý konstruktor dělá veškerou práci – nastavuje počet uložených prvků na 0, ukládá výchozí délku a hlavně inicializuje samotné pole.
Metoda enlarge
/**
* Prodlouzi dvojnasobne pole
*/
private void enlarge() {
int[] newArray = new int[size * 2];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
Metoda enlarge vytvoří nové dvojnásobně dlouhé pole a obsah starého pole do něj zkopíruje. Na závěr nahradí odkaz na staré pole odkazem na pole nové (staré pole zničí garbage collector). Metoda je soukromá, aby nemohla být volána mimo tuto třídu – použitím public bychom zbytečně odhalovali implementaci a ponoukali uživatele, aby zkusil, co to udělá (volání ve špatnou chvíli by pouze způsobilo havárii programu).
Metoda trim
/**
* Pokud je pole plne mene nez z ctvrtiny, tak ho zkratime na polovinu
* (pokud by to nebylo mene, nez je vychozi delka)
*/
private void trim() {
if ((array.length / 4) > size && array.length / 2 >= defaultSize) {
int[] newArray = new int[array.length / 2];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
}
Opačnou práci než enlarge dělá metoda trim. Pokud je pole obsazené pouze ze čtvrtiny, tak jej, je-li to možné (tj. neporušíme výchozí délku), zkrátí na polovinu. Tohoto je opět docíleno pomocí alokace nového polovičního pole, překopírováním obsahu a výměnou referencí.
Metoda add
/**
* Prida prvek do arraylistu
* @param i prvek k pridani
*/
public void add(int i) {
if (size == array.length) {
this.enlarge();
}
array[size] = i;
size++;
}
Metoda add přidá prvek na konec pole. Je-li pole již plně obsazené, pak nejprve zavolá metodu enlarge, která pole nejprve prodlouží. Na závěr metoda inkrementuje proměnnou reprezentující počet prvků.
Tato metoda je samozřejmě veřejná, abychom umožnili uživateli s touto strukturou pracovat.
Metoda remove
/**
* Odstrani prvek na zadanem indexu
* @param index index prvku k odstraneni
*/
public void remove(int index) {
array[index] = array[size - 1];
size--;
trim();
}
Komplementární metodou k add je remove, která odstraní prvek na zadaném indexu, na volné místo umístí poslední prvek a dekrementuje proměnnou size.
Tato implementace je velmi naivní, protože odstranění prvku způsobí přehození posledního prvku na jiné místo, což nemusí být žádoucí. Alternativním řešením by bylo setřepávání, kdy bychom přemístili všechny následující prvky o jedno místo doleva. Nevýhodou tohoto přístupu by pro změnu byla asymptotická složitost , která se bohužel nijak neamortizuje.
Metoda get
/**
* Vrati prvek na zadanem indexu
* @param index index prvku
* @return pozadovany prvek, Integer.MAX_VALUE v pripade pristupu na nevhodny index
*/
public int get(int index) {
if (index >= size) {
return Integer.MAX_VALUE;
}
return array[index];
}
Metoda get slouží k přístupu k prvku na zvoleném indexu. V případě použití indexu neexistujícího prvku (tj. vyšší nebo rovno size) metoda vrátí Integer.MAX_VALUE, což je maximální hodnota, kterou může datový typ int reprezentovat.
Tento přístup není vhodný, protože si tím značně znepříjemňujeme ukládání (a hlavně výběr) této hodnoty. Správným řešením by bylo použití výjimky – zprávy, která modifikuje tok a značí chybu programu. Výjimky jsme bohužel zatím neprobrali, ale toto je ukázkový příklad jejich vhodného nasazení.
Metoda toString
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size; i++) {
builder.append(array[i]);
builder.append(" ");
}
builder.append("\\narray.length: ");
builder.append(array.length);
builder.append(", size: ");
builder.append(size);
builder.append(", default size: ");
builder.append(defaultSize);
return builder.toString();
}
Metoda toString je speciální metoda, kterou má každý objekt, a která vrací řetezec, jež tento objekt reprezentuje. V našem případě bude vracet výpis všech uložených hodnot, aktuální délky pole hodnot, počtu uložených prvků a výchozí délky dynamického pole.
Pro ukládání mezivýstupu používáme třídu StringBuilder (dokumentace), což je v podstatě dynamické pole pro znaky. Výhoda tohoto přístupu oproti zřetězování (operátoru +) je v tom, že se nevytváří značné množství zcela zbytečných objektů (výstupem každého zřetězení je nový objekt řetězce).
Na osmé řádce si všimněme sekvence znaků \\n, která značí odřádkování (znak line feed). Na poslední řádce voláme toString metodu StringBuilderu, která nám vrací jeho textovou reprezentaci – uložený řetězec.
Gettery délky
/**
* Getter na vychozi delku pole
* @return vychozi delka pole
*/
public int getDefaultSize() {
return defaultSize;
}
/**
* Vrati pocet prvku ulozenych v poli
* @return pocet ulozenych prvku
*/
public int getSize() {
return size;
}
Posledními metodami jsou gettery na výchozí velikost dynamického pole a na počet uložených prvků.
Volání ArrayListu
public static void main(String[] args) {
MyArrayList list = new MyArrayList(10); //nova instance
list.add(4);
list.add(5);
list.add(6);
System.out.println(list); //toString metoda
System.out.println(list.get(2)); //6
System.out.println(list.get(3)); //2147483647 == Integer.MAX_VALUE
System.out.println(list.getSize()); //3
list.remove(0);
System.out.println(list);
System.out.println(list.get(0)); //6 - doslo k prohozeni
}
Projekt obsahující veškeré zdrojové kódy si můžete stáhnout zde.