Porovnání hashovacích strategií

Budeme pracovat se dvěma hashovacími tabulkami, obě tabulky budou mít stejnou délku a do obou uložime celou danou množinu klíčů. Tabulky se budou navzájem lišit použitou hashovací strategií. První tabulka bude používat strategii Linear Probing, druhá bude používat strategii Double Hashing.

Pro účely této ulohy budeme považovat za kolizi každou situaci, kdy máme vypočtenou možnou pozici vkládaného klíče a přitom je tato pozice v tabulce obsazena jiným klíčem. Během procesu vkládání jednoho klíče tedy může nastat více kolizí, resp. kolize nastávají tak dlouho, dokud v tabulce není nalezena volná pozice pro vkládaný klíč.

Klíči, ukládanými do tabulek, budou řetězce. Každý řetězec může obsahovat pouze znaky z množiny 26 znaků {'a', 'b', ... 'z'}. Každému znaku x je přiřazena jeho ASCII numerická hodnota anv(x) takto: anv('a') = 97, anv('b') = 98, ..., anv('z') = 122.

Množina klíčů K, které budeme vkládat do tabulek, je určena takto: Na vstupu je M (M > 0) množin znaků, označme je Z₁, Z₂, ..., Z_M, všechny mají stejnou mohutnost D > 0. Prvkem množiny K bude každý neprázdný řetězec s = s₁s₂...s_k (k ≤ M), pro jehož znaky platí
1 ≤ j ≤ k ⇒ s_j ∈ Z_j.
Každý klíč budeme vkládat do tabulky právě jednou.

Pro klíč s = s₁s₂...s_k zavedeme hashovací funkce následujícím způsobem:
Hashovací funkce h₁ pro první tabulku je dána předpisem
h₁(s) = (f₁(s ) + i×F) mod L,       kde f₁(s) = ∑_j=1..k anv(s_j)×p₁^k−j,
L je velikost tabulky, i, p₁, F jsou celá nezáporná čísla. Hodnota i probíhá postupně čísla 0, 1, 2, ... až do okamžiku, kdy h₁(s) je indexem některého volného prvku tabulky. Pokud tedy tento okamžik nastane pro určité i₀, bude to znamenat, že během generování hodnoty h₁(s) nastalo právě i₀ kolizí.

Hashovací funkce h₂ pro druhou tabulku je dána předpisem
h₂(s) = (f₁(s ) + i×f₂(s)) mod L,       kde f₂(s) = 1 + ( ∑_j=1..k anv(s_j)×p₂^k−j) mod L₂,
p₂, L₂ jsou celá kladná čísla a význam ostatních symbolů je analogický jako v definici h₁.

Úloha
Pro dané parametry tabulek a pro danou množinu klíčů K máme určit průměrný počet kolizí, který nastal při vložení jednoho prvku do každé tabulky. Klíče do každé tabulky budeme vkládat v abecedním pořadí.

Vstup

Na vstupu je více textových řádků. První řádek obsahuje tři celá kladná čísla navzájem oddělená mezerou L, M, D. Číslo L představuje velikost obou tabulek, tj. každá tabulka obsahuje prvky s indexy 0, 1, ..., L−1.
Každý z dalších M řádků obsahuje řetězec délky D, který obsahuje neopakující se znaky z množiny {'a', 'b', ... 'z'} uspořádané ve vzestupném abecedním pořadí a představuje množinu Z_i (1 ≤ i ≤ M) definovanou v textu.
Poslední řádek na vstupu obsahuje čtyři celá kladná čísla navzájem oddělená mezerou F, p₁, p₂, L₂, která jsou definována v textu.
O vstupních hodnotách platí: L je prvočíslo nepřesahující 10⁷, množina K má nejvýše 9×10⁶ prvků, jejichž délka nepřesáhne 26, |K| ≤ L. Hodnoty F, p₁, p₂, L₂ nepřesáhnou 10⁷.

Výstup

Výstup obsahuje jediný textový řádek se dvěma desetinnými čísly V₁, V₂ oddělenými mezerou. Obě čísla obsahují povinně tři desetinné číslice. V₁ představuje podíl celkového počtu kolizí, které nastaly při vkládání řetězců do první tabulky, a celkového počtu klíčů v tabulce. Analogicky V₂ představuje podíl celkového počtu kolizí, které nastaly při vkládání řetězců do druhé tabulky, a celkového počtu klíčů v tabulce.
V daných datech lze očekávat, že průměrný počet kolizí na jeden prvek nepřesáhne 35.

Příklad 1

Vstup:

7 2 2
ab
cd
5 3 4 5

Výstup:

0.167 0.167

Příklad 2

Vstup:

7 2 2
ab
cd
5 1 2 5

Výstup:

0.500 1.000

Příklad 3

Vstup:

9999511 7 9
fiklnpruv
efgkloruz
cefijluyz
ajklpsvyz
ceghimnru
egiklmntv
acjklpstv
289573 33 1399 5672

Výstup:

0.574 0.474

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data