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

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ů

18.6.2018 0:43 /František Kučera
Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.
Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

13.2.2018 0:41 /František Kučera
Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář

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

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

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