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 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:
Co zvážit o rozložení (ne)nulových prvků:
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.
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.
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.
Nový komentář