Spare arrays

Oct 08 2015

Sorry, this entry is only available in Czech. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.

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.

Zatím žádná reakce

Vítám tvoje reakce