Uppgift 4 - PK3 VT-03

Uppgift 4 måste lämnas in senast tisdag 27/5 kl. 24:00. Lämna in den med hjälp av inlämningssystemet i slutet av denna sida. Se till att läsa igenom kodkonventionerna innan du börjar. Dessa skall följas.

Efter denna uppgift ska du kunna

• Undersöka fördelningen i en hashtabell givet en hashfunktion.

Före uppgiften

• Läs igenom hela uppgiften.
• Läs igenom föreläsningsmaterialet rörande hashing (dina egna anteckningar och Pierres slides).
• För programmeringsuppgifter, skriv dokumentation, dvs skriv med ord vad funktioner ska göra och hur de ska göra det, samt specifikation för funktioner och eventuella hjälpfunktioner. Endast den sistnämnda måste (och förväntas) inkluderas i din redovisning och ska följa kodkonventionerna. Se detta steg som en hjälp i att lösa uppgiften på bästa sätt. Att hoppa över förarbetet bidrar oftast med merjobb i efterhand.

Din inlämning

Överst i din fil ska följande finnas (inom kommentartecken):

• Ditt namn och klass
• Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså)
• En kort beskrivning (en rad) av vad det är för fil

Se till att du hunnit ge ett svar på varje deluppgift.

Uppgift

Filen hash.sml innehåller bla 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. 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.

1. Ladda filen hash.sml till ditt konto och öppna den i en texteditor (förslagsvis i emacs).
    
    
2. 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. Funktionen makeBin 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.
    
     

3. För att de tre hashfunktionerna ska fungera så måste du initiera slumtalsgenerator 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));.
    
    
4. Implementera en testfunktion testHash:(string -> word) -> string -> int -> string -> unit som visar hur väl hashfunktionerna fördelar givet data. Det "första" argumentet till testHash ska vara en hashfunktion (här således simpleHash, knuthHash eller hash), det "andra" argumentet ska vara namnet på filen i vilken datat som ska köras genom hashfunktionen finns, det "tredje" argumentet ska tala om storleken på själva hashtabellen och det "fjärde" argumentet ska ange namnet på den fil i vilken tabellen funktionen skapar ska sparas. Följande anrop testHash(knuthHash)("tusenSlumpmässigaTal.txt")(200)("knuthHash.txt"); ska skapa 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).
   OBS! Funktionsnamnet, "knutHash", som står på den första raden i filen är hämtat från testHash:s "fjärde" argument, som i exemplet är "knuthHash.txt". Men hur du lägger upp layouten på din filen fäster vi ingen större vikt på vid rättningen, så länge som n, m och α (samt själva tabellen) finns med.
   
   Förtydligande: Antag att hashFn är någon av funktionerna simpleHash, knutHash eller hash. Positionen p där strängen s ska placeras i en hashtabellen av längd n beräknas enligt följande: p=(hashFn(s) mod n). Det är kedjornas längd som fördelningen av p ger upphov till som testfunktionen testHash ska undersöka. Observera att testHash inte behöver placera in värdena från dina slumptalsfiler i en hashtabell, bara mäta fördelningen av dem.
    
    
5. 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.
    
    
6. 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). 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 URL:er till dem.
    
    
7. Skriv ner vilka slutsatser du drar av ditt experiment! Svara även på följande frågeställningar i din slutsats:
   - Vi har undersökt fördelningen av unika slumpmässiga heltal i de tre hashfunktionerna. Varför ska slumptalen vara unika?
   - Vad beror fördelningsskillnaden på mellan de två typerna av indata? (Tips: de binära slumptalen är syntaktiskt liknande varandra.)
   - Om någon säger att det är viktigt att "trimma" en hashfunktion, givet en viss fördelning, på det data som ska hashas, vad säger ni då?
    

Din redovisning ska innehålla

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

Din inlämning ska vara körbar. Dvs det som inte är kod ska vara bortkommenterat!

Inlämning

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.

* Då alla funktioner i SML endast har ett argumnet, så är det rent teoretiskt fel att prata om första och andra parametern/argumentet.