DD1321 HT20 (50170)
    d2
    Hoppa över till innehåll
    Översikt
    • Logga in
    • Översikt
    • Kalender
    • Inkorg
    • Hjälp
    Stäng
    • Min översikt
    • DD1321 HT20 (50170)
    • Uppgifter
    • d2
    • Startsida
    • Uppgifter
    • Sidor
    • Filer
    • Kursöversikt
    • Quiz
    • Moduler
    • Samarbeten
    • Video Recording
    • Media Gallery

    d2

    • Inlämningsdatum 13 dec 2020 av 23.59
    • Poäng 1
    • Lämnar in en filuppladdning
    • Filtyper py och txt

    Mål: Kunna använda och implementera en hashtabell. Kunna använda unittest för att testa program.

    Läs i Miller-Ranum om Hashing, och repetera Föreläsning 7

    1. Hashning med Pythons inbyggda dictionary

    Nu ska du göra en egen hashtabell med Pythons dictionary!

    Skriv en klass DictHash som använder Pythons inbyggda dictionary . Den måste ha metoderna

    • store(nyckel, data) som lagrar data som value i din dictionary, med nyckel som key.
    • x = search(nyckel) som slår upp nyckel i din dictionary.

    Dessutom får du om du vill lägga till två extra metoder:

    • Vill du kunna skriva d[nyckel] istället för d.search(nyckel)? Definiera då metoden __getitem__(self, nyckel) som anropar din search-metod.
    • Vill du kunna skriva if nyckel in d ? Definiera då metoden __contains__(self, nyckel) som returnerar True om nyckel finns i d, False annars.

    Testkör din klass  DictHash med datafilen unique_tracks.txt. Du får själv välja vad du vill ha som nyckel, t ex artist eller låtnamn. Tips: split()

    2. En egen implementation av hashtabellen

    Nu ska du även göra hashningen själv, i din nya klass Hashtabell med samma gränssnitt och funktionalitet som DictHash.

    Krav:

    1. Definiera en klass HashNode för hashtabellens noder. Noderna måste innehålla både nyckel och värde.
    2. Hashtabellen ska vara lagom stor.
    3. Du måste skriva en egen hashfunktion.
    4. Någon krockhantering måste ingå, t ex krocklistor eller probning.
    5. Du ska använda KeyError för att tala om att en nyckel inte finns.

     

    Testning

    Det kan vara en god idé att först prova med liten hashtabell för att se så att krockhanteringen fungerar.

    När du har förvissat dig om det är det läge att prova med mer data. Filen unique_tracks.txt innehåller bland annat artist och titel för en miljon låtar. Du kan hämta den via din webbläsare, men eftersom den är så stor kan det vara smidigare att hämta den via kommandoraden:

    $ curl https://www.csc.kth.se/~lk/unique_tracks.txt > unique_tracks.txt

    Läs in den i ditt program och lägg in låtarna i din hashtabell, förslagsvis med artister som nycklar och deras respektive låtar som värden. Tänk på att varje nyckel har precis ett värde, och att gamla värden ska skrivas över om man anropar store med en nyckel som redan finns i hashtabellen.

    Redovisning

    Vid redovisningen ska du kunna

    • skissa principerna för insättning och sökning i hashtabeller,
    • visa hur man söker i din hashtabell med de från unqiue_tracks.txt inlagda låtarna,
    • förklara varför hashtabeller ger snabb sökning.
    1607900340 12/13/2020 11:59pm
    Ytterligare kommentarer:
    Maxresultat för gradering till > poäng

    Matris

     
     
     
     
     
     
     
         
    Det går inte att ändra en matris efter att du börjat använda den.  
    Hitta en matris
    Hitta matris
    Titel
    Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
    Titel
    Kriterier Bedömningar Poäng
    Redigera beskrivning av kriterium Ta bort kriterium rad
    Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
    tröskel: 5 poäng
    Redigera ranking Radera ranking
    5 till >0 poäng
    Full poäng
    blank
    Redigera ranking Radera ranking
    0 till >0 poäng
    Inga poäng
    blank_2
    Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
    poäng
      / 5 poäng
    --
    Ytterligare kommentarer
    Poängsumma: 5 av 5