LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> 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 70778×

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

pridej.cz

 

DISKUZE

Pochvala 26.4.2005 17:07 Petr Zajíc
Plnění seznamu 20.7.2006 13:43 Martin Landa
L 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




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

13.9.2017 8:00 /František Kučera

Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze