ARCHIV

Java (12) - Kontejnery III.

Pojednání o kontejnerech by nebylo úplné, kdybychom vynechali algoritmy, které nad nimi pracují. Také se podíváme na nové (a vesměs příjemné) věci, které se do The Collections Framework dostaly v Javě 5.0.

26.4.2005 06:00 | Lukáš Jelínek | Články autora | přečteno 74718×

Algoritmy

Implementace algoritmů pro práci s kolekcemi jsou shromážděny ve třídě Collections převážně jako statické metody. Jsou obecně navrženy tak, aby bez ohledu na implementaci kontejneru zajišťovaly minimální operační složitost (i za cenu vyšší spotřeby paměti).

Seřazení seznamu

Máme nějaký obecný seznam (tj. nějakou implementaci rozhraní List) a potřebujeme ho seřadit. K tomuto účelu máme k dispozici dvě statické metody sort(), jedna řadí pouze porovnatelné prvky, druhá jakékoli - s tím, že poskytneme nějaký komparátor. Obě používají upravený algoritmus mergesort, řazení probíhá v čase n.log(n) a je stabilní. Podívejme se, jak to vypadá:

List list = new ArrayList();  // vytvoření seznamu
...                           // naplnění atd.
Collections.sort(list);       // seřazení

Promíchání seznamu

Opakem seřazení je náhodné zamíchání seznamu. I to se může občas hodit (a to nejen v případě, že chceme přehrávat písničky v náhodném pořadí). I zde jsou metody dvě (shuffle()), jedna používá standardní, druhá uživatelský generátor náhodných čísel. Pracují v lineárním čase.

List list = new LinkedList(); // vytvoření seznamu
...                           // naplnění atd.
Collections.shuffle(list);    // promíchání

Obrácení pořadí

Opět velmi jednoduchá, avšak užitečná činnost. Poskytuje ji metoda reverse(), pracující opět v lineárním čase.

Hledání binárním dělením

Podobně jako u polí, i u seřazených seznamů může s úspěchem použít hledání binárním dělením. Pro seznamy s možností náhodného přístupu (tj. implementující rozhraní RandomAccess) pracuje v čase log(n), pro ostatní bude čas řádově lineární.

List list = new ArrayList(); // vytvoření seznamu
list.add("abc");             // vložíme prvky
list.add("efg");
list.add("cde");
Collections.sort(list);      // seřazení
System.out.print("Hledaný řetězec má pozici ");
System.out.println(Collections.binarySearch(list, "efg")); // vypíše "2"

Plnění seznamu

Opět zjevná analogie s poli, co k tomu říci více...

List list = new ArrayList(); // vytvoření seznamu
list.addAll(Collections.nCopies(100, new Double(3.3))); // první naplnění
Collections.fill(list, new Double(5.0)); // další naplnění

Kopírování seznamu

Zkopírovat seznam lze v zásadě třemi cestami. Jednou je vytvoření úplně nového seznamu pomocí "kopírovacího" konstruktoru (v uvozovkách proto, že zde nejde o skutečný kopírovací konstruktor). Tím se vytvoří nový seznam obsahující prvky toho původního (resp. obecněji, prvky libovolné kolekce implementující rozhraní Collection).

List list1 = new ArrayList();        // vytvoření prvního seznamu
...                                  // nějaké operace
List list2 = new LinkedList(list1);  // nový seznam obsahuje všechny prvky původního

Druhou možností je volání statické metody copy() s obdobným efektem jako u polí, tedy se zkopírováním jen určitých prvků (aniž by ostatní byly dotčeny). Nový seznam musí být vytvořen předem. Pozor, jako první argument se uvádí cílový seznam, zdrojový až jako druhý.

List list1 = new ArrayList();        // vytvoření prvního seznamu
...                                  // nějaké operace
List list2 = new LinkedList();       // vytvoření druhého seznamu
Collections.copy(list2, list1);      // kopírujeme

Třetí způsob není v podstatě skutečné kopírování, vytváří totiž pouze pohled na tentýž seznam (při modifikaci se mění data v nové i v původním seznamu). Používáme metodu subList(), kterou získáme seznam stejného typu, jako byl ten původní.

List list1 = new ArrayList();        // vytvoření prvního seznamu
...                                  // nějaké operace
List list2 = list1.subList(0, 10);   // získání podseznamu
list2.set(0, list2.get(1)); // zkopíruje prvek z pozice 1 na pozici 0 (v obou seznamech!)

Konverze kolekcí na pole a naopak

Běžné kolekce lze převádět na normální pole dvojicí metod toArray(). Metody se liší tím, že jedna vytvoří pole s prvky typu Object, zatímco druhá pole prvků určeného typu. Více napoví příklad. Pozor - kromě určení typu je nutné vrácené pole vždy ještě přetypovat na správný typ (na to se často zapomíná)! Navíc je chování ovlivněno tím, jaké pole se metodě předá - pokud je alespoň stejně velké jaké daná kolekce, naplní se prvky (případné přebytečné pozice se nastaví na null), v opačném případě se vytvoří úplně nové pole.

List list = new ArrayList();   // vytvoření seznamu
Object oa[] = list.toArray();  // převedení na pole objektů
String sa[] = (String[]) list.toArray(new String[0]); // převedení na pole řetězců

Opačným případem je vytvoření seznamu (nebo jiné kolekce) z pole. K tomu slouží statická metoda asList() ze známé třídy Arrays. Ta vytvoří nový seznam, který je ovšem jen vnějším rozhraním k původnímu poli - je tedy neměnný. Pokud chceme vytvořit modifikovatelný seznam nebo nějakou jinou kolekci, musíme vytvořený seznam předat konstruktoru nového kontejneru.

String sa[] = new String[10];   // vytvoření pole
...                             // naplnění apod.
List list = Arrays.asList(sa);  // vytvoření neměnného seznamu nad polem

list.add("bbbb");               // nelze - způsobí výjimku UnsupportedOperationException

list = new List(list);          // zkopírujeme seznam
list.add("bbbb");               // tohle už lze

Zjišťování informací o prvcích

Ve třídě Collections existuje skupina statických metod, zabývajících se zjišťováním různých informací o prvcích obsažených v kontejnerech. O nich si povíme jen stručně.

Máme zde metody min() a max(), každou ve dvou variantách (bez uvedení komparátoru a s ním). Již z jejich názvu vyplývá, že budou zjišťovat největší a nejmenší prvek. Ovšem pozor na to, že pro prázdné kolekce vyhodí výjimku NoSuchElementException!

Set set = new HashSet();
...
System.out.println("Minimum: " + Collections.min(set));
System.out.println("Maximum: " + Collections.max(set));

Dvojice metod indexOfSubList() a lastIndexOfSubList() zjišťuje první, resp. poslední místo výskytu podseznamu v seznamu. Pokud žádný podseznam nenajde, vrátí -1.

Ostatní algoritmy

Seznam můžeme "zrotovat" o určitý počet pozic. Použijeme k tomu metodu rotate(). Dále lze prohodit dva prvky v seznamu metodou swap() nebo pomocí replaceAll() nahradit všechny výskytu určitého prvku. K dalším algoritmům se dostaneme za chvíli, jsou totiž k dispozici až od JDK 1.5.

Novinky v kontejnerech od Javy 5.0

Java 5.0 (tedy JDK 1.5) přináší dost podstatné změny v rozhraní i implementaci kolekcí. Byly tak vyslyšeny časté stížnosti některých programátorů na napříliš bezpečný způsob práce s kolekcemi, na složité používání primitivních typů a další problémy. Současně přibyly některé funkce, které usnadňují práci s kontejnery. Podívejme se tedy blíže...

Typová bezpečnost

Programátoři v C++ jsou zvyklí, že pokud potřebují nějaký kontejner, vytvoří si instanci příslušné šablony s takovým typem, kterého jsou vkládané hodnoty. Pro takovou práci dříve javovské kolekce neposkytovaly žádnou podporu, do kontejneru bylo možné vkládat prakticky cokoliv a pokud někdo vyžadoval typovou bezpečnost, musel si vše ošetřit sám. Nová verze Javy ale přináší podstatnou změnu.

Nyní lze vytvořit typově určený kontejner, čímž máme zaručeno, že prvky v něm obsažené budou konkrétního typu. Pokus o porušení typové kontroly bude ohlášen již během kompilace. Podmínkou ale je, aby byl kontejner nejen vytvořen jako typový (tj. při volání konstruktoru), ale musí tak být deklarována příslušná proměnná. Kolekce bez typové kontroly lze nadále používat, kompilátor však bude vypisovat varování.

// starý způsob - chceme pracovat jen s celými čísly
List list = new ArrayList();  // seznam bez určení typu
list.add(new Integer(5));     // vložíme číslo...
list.add("");                 // ...ale klidně i něco jiného

// nový způsob
List<Integer> list = new ArrayList<Integer>(); // seznam celých čísel
list.add(new Integer(5));     // vložíme číslo...
list.add("");                 // ...a tohle by kompilátor nedovolil

Uvedený způsob typové kontroly má jednu nevýhodu - je statický, takže lze použít jen tam, kde typ známe předem. V řadě případů je tomu však jinak, proto musíme použít dynamickou typovou kontrolu. Máme k dispozici wrappery na generování typově bezpečných kolekcí, které se používají podobně jako jiné wrappery (viz minulý díl). Při pokusu o porušení ochrany je vyvolána výjimka ClassCastException.

// vytváření seznamu - použijeme wrapper
List<Integer> list = Collections.checkedList(new ArrayList<Integer>(), Integer.class);
ForeignObj obj = new ForeignObj();
obj.setList(list) // nyní se seznam někam předá...

// ...a tam to může vypadat třeba takto:
public class ForeignObj {
  ...
  public void setList(List lst) {
    lst.add(new Integer(5)); // tohle je v pořádku
    lst.add("abc");          // tohle v pořádku není a způsobí to ClassCastException
  }
}

Přímá práce s primitivními typy

Komplikací při práci s primitivními typy (int, byte apod.) byla nutnost vytvářet zapouzdřující objekty při vkládání do kolekce. To už nyní není nutné. Objekty se sice stále vytváření, ale programátor může jako argumenty používat přímo příslušné primitivní typy (kontroverzní, nečisté řešení - ale ulehčuje práci). Typové kontejnery je ovšem nutné deklarovat s uvedením zapouzdřující třídy.

List<Double> list = new ArrayList<Double>(); // seznam celých čísel
list.add(new Double(2.75));  // starý způsob
list.add(2.75);              // nový způsob

Speciální cykly pro snadnou iteraci

Při sekvenčním přístupu k prvkům přes iterátor jsme museli napsat poměrně hodně kódu, který se při každém takovém použití opakoval. Proto vznikla (opět podle mého názoru nepříliš čistá) berlička, spočívající v "rozšířeném" (resp. speciálním) cyklu for. Tento speciální cyklus řeší syntakticky to, co se dosud provádělo ručně. Posuďte sami:

List<String> list = new ArrayList<String>();

// původní způsob (klasický cyklus)
for (Iterator<String> i = list.iterator(); i.hasNext(); ) {
  System.out.println(i.next());
}

// nový způsob (rozšířený cyklus for)
for (String s : list) {
  System.out.println(s);
}

Fronty

Často používanými strukturami jsou fronty, proto se dostaly i do CF. Máme zde nová rozhraní - Queue (obecná fronta, rozšíření rozhraní Collection o operace typické pro frontu) a BlockingQueue (potomek Queue, přidává blokující operace). BlockingQueue (a její implementace, viz dále) je součástí balíku java.util.concurrent, o kterém bude řeč někdy později - na tuto dobu bych také přenechal další detaily ohledně front, bude to (z hlediska souvislostí) vhodnější. Nyní tedy jen řeknu, že jednou z implementací front je i spojový seznam - LinkedList.

Kolekce "téměř jen ke čtení"

V řadě případů kolekci někdy na počátku vytvoříme a pak už se nemění buď vůbec, nebo jen zřídka. Pro takové situace se hodí implementace, která zajišťuje maximální rychlost při operacích čtení, bez ohledu na rychlost manipulačních operací. V Javě 5.0 tuto skupinu reprezentují třídy CopyOnWriteArrayList a CopyOnWriteArraySet (obě z balíku java.util.concurrent). Při přístupu k prvkům pracují velmi rychle, modifikace způsobí zkopírování celého kontejneru (je to podobné jako u tzv. konstantních databází), což je sice pomalé, ale tady to nevadí. Výhodou je, že se vůbec nemusíme starat o synchronizaci, problémy se současným přístupem nejsou.

Nové algoritmy

Ve třídě Collections přibylo několik statických metod, poskytujících poměrně příjemné funkce:

• frequency() - zjistí četnost výskytu určitého prvku v kolekci
• disjoint() - zjistí, zda jsou dané kolekce disjunktní (nemají společné prvky)
• addAll() - přidá do kolekce všechny prvky pole
• reverseOrder() - vytvoří komparátor, který funguje přesně obráceně (zajišťuje obrácené uspořádání) než ten původní

Možná toho bylo o kolekcích až příliš, ale doufám, že to nevadí. Příště se vrátíme až na úplný začátek a povíme si zase něco o psaní programů, kompilaci, spouštění apod. Od doby, kdy seriál začal (tj. od loňského léta) se totiž leccos změnilo, současně tím ale budu reagovat i na reakce čtenářů, že by rádi do těchto věcí pronikli hlouběji

Verze pro tisk

DISKUZE Pochvala 26.4.2005 17:07 Petr Zajíc Plnění seznamu 20.7.2006 13:43 Martin Landa Re: Plnění seznamu 20.7.2006 14:10 Martin Landa Novinky v kontejnerech od Javy 5.0 21.7.2006 14:06 Martin Landa Speciální cykly pro snadnou iteraci 21.7.2006 15:22 Martin Landa Zobrazit označené Zobrazit vše Příspívat do diskuze mohou pouze registrovaní uživatelé.