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 74842×
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
|
Příspívat do diskuze mohou pouze registrovaní uživatelé.
|
|

Vyhledávání software

Vyhledávání článků
28.11.2018 23:56 /František Kučera Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz 22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz 20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
Více ...
Přidat zprávičku
 Poslední diskuze
31.7.2023 14:13 /
Linda Graham iPhone Services
30.11.2022 9:32 /
Kyle McDermott Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš Re: zavináč
2.12.2018 23:56 /
František Kučera Sraz
5.10.2018 17:12 /
Jakub Kuljovsky Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?
Více ...
|