Java (21) - Kolekce

Tento díl se skládá ze dvou částí. Ta první je lehce teoretičtější, jelikož se zabývá porovnáváním výkonu našich algoritmů – asymptotickou složitostí. V druhé části si řekneme, jaké kolekce má Java připravené ve svých standardních knihovnách.

Asymptotická složitost

Asyptotická složitost slouží ke klasifikaci algoritmů na základě jejich výkonu na různě velkých datech.

Motivace

Představme si, že máme dva programy, které pracují v lineárním čase - první zpracuje vstup velikosti v krocích, druhý jich potřebuje . Pokud bychom chtěli, aby oba algoritmy zpracovaly vstup ve stejném čase, tak bude stačit, když druhý algoritmus pustíme na dvakrát rychlejším počítači.

Naproti tomu kdybychom měli lineární algoritmus, který zpracuje vstup v krocích a kvadratický algoritmus, který vstup zpracuje v $n^{2}$ krocích, tak nám žádný trik se zrychlováním počítačů nepomůže. Vždy budeme schopni nalézt velikost dat, od které je lineární algoritmus rychlejší.

Škála v nekonečnu

První dva algoritmy jsou pro nás určitým způsobem srovnatelné, druhé dva nikoliv. Tím důvodem je škála v nekonečnu.

Pokud máme data obrovské velikosti, která se limitně blíží nekonečnu, tak můžeme algoritmy rozdělit do několika skupin podle funkce, která popisuje jejich chování. Pro algoritmy z každé skupiny platí, že jsou na nekonečných datech nekonečněkrát výkonnější než algoritmy ze skupiny následující. Algoritmy, které jsou ve stejné skupině, jsou stejně výkonné (asymptoticky rychlé).

$1 \\ll \\log(n) \\ll n \\ll n \\cdot \\log(n) \\ll n^{k} \\ll k^{n} \\ll n! \\ll n^{n}$

Příklad

Spočítali jsme, že náš algoritmus vykoná přesně $2n^{3} + n^{2} + 2n$ kroků, jakou má asymptotickou složitost?

Řešení: Při hledání asymptotické složitosti srovnáváme výkon zadaného algoritmu s funkcí ze škály v nekonečnu. Hledáme takovou funci, která je srovnatelná - to znamená, že pokud jednu z funkcí násobíme libovolnou konstantou (zrychlujeme a zpomalujeme počítač), tak je v některých případech od určitého bodu (velikosti dat) rychlejší jedna funce, v jiných ta druhá. Kdyby byla jedna funkce rychlejší ve všech případech, tak by to znamenalo, že funkce nejsou stejně asymptoticky rychlé (tj. limita jejich podílu v nekonečnu by byla buď nulová nebo nekonečná).

Nyní k samotnému postupu. Nejprve nalezneme člen, který je dominantní. To je ten člen, který nalezneme na škále nejvíce vpravo – v našem případě se jedná o $2n^{3}$ . Všechny ostatní členy můžeme vyškrtnout, protože s již zmiňovaným bodem pouze hýbou po ose x, ale na jeho existenci nemají žádný vliv (dominantní člen je od určité velikosti dat převáží). Ze stejného důvodu vyškrtneme multiplikativní konstantu 2. Náš algoritmus má proto asymptotickou složitost $n^{3}$ .

Pokud bychom chtěli provést zkoušku, tak bychom ji vykonali pomocí l'Hospitalova pravidla pro limitu podílu našeho výsledku a zadání v nekonečnu. Musí vyjít nenulové reálné číslo.

Co z toho plyne?

Pokud máme dva algoritmy s různou asymptotickou složitostí, tak vždy nalezneme bod (velikost dat), od které je jeden z nich výkonnější. Tato matematika platí pro většinu algoritmů již od velmi malých instancí - to znamená, že již na malých datech je poznat velmi velký rozdíl.

Třídy složitosti

Chování algoritmu bohužel nelze většinou popsat pouze jednou funkcí, jelikož se složitost algoritmu může měnit vzhledem ke struktuře dat. Jednou může algoritmus terminovat v kvadratickém čase, jindy pouze v lineárním (takto se chová například insertion sort).

Z tohoto důvodu zavádíme třídy složitosti. Třída složitosti O(f(x)) (čteme omicron f(x)) říká, že se algoritmus bude v asymptoticky nejhorším případě chovat jako f(x) . Oproti tomu třída $\\Omega(f(x))$ (čteme omega f(x)) říká, že se algoritmus v nejlepším případě bude asymptoticky chovat jako f(x). Pokud chceme vyjádřit, že algoritmus spadá do obou tříd zároveň (tj. chová se přesně jako funkce v argumentu), tak použijeme třídu $\\Theta(f(x))$ (théta f(x)).

Již zmíněný insertion sort by spadal do třídy $O(n^{2})$ , méně přesně také do třídy $\\Omega(n)$ .

Příklad

Ukažme si nyní celý postup na příkladu. Budeme zjišťovat asymptotickou složitost selection sortu.

Selection sort je řadicí algoritmus, který nejprve nalezne nejvyšší prvek pole a umístí jej na první index. Protože je první index seřazen a zbytek pole obsahuje pouze nižší prvky, tak zde může selection sort opakovat stejnou proceduru. Tímto způsobem dochází k postupnému zařazování nejvyšších prvků a ke zkracování neseřazeného úseku. V okamžiku, kdy algoritmus zpracuje poslední prvek (jenž je zařazen triviálně), je pole seřazeno v sestupném pořadí.

Kód

Java

/**
 * Razeni vyberem (od nejvyssiho)
 * @param array pole k serazeni
 */
 public static void selectionSort(int[] array){
     for(int i = 0; i < array.length - 1; i++){
         int maxIndex = i;
         for(int j = i + 1; j < array.length; j++){
             if(array[j] > array[maxIndex]) maxIndex = j;
         }
         int tmp = array[i];
         array[i] = array[maxIndex];
         array[maxIndex] = tmp;
     } 
 }

Výpočet složitosti

Při zjišťování počtu operací můžeme sledovat rozdílné věci – počet elementárních operací, počet elementárních operací nad daty nebo počet operací porovnání. Naštěstí všechny tyto metody dávají stejný výsledek.

Protože ignorujeme veškeré aditivní a multiplikativní konstanty (podvod se zrychlováním počítače), tak se můžeme soustředit počet iterací příkazů ve vnitřní smyčce.

První iterace proběhne n-1 krát, poslední (pořadové číslo n-1 ) pouze jednou. Celkový počet operací vypočteme pomocí vzorce pro aritmetickou posloupnost.

$n-1 + n - 2 + \\cdots + 1 = (n - 1) \\cdot {{n-1+1} \\over {2}} = (n^2 - n) /2$

Nyní opět zanedbáme multiplikativní konstanty a vychází nám složitost n^2 - n . Nyní si vzpomeneme na to, že nás zajímá pouze dominantní člen, a zanedbáme proto lineární člen. Vychází nám složitost $n^{2}$ . Protože se jedná o nejlepší i o nejhorší možný běh algoritmu, tak je výsledná asymptotická složitost selection sortu $\\Theta(n^{2})$ .

Kolekce

Po tomto (nutném) teoretickém výletu se vrátíme zpět do luhů a hájů Javy a představíme si již hotové implementace kolekcí, které jsou obsaženy ve standardních knihovnách.

Nyní jsme po všech stránkách dostatečně vyzbrojeni, abychom pochopili rozdíly v implementaci těchto kolekcí. Použití správného kontejneru na správném místě nám ušetří spoustu času při programování a zároveň zajistí dobrý výkon aplikace.

Nevynalézat kolo...

Patrně si říkáte, proč jsme psali v minulých dílech knihovny sami, vždyť to byla zbytečná práce... a budete mít do určité míry pravdu. Opravdu nemá smysl vynalézat kolo, protože jeho existující implementace jsou často perfektní a hlavně prověřené. Na druhou stranu je nutné vědět, jakým způsobem jsou vytvořeny základy staveb, které používáme.

...ale znát jeho konstrukci

Nepoučený programátor, který si nepřečetl minulý díl (hashovací tabulka) a ještě přeskočil první část tohoto dílu, by například velmi snadno mohl používat pro vyhledávání ve velkých souborech dat seznam (složitost O(n) ), místo toho, aby použil již zmíněnou hashovací tabulku (průměrně O(1) ). Jeho program by při jakémkoliv větším zatížení šel velmi rychle k zemi.

Kolekce implementující rozhraní List

Prvním typem kolekcí, které zde probereme, budou ty založené na rozhraní List (dokumentace). Jak již název napovídá, tak se jedná o seznamy.

ArrayList

ArrayList (dynamické pole) je seznam postavený nad polem. Tuto kolekci jsme implementovali v desátém dílu tohoto seriálu. Připomeňme si stručně vlastnosti této implementace.

Největší výhodou ArrayListu (dokumentace) je přístup k libovolnému prvku v konstantním čase O(1) , nevýhodou pak občasná nutnost kopírování všech prvků do nového pole (při rozpínaní a zmenšování kolekce), kvůli které operace vkládání zabere až O(n) operací.

Tato skutečnost ale není ve většině případů kritická, protože zde figuruje tzv. amortizace operace. Díky amortizaci dojde k rozložení nákladů na přesun pole do všech operací vkládání, které jej nevyžadují. Průměrně proto operace vložení zabere pouze konstantní množství kroků.

Java

        List<String> list = new ArrayList<String>();
        list.add("jedna");
        list.add("dva");
        list.add("tri");

        System.out.println(list.get(0)); //jedna
        System.out.println(list.get(1)); //dva
        System.out.println(list.get(2)); //tri

LinkedList

LinkedList (dokumentace) – spojový seznam – jsme implementovali v šestnáctém dílu. Jedná se o posloupnost zřetězených objektů, z nichž každý obsahuje ukládanou hodnotu. Naše implementace byla jednosměrně zřetězená (tj. každý uzel obsahoval pouze ukazatel na další prvek), javovský LinkedList je obousměrně zřetězený (tj. uzel obsahuje ukazatel i na předchozí prvek).

Největší nevýhodou LinkedListu je absence libovolného přístupu – pokud chceme i-tý prvek, tak spotřebujeme O(i) operací na přeiterování všech předchozích prvků. Výhodou oproti dynamickému poli je absence realokace, díky které je spojový seznam vhodný pro použití v systémech, v nichž musíme garantovat odpověď v určitém časovém horizontu (u dynamického pole si nikdy nemůžeme být jisti, že nedojde k onomu nejhoršímu případu).

Java

        List<String> list = new LinkedList<String>();
        list.add("jedna");
        list.add("dva");
        list.add("tri");

        System.out.println(list.get(0)); //jedna
        System.out.println(list.get(1)); //dva
        System.out.println(list.get(2)); //tri

Vector

Vector (dokumentace) je obdobou dynamického pole. Jediným rozdílem je, že je synchronizovaný. Synchronizovanost znamená, že lze tuto kolekci využívat najednou z více vláken (jaké to má přesně důsledky si ukážeme v některém z dalších dílů). Nevýhodou synchronizace pak je overhead, který s sebou automaticky přináší – z tohoto důvodu se používá pouze tehdy, je-li k tomu skutečně pádný důvod.

Vector je zastaralá kolekce, proto bychom ji neměli v nových programech vůbec používat. Synchronizace kolekce můžeme dosáhnout i jinými prostředky (voláním metody synchronizedList třídy Collections (dokumentace)).

Java

        List<String> list = new Vector<String>();
        list.add("jedna");
        list.add("dva");
        list.add("tri");

        System.out.println(list.get(0)); //jedna
        System.out.println(list.get(1)); //dva
        System.out.println(list.get(2)); //tri

Kolekce implementující rozhraní Map

Druhým typem kolekcí jsou kontejnery, které implementují rozhraní Map (dokumentace). V české terminologii se kromě slova mapa také používá označení tabulka.

HashMap

HashMap odpovídá hashovací tabulce z minulého dílu. Připomeňme si, že její hlavní výhodou bylo vyhledávání prvku dle klíče v průměrně konstantním čase. Nepříjemností pak bylo negarantování jakéhokoliv pořadí prvků.

Hashovací tabulka má v Javě řadu variant. Třída Hashtable (dokumentace) je synchronizovaná. Třída WeakHashMap (dokumentace) umožňuje garbage kolekci záznamů, na jejichž klíče již neexistuje žádná další reference (tj. lze ji využít jako cache citlivou na paměť). LinkedHashMap (dokumentace) vnitřně obsahuje navíc spojový seznam – mapa je schopna garantovat predikovatelné pořadí prvků. Posledním významnou modifikaci je ConcurrentHashMap (dokumentace), která umožňuje vícevláknové použití, aniž by docházelo k zamykání zdrojů (více se opět dozvíme v následujících dílech).

Java

        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(2, "dva");
        map.put(1, "jedna");

        System.out.println(map.get(1)); //jedna
        System.out.println(map.get(2)); //dva

TreeMap

TreeMap je mapa, jejíž klíče jsou seřazené za pomoci předaného Comparatoru (třídy, která rozhoduje relaci větší než mezi jednotlivými prvky).

Kolekce je implementovaná jako červeno-černý strom (red-black tree), což je výškově vyvážený binární strom, který má v každém okamžiku hloubku úměrnou $\\log_{2}(n)$ . Z této skutečnosti plyne také složitost základních operací (containsKey, get, put, remove), která je $O(\\log_{2}(n))$ .

Java

        Map<Integer, String> map = new TreeMap<Integer, String>();
        map.put(2, "dva");
        map.put(3, "tri");
        map.put(1, "jedna");

        for(Integer key : map.keySet()){
            System.out.println(map.get(key)); //jedna dva tri (serazene podle klice)
        }

Kolekce implementující rozhraní Set

Třetí významnou skupinou kontejnerů jsou množiny – kolekce implementující rozhraní Set (dokumentace). Jedná se fakticky o mapy, které jako klíč i hodnotu používají totožný objekt. Tohoto chování využijeme v okamžiku, kdy chceme z dané kolekce opakujících se hodnot vybrat každou právě jednou (množina neumožňuje opakování prvků).

HashSet a TreeSet

Stejně jako u map se setkáme především s dvěma implementacemi – HashSet (dokumentace) a TreeSet (dokumentace). Vlastnosti těchto kolekcí odpovídají vlastnostem příslušných map. HashSet umožňuje vyhledat prvek v průměrně konstantním čase, prvky v TreeSetu jsou seřazené a přístup k nim zabere $O(\\log_{2}(n))$ operací.

Java

        Set<Integer> set = new HashSet<Integer>();
        set.add(1);
        set.add(37);
        set.add(1);
        set.add(17);

        for(Integer i : set){
            System.out.println(i); //17 1 37 (zadna duplicita, poradi negarantovano)
        }

        Set<Integer> set2 = new TreeSet<Integer>();
        set2.add(37);
        set2.add(17);
        set2.add(37);
        set2.add(1);

        for(Integer i : set2){
            System.out.println(i); //1 17 37 (zadna duplicita, serazeno)
        }

Další kolekce

Kromě výše uvedených existuje ještě mnoho různých kolekcí. V této části si ze zbytku vyjmenujeme ty nejužitečnější.

Rozhraní Deque a Queue

Kolekce, které implementují rozhraní Deque (dokumentace) jsou seznamy, u kterých lze manipulovat jak s prvky na začátku, tak na konci. Pomocí manipulace s prvky na konci seznamu lze vytvořit zásobník (stack). Zásobník je kolekce, z níž je poslední vložený prvek vybrán jako první. Tomuto přístupu se říká LIFO – last in, first out.

Opačnou strategii (LILO – last in, last out) používají kontejnery implementující rozhraní Queue (dokumentace) – fronty. Objekt, který je vložen jako poslední, je z kolekce také jako poslední vybrán.

Java


        Deque<Integer> stack = new LinkedList<Integer>(); //spojovy seznam je obousmerny
        stack.add(1);
        stack.add(2);
        stack.add(3);

        System.out.println(stack.pollLast()); //3
        System.out.println(stack.pollLast()); //2
        System.out.println(stack.pollLast()); //1
        System.out.println(stack.isEmpty()); //true


        Queue<Integer> q = new LinkedList<Integer>(); //spojovy seznam implementuje take frontu
        q.add(1);
        q.add(2);
        q.add(3);

        System.out.println(q.poll()); //1
        System.out.println(q.poll()); //2
        System.out.println(q.poll()); //3
        System.out.println(q.isEmpty()); //true

Prioritní fronta

Poslední kolekcí, kterou si dnes uvedeme, je prioritní fronta. Jedná se o klasickou frontu s tím, že prvky s vyšší prioritou (hodnotou) mohou předbíhat. Typickou implementací je datová struktura halda (heap), ve které je složitost výběru a přidání prvku $O(\\log_{2}(n))$ .

Java

        Queue<Integer> queue = new PriorityQueue<Integer>();
        queue.add(1);
        queue.add(4);
        queue.add(3);
        queue.add(2);

        //vsimnete si serazeni (za vyssi prioritu je povazovana nizsi hodnota cisla)
        //razeni prioritni frontou (binarni haldou) se nazyva heapsort a ma asymptotickou slozitost O(n*log(n))
        System.out.println(queue.poll()); //1
        System.out.println(queue.poll()); //2
        System.out.println(queue.poll()); //3
        System.out.println(queue.poll()); //4

Asymptotická složitost

Motivace

Škála v nekonečnu

Příklad

Co z toho plyne?

Třídy složitosti

Příklad

Kód

Výpočet složitosti

Kolekce

Nevynalézat kolo...

...ale znát jeho konstrukci

Kolekce implementující rozhraní List

ArrayList

LinkedList

Vector

Kolekce implementující rozhraní Map

HashMap

TreeMap

Kolekce implementující rozhraní Set

HashSet a TreeSet

Další kolekce

Rozhraní Deque a Queue

Prioritní fronta

Doporučujeme