Uppgift 4 -- PK2 VT04 -- Uppsala Universitet

Uppgift

1. 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. Två datafiler av följande typer ska skapas:
   • Slumptal: Skapa en fil med 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 en fil med 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.
2. 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)).
3. Filen testHash.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. Specifikationerna av de andra funktionerna i denna fil är irrelevanta här. 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.
4. Jämför de uppmätta fördelningarna du erhållit med det teoretiska uppträdandet hos slumpmässig uniform hashning (se slide 13). 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 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.
5. 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?

1. Först i din kod ska följande rad finnas (anledningen är att underlätta rättningen): use "hash.sml";
2. Två sökvägar/URL:er till dina två filer med slumpdata (se punkt 1 ovan).
3. Din initiering av buzinit (se punkt 2 ovan).
4. Dina 24 körexempel av testHash (se punkt 3 ovan).
5. Sökväg/URL till en fil med åtta grafer med de teoretiska och de uppmätta fördelningar (se punkt 4 ovan).
6. Dina svar på punkt 5 ovan.

Inlämning

• 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.
• En kort beskrivning (en rad) av vad det är för fil.
• Alla kommentarer och all dokumentation ska vara på engelska.

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.