Řídká pole
Spare Array (česky řídké pole) je jednorozměrná datová struktura, která slouží k uložení pole dat. Analogickou vícerozměrnou datovou strukturou je řídká mřížka. Podstatou této struktury je, že v poli je uloženo velké množství prvků jedné stejné hodnoty. Typicky je v poli uloženo velké množství hodnot 0 nebo null. Proto budu nadále dělit prvky v poli na nulové a nenulové.
Implementace
Implementace takového pole se mohou velmi lišit v závislosti na požadovaný operacích a na předpokladech o rozložení nenulových prvků. Klíčovými parametry je samozřejmě efektivita vybraných operací nad takovým polem. Základní operace s polem:
- přístup na n-tý prvek (čtení/zápis)
- sekvenční průchod (enumerace)
- vložení/odebrání prvků
- přidání prvku nakonec
- nalezení prvku (indexOf)
- existence prvku v poli
Co zvážit o rozložení (ne)nulových prvků:
- rozložení je zcela náhodné
- nulové nebo nenulové prvky se vyskytují v blocích
- nenulové prvky jsou velmi izolované
Hash tabulka
Jednou z velmi častých implementací řídkého pole je použití hashovací tabulky. Tato implementace ukládá pouze nenulové prvky. Klíčem tabulky je pozice prvků. Hodí se pro velmi izolované nenulové prvky a přístup pomocí indexu.
Spojový seznam (Linked list)
Pro sekvenční přístup se hodí implementace řídkého pole pomocí sojového seznamu, kde každý prvek obsahuje index a hodnotu. Při implementaci spojovým seznamem je jednoduché i přidání prvku nakonec – stačí si udržovat ukazatel na poslední prvek.
Spojový seznam bloků
Tato implementace vychází z předpokladu, že nenulové prvky se vyskytují ve víceméně souvislých blocích, kterých navíc není mnoho. Každý blok udržuje svůj počáteční index a normální (neřídké) pole prvků. Třída pak řeší růst/slučování a dělení bloků. Pro nalezení n-tého prvku je třeba najít příslušný blok a potom už se jedná o přímý přístup do pole. Pro enumeraci prvků postupně procházíme všechny prvky. Mimo jiných je výhoda této implementace v relativně rychlých operacích insert a remove, protože pro posunutí všech prvků bloku stačí změnit počáteční index bloku. Další výhodou je fakt, že pokud naše řídké pole degeneruje na téměř normální pole, tato implementace se tomu přizpůsobí a prvky uloží v jediném bloku, a tedy defakto jako jednoduché pole.