Uppgift 4 -- AD1 VT04 -- Uppsala Universitet
Uppgift 4 måste lämnas in senast måndag 1 mars klockan 11:59 (på
morgonen). Lämna in den med hjälp av inlämningssystemet (se
slutet av denna sida). Se till att läsa igenom kodkonventionerna
innan du börjar. Dessa skall följas.
Uppgift
Filen hash.sml innehåller bland annat tre
hashfunktioner: simpleHash: string -> word, knutHash:
string -> word, samt hash: string -> word.
Funktionen simpleHash är en mycket trivial hashfunktion,
knuthHash är en implementation av Donald Knuths hashfunktion,
och hash är en av den nya generationens hashfunktioner (av
John Hamer). Den här uppgiften går ut på att du ska undersöka hur de
tre hashfunktionerna beter sig för två olika typer av slumpdata och
jämföra det med det teoretiska uppträdandet hos slumpmässig uniform
hashning. Med hjälp av GNU-plot ska resultatet redovisas grafiskt.
- Datat som du ska köra igenom de tre hashfunktionerna ska du skapa
på egen hand. Datamängderna ska sparas i en fil där varje enskilt
slumpdata ska stå på en egen rad. Följande två filer av data ska
skapas:
- Slumptal: Skapa 1000 unika och slumpmässiga tal, med hjälp
av tex www.random.org. Var
noga med att talen är unika (för att undvika dubletter är
unix-kommandot sort -u filnamn.txt > nytt_filnamn.txt
användbart).
- Binära slumptal: Skapa 1000 unika och slumpmässiga binära
tal. Till din hjälp finns funktionen makeBin: string * string
-> unit i makeBin.sml, som
konverterar en fil med heltal till en fil med heltalens binära
representation (varje heltal ska stå på en egen rad). Det
"första" argumentet till makeBin är namnet på
filen som ska konverteras och det "andra" argumentet är
namnet på den fil som ska fyllas med den binära representationen.
För att skapa 1000 unika och slumpmässiga binära tal räcker det
således att anropa makeBin med slumptalsfilen skapad ovan
som input. Körexempel:
makeBin("tusenSlumptal.txt","tusenBinäraSlumptal.txt").
OBS! Du behöver inte redovisa hur du skapade dina två filer
med slumpdata. Däremot ska sökvägarna/URL:erna till dem bifogas i
din inlämning.
- För att de tre hashfunktionerna ska fungera så måste du initiera
slumptalsgenerator i hash.sml. Det gör du
genom att anropa funktionen buzinit: word * word ->
unit. Vilka "två" argument du anropar
buzinit med spelar ingen roll, så välj dina egna
favoriter. Här följer ett exempel på hur buzinit kan
anropas: buzinit(Word.fromInt(4711),Word.fromInt(6)).
- Filen test_hash.sml definerar en
testfunktion testHash: (string -> word) -> string ->
int -> string -> unit, som tar fram statistik över hur
väl hashfunktionerna fördelar givet data. Det "första"
argumentet till testHash är en hashfunktion (här således
simpleHash, knuthHash, eller
hash), det "andra" argumentet är namnet på
filen i vilken datat som ska köras genom hashfunktionen finns, det
"tredje" argumentet talar om storleken på själva
hashtabellen, och det "fjärde" argumentet anger namnet
på den fil i vilken tabellen funktionen skapar ska sparas.
Följande anrop
testHash(knuthHash)("tusenSlumpmässigaTal.txt")(200)("knuthHash.txt")
skapar en fil knuthHash.txt liknande denna:
# Fördelning av kedjor för knutHash.
# Data att fördela: tusenSlumpmässigaTal.txt
# n = 200; m = 1000; α = 5.0
# k v (%)
0 1.0
1 5.0
2 12.0
3 11.5
4 13.5
5 18.5
6 13.5
7 9.5
8 4.5
9 7.0
10 2.0
11 1.0
12 0.5
Teckenförklaring till filen: # anger för gnuplot att
raden är att betrakta som en kommentar, n anger hur stor
hashtabellen är (antalet celler), m anger hur många
element som finns i tabellen, och α är den så kallade
load-faktorn (m/n). På den fjärde raden i filen börjar
själva tabellen bestående av två kolumner. Kolumnen k
visar en kedja med längd k i hashtabellen, och kolumnen
v hur stor förekomst den kedjan, med längd k,
har i hashtabellen (mätt i procent).
Kör testfunktionen testHash fyra gånger för var och en av
de tre hashfunktionerna och för båda typerna av slumpdata. Låt
load-faktorn variera mellan 1 och 10 genom att ändra storleken på
hashtabellen. Bra värden på load-faktorn är 1, 2, 5 och 10.
- Jämför de uppmätta fördelningarna du erhållit med det teoretiska
uppträdandet hos slumpmässig uniform hashning (se
föreläsningsanteckningarna om hashing och rubriken "Chain
length under load"). Använd GNU-plot för att plotta de
teoretiska och de uppmätta fördelningarna (se uppgift 2 om du har glömt hur man
startar och använder GNU-plot; exp(n) ger e**n;
gamma(n+1) ger n!). Vi vill se fyra grafer, en
för respektive load-faktor, för båda typerna av indata (slumptal
respektive binära slumptal). Totalt vill vi alltså se åtta
grafer. Varje graf ska innehålla fyra kurvor. En av kurvorna ska
representerar de teoretiska värdena och de andra tre de uppmätta
värdena -- en kurva för respektive hashfunktion. Redovisa
graferna genom att lämna in sökvägar/URL:er till dem.
- Skriv ner vilka slutsatser du drar av ditt experiment! Du bör
bland annat diskutera följande: Vilka egenskaper vill man att en
bra hash-funktion ska ha? Hur kan den statistiska information som
samlats med funktionen testHash användas för att jämföra
de olika funktionerna? Hur förhåller sig de olika
hash-funktionerna till varandra?
Din redovisning ska innehålla:
- Först i din kod ska följande rad finnas (anledningen är att
underlätta rättningen): use "hash.sml";
- Två sökvägar/URL:er till dina två filer med slumpdata (se punkt 1 ovan).
- Din initiering av buzinit (se punkt 2 ovan).
- Dina 24 körexempel av testHash (se punkt 3 ovan).
- Åtta sökvägar/URL:er till åtta grafer med de teoretiska och de
uppmätta fördelningar (se punkt 4 ovan).
- Svar på punkt 5 ovan.
Inlämning
Överst i din fil ska följande finnas (inom kommentartecken):
- Ditt namn och klass.
- Om du löser uppgiften tillsammans med en annan student, ange den
andra studentens namn. I så fall ska endast en av er lämna in
en lösning, men båda ska meddela namn, klass och labpartner via
inlämningssystemet.
- Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså).
- En kort beskrivning (en rad) av vad det är för fil.
- Notera att alla kommentarer och all dokumentation ska vara på engelska.
Kontrollera att du hunnit ge svar på varje deluppgift.
Din inlämning ska vara körbar. Det som inte är kod ska vara
bortkommenterat!
Glöm inte att alla funktioner ska dokumenteras enligt kodkonventionerna.
Hämta ett formulär för att lämna in uppgiften genom att fylla i
fälten nedan.