Na jednu prezentaci jsem relativně nedávno připravoval poměrně pěkný slajd, kde je přehledně popsáno, jak rychlé jsou jednotlivé vestavěné kolekce v .NET Frameworku.
| | Přidání na konec | Odebrá-ní z konce | Vložení dovnitř | Odebrá-ní zevnitř | Přístup podle indexu | Sekven-ční přístup | Vyhle-dání | Poznámky |
| Array | O(n) | O(n) | O(n) | O(n) | O(1) | O(1) | O(n) | Nejefektivnější využití paměti; vhodné v případě neměnného počtu položek. |
| List | většinou O(1); nejhůře O(n) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | Vnitřně implementováno pomocí pole, při zaplnění se 2x zvětší. Přidávání nebo odebírání z prostředka či začátku jsou pomalé. |
| LinkedList | O(1) | O(1) | O(1) | O(1) | O(n) | O(1) | O(n) | Obousměrný spojový seznam. Pomalé přístupy doprostřed, rychlé přidávání na začátek a na konec. |
| Stack | většinou O(1); nejhůře O(n) | O(1) | N/A | N/A | N/A | N/A | N/A | Zásobník, vhodné pro implementaci různých algoritmů. Last in, first out. |
| Queue | většinou O(1); nejhůře O(n) | O(1) | N/A | N/A | N/A | N/A | N/A | Fronta, vhodná pro implementaci různých algoritmů. First in, first out. |
| Dictionary | většinou O(1); nejhůře O(n) | O(1) | většinou O(1); nejhůře O(n) | O(1) | O(1)* | O(1)* | O(1) | Vnitřně implementováno pomocí hashovací tabulky, vhodné pro rychlé vyhledávání podle klíče. |
Tato tabulka je převzatá z dokumentu o rychlosti kolekcí, který jsem našel na webu http://creators.xna.com. Trochu jsem ji doplnil a přeložil, protože se mě na složitost operací ptalo v poslední době docela dost lidí.
Pokud je v buňce uvedena složitost O(1), znamená to, že operace má konstantní časovou složitost, to znamená, že to, jak dlouho bude operace trvat, záleží na nějaké konstantě a ne na počtu položek. Zjednodušeně řečeno nalezení položky ve slovníku (Dictionary) bude trvat stejně dlouho, ať bude ve slovníku deset či milion položek.
Pokud je v buňce složitost O(N), znamená to, že operace má lineární časovou složitost, což je dáno tím, že v nejhorším případě musíme projít všechny prvky kolekce (což u kolekcí s miliony prvků může trvat docela dlouho).
Array
Nejhůře je na tom pole, přesto jej ale používáme velmi často. Pokud předem víme, kolik budeme potřebovat položek, nevadí nám omezení přidávání a odebírání položek z kolekce. Pole je nejefektivnější, pokud jde o množství paměti, ze své postaty je v něm rychlý přístup na položku s daným indexem.
Jakékoliv zvětšování či zmenšování existujícího pole není možné, musí se to řešit vytvořením nového pole a zkopírováním obsahu. Vyhledání položky v poli podle její hodnoty je samozřejmě pomalé, protože v nejhorším případě bude ta hledaná položka až na konci a projdeme tedy celé pole.
List
Do této kategorie patří samozřejmě generický List a jeho předchůdce ArrayList, který však nedoporučuji používat, protože pracuje s datovým typem object a nemáte pořádnou typovou kontrolu. Vnitřně tyto seznamy fungují jednoduše - mají v sobě pole určité velikosti, do kterého sází položky. Jakmile se pole zaplní, vytvoří nové 2x větší a položky do něj přesunou.
Přístup k položkám podle indexu i sekvenční přístup je velmi rychlý, problém je s přidáváním doprostřed nebo na začátek, protože se musí položky za danou pozicí odsunout, aby se vytvořilo místo. To samé platí pro odebírání z prostřed. Přidávání na konec je většinou rychlé, ale problém může nastat, pokud se vnitřní pole zaplní a je nutné jej zvětšit.
LinkedList
Do této kategorie patří datová struktura LinkedList, jedná se o obousměrně zřetězený seznam. Položky jsou rozházené náhodně po paměti (kde bylo zrovna místo), netvoří tedy souvislý blok, a drží si reference (adresy v paměti) na předchozí a následující prvek. Přidávání a odebírání je rychlé, pokud máte prvek, za který se bude přidávat, resp. který se bude odebírat, přidání či odebrání je totiž otázkou změny pár odkazů na předchozí a následující prvek. Sekvenční přístup je také v pohodě, struktura zná svůj první prvek a každá položka zná svého následovníka, pokud tedy chcete prvky projít popořadě, je to rychlé. Problém je s přístupy pomocí indexu, když chcete padesátý prvek, musí se prostě odpočítat, což zabere 50 kroků. Navíc tato struktura má dost velkou paměťovou režii.
Stack a Queue
Zásobník a fronta jsou dvě datové struktury, které mají dosti specifické použití. Zásobník (Stack) má operace push (přidej prvek) a pop (odeber prvek), přičemž prvky se přidávají na konec a odebírají také z konce. Je to něco jako trička ve skříni - každý den si vezmete to, které je nahoře, a když se nějaké vypere, přidá se také nahoru. Protože pořád odebíráte z vrchu, může se klidně stát, že se k těm spodním ani nedostanete. Poslední položka, která se přidala, se odebere jako první.
Fronta (Queue) je obyčejná fronta, třeba fronta na banány - lidi odcházejí zepředu, když jsou u pultu obslouženi, a nově příchozí se řadí na konec. Ten, co přišel první, z fronty také jako první odchází.
Dictionary
Slovník (Dictionary) je speciální datová struktura, která neobsahuje jen hodnoty, ale i jejich klíče. Klíčem může být cokoliv, například řetězec. Slovníky fungují většinou na principu hashovací tabulky - z každého klíče se spočítá tzv. hash, což je hodnota, která by měla splňovat dvě podmínky - stejné hodnoty musí vždy dávat stejný hash a hodnoty hashů by měly být rovnoměrně rozprostřeny v daném rozsahu. V .NETu je hash číslo a každý objekt má metodu GetHashCode, která jej spočítá.
Pokud tedy do hashovací tabulky chceme uložit dvojice klíč hodnota např. { jablko = apple }, { hruška = pear } a { pomeranč = orange }, z klíčů se spočítají hashe. Tabulka má velikost řekněme 17 prvků, slovo jablko má třeba hash 346. Když se má položka uložit do tabulky, její hash se vydělí velikostí tabulky a spočítá se zbytek po tomto dělení, což je 6. Položka se tedy uloží do vnitřního pole na pozici 6 (uloží se tam i s klíčem). Když chceme přidat hrušku, která má hash řekněme 13783, zbytek po dělení dá 14, tedy hruška se uloží na pozici 14. Pomeranč má hash 584, což po vydělení 17 dá zbytek 6, jenže na pozici 6 už máme jablko. Této situaci se říká kolize.
Kolize se dají řešit vícero způsoby - položka se buď uloží na následující volné místo, nebo na každé pozici v poli máme ještě položku, která bude obsahovat odkaz na následující prvek se stejným hashem (takže víceméně v každé položce pole je jakoby spojový seznam).
Pokud je zaplnění tabulky řekněme do 50 - 70%, kolize téměř nenastávají; záleží také samozřejmě na tom, jak dobře je zvolená hashovací funkce, pokud je kvalitní, tak se položky krásně rozprostřou do tabulky a kolizí bude méně. Jakmile se tabulka hodně zaplní, musí se zvětšit a položky se přesunou.
Proč je kolem toho tak složitá maškaráda? V hashovacích tabulkách se dá velmi dobře vyhledávat podle klíčů - víceméně s konstantní složitostí. Pokud umíme spočítat hash z klíče, což umíme, a pokud ze stejných klíčů spočítáme vždy stejný hash, což je podmínka, pak místo, kde položka bude, najdeme bez ohledu na to, kolik položek máme.
Jako hashovací tabulka funguje v .NETu generická třída Dictionary, případně starší HashTable. Výhodou je, že to, jakým způsobem se počítá hash, můžeme do jisté míry ovlivnit tak, že naimplementujeme rozhraní IEqualityComparer. Pokud bychom například chtěli jako klíč použít vlastní strukturu reprezentující třeba racionální číslo (struktura by dejme tomu obsahovala čitatel a jmenovatel), chceme, aby položky 3/6 a 1/2 dávaly stejný hash, protože je to víceméně ten samý zlomek. Jiným a asi nejčastějším příkladem použití může být například potřeba indexovat položky klíčem a nebrat ohled na velikost písmen.
Závěrem
Doufám, že se mi tímto kratičkým článečkem podařilo objasnit, jak to s těmi kolekcemi je. Rozhodně jsem se nesnažil o žádné formální definice, šlo mi o to, aby to pochopil každý. V .NETu máme samozřejmě ještě další datové struktury, jako třeba SortedList a SortedDictionary, ale ty se zase až tak často nepoužívají, takže jsem je do tabulky nezařazoval.