5.5 Modul Star

Stručný popis

Modul Star uchovává kapky ve vnitřní datové struktuře. Požadavky na tuto strukturu jsou: rychlé vyhledávání blízkých kapek, možnost projít všechny kapky. Dále potřebujeme do struktury přidávat nové a ubírat staré kapky. Na druhou stranu můžeme slíbit, že přidávání a ubírání bude probíhat najednou (v kvantech). Jinými slovy budou se střídat dvě fáze. První: časté vyhledávání. A druhá: mazání a přidávání. To odpovídá tomu, že simulace probíhá diskrétně.

Prostor je rozdělen na 2 ⁴⁸ pomyslných buněk. Buňka je vlastně malá krychlička, která případně obsahuje kapky. Každá buňka má své vlastní číslo, které koresponduje s jejím umístěním v prostoru. Číslo je rozděleno na významnější (hi) a méně významnou část (lo). Významná část má 32 bitů, méně významná 16.

Popis datových struktur

Základem je pole st_hvezdy, ve kterém jsou informace o kapkách (trochu zavádějící název zůstal ze starších verzí). Tj. poloha, rychlost a různé další, které využívá převážně modul Move.

Nad tímto polem je ona vnitřní struktura, tvořena polemi st_bunky_ht hašovací tabulka buněk, st_bunky pole obsazených buněk, st_hvezdy_idx prvky buněk.

Dejme tomu, že máme najít kapku, která patří do buňky s číslem B. Méně významnou část čísla B nazveme lo, více významnou pak hi.

st_bunky_ht hashtable buněk, na místě st_bunky_ht[lo] se nalézá index do pole st_bunky, jde o první buňku s tímto lo. Zatímco st_bunky_ht[lo+1] je index na první buňku, která má již jiné lo. Mezi těmito dvěma čísly se nacházejí všechny buňky s hledaným lo.

st_bunky bloky buněk se stejným lo. Jak jsou tyto bloky určeny je patrné z předcházejícího odstavce. V bloku jsou buňky uspořádány dle hodnoty hi. Hledaná buňka se najde poměrně snadno půlením intervalu. V buňce jsou kromě informace o hodnotě hi tyto informace: fst první hvězda této buňky (odkaz do pole st_hvezdy_idx), len jejich počet.

st_hvezdy_idx bloky indexu do pole st_hvezdy, v každém bloku jsou hvězdy ze stejné buňky. Jak jsou určeny počátky a délky těchto bloků, je opět jasné z předchozího odstavce.

Z výše uvedeného je zároveň i vidět, jak se v takové struktuře vyhledávají blízké kapky: prostě prohledáme blízké buňky. Čísla hledaných buněk jsou snadno spočítatelná z jejich souřadnic.

Konstrukce datové struktury

První průchodem pole st_hvezdy zjistíme počty kapek se stejnými lo. Tyto hodnoty jsou dočasně uchovány v poli st_bunky_ht.

Poté průchodem pole st_bunky_ht připravíme bloky v st_bunky. Pro každou, kapku zde bude zatím připravena jedna buňka.

Druhým průchodem st_hvezdy zaplníme pole st_bunky.

Následuje komprese a setřídění v každém z bloků buněk. Bloky buněk budou setřízeny dle hodnoty hi. Komprese spočívá v tom, že buňky se stejnou hodnotou hi budou spojeny v jednu.

Posledním průchodem st_hvezdy konečně zařadíme hvězdy do buněk. A to tak, že vyplníme bloky pole st_hvezdy_idx indexy příslušných kapek.

Časová složitost

Označíme h_siz počet kapek, rozsah hodnot lo označíme lo_max. ro maximální počet kapek na buňku ro. Z výše uvedeného je vidět, že časová složitost vybudování struktury je O(h_siz + lo_max).

Časová složitost vyhledávání buňky je pak O(ln(kol)), kde kol je maximální počet kolizí v st_hvezdy_ht.

Tyto úvahy však vedou k zamyšlení, zda má smysl počítat asymptotickou složitost datové struktůry, jejíž velikost je omezena konstantou (viz následující odstavec).

Paměťová náročnost

Velikost této struktury záleží poněkud netriviálním způsobem na maximálním počtu kapek (h_siz).

V ``malé'' variantě je počet kapek omezen číslem 65535(= 2^16 - 1).

Ve ``velké'' variantě je počet kapek v podstatě neomezen (přesněji: omezen číslem 2^32). V hranatých závorkách je uváděna hodnota pro velkou variantu.

Počet položek pole st_bunky_ht je vždy 64k. Každá položka (index do pole st_bunky) má velikost 2B [4B].

Počet položek pole st_bunky_ht je h_siz. Velikost položek hi 4B [4B], fst index do st_hvezdy_idx 2B [4B], len délka bloku 2B [4B], celkem tedy 8B [12B].

Počet položek pole st_index je také h_siz. Položky mají velikost 2B [4B].

Celkově je tedy v malé variantě potřeba (horní odhad) 12 * 64kB = 768kB.

Kódování čísla buňky

Kódování polohy prostoru do čísla buňky je voleno tak, aby blízké buňky měly rozdílné číslo.

lo

 y5 y4 y3 y2 y1 y0 z4 z3 z2 z1 z0 x4 x3 x2 x1 x0
`--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--'
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

hi

 y15 ...  y6 z15 ...  z5 x15 ...  x5
`---+---+---+---+---+---+---+---+---'
 31  ...  22  21 ...  11  10 ...   0

Interface modulu

st_init()

Inicializace polí st_hvezdy, st_hvezdy_idx, st_bunky_ht,

t_star *st_hvezda_alloc()

Alokace nové hvězdy v poli st_hvezdy.

hvezda->flag &= ~ST_FLAG_IN

Zneplatnění hvězdy. Po zavolaní st_pack() bude hvězda uvolněna.

void st_pack()

modul Star vymaže všechny označené hvězdy a přejde do ``přidávacího'' stavu. Tj. mohou se přidávat nové kapky.

void st_build()

Vystavěné struktury. Od této chvíle se bude pouze vyhledávat.

t_long_bid vec2bid(t_vec v)

t_long_bid bid2vec(t_bid b)

t_long_bid bid2lbid(t_bid b)

Funkce na převod mezi identifikací, bodem prostoru a číslem buliňky, do které patří.