Till KTH:s startsida Till KTH:s startsida

Laboration 5

Laboration 5 - Atomvikter

Ditt program ska bygga upp en hashtabell över alla grundämnens beteckningar och atomvikter så att det supersnabbt kan söka önskad information. Dialogen blir så här:

    Atombeteckning: Ag
    107.8682
    Atombeteckning: Au
    196.966569
    Atombeteckning: Q
    Okänd atom
    Atombeteckning: 

Du ska göra tre versioner av programmet:

  1. Använd Pythons inbyggda datastruktur dictionary som hashtabell.
  2. Implementera en egen hashtabell.
  3. Lägg till ett grafiskt gränssnitt.

1. Hashning med Pythons inbyggda dictionary

Skriv en klass Hashtabell som använder dictionary. Den ska ha metodernaput ochget.

Programmet hashtest.py innehåller data om alla atomer (namn och atomvikt). Lista ut vad det gör och hur det anropar hashtabellen. Modifiera det sedan för att kontrollera om din hashtabell fungerar.

Skriv sedan ett huvudprogram labb5.py där man kan ge ett atomnamn och få ut atomvikten, enligt dialogexemplet ovan.

2. En egen implementation av hashtabellen

Nu ska du göra en ny version av klassen Hashtabell (spara den i en ny fil) där du använder en Python-lista för att implementera en egen hashtabell. Krav:

  • Noderna måste innehålla både nyckel och värde
  • Hashtabellen ska vara lagom stor
  • Någon krockhantering måste ingå, t ex krocklistor eller probning
  • AnvändKeyError för att tala om att en nyckel inte finns
  • Skriv en egen hashfunktion
  • Ska klara testning med hashtest.py ovan

Låt nu labb5.py använda din egen hashtabell!

3. Grafiken

För att få till grafiken i labb5.py importerar du klasserna Molgrafik och Ruta från filen molgrafik.py.

Börja med att skapa ett Molgrafik-objekt;

  mg = Molgrafik()

Klassen Ruta har fyra attribut:
atom där du kan lägga in atomens namn
num där du kan lägga in atomens vikt
next ochdown som du kan strunta i för denna labb (dom används i labb 7).

Gör ett objekt av Ruta och använd sedan metoden show så här:

  mg.show(r)


Om programmet avslutas direkt hinner man inte se grafiken blinka förbi. Lägg en slinga runt huvudprogrammet för inmatning av flera atomer.

PS Provkör gärna programmet i ett Terminalfönster för att undvika ev problem med IDLE.

Betyg

betyg E: Ditt program ska lösa uppgifterna ovan.
Vid redovisningen ska du även kunna

  • motivera ditt val av hashfunktion, krockhantering och tabellstorlek,
  • skissa hashtabellen,
  • förklara varför hashning ger snabb sökning

betyg C: Kraven för E uppfyllda +  Labben inlämnad via KTH Social i tid och redovisad i tid (se datum under Laborationer).
Du ska också:

  • Provköra hashtabellen med större datamängder: I programmet storfil.py används en dictionary för att lagra en miljon artister och sånger.
    Kopiera programmet, byt ut "songtable" mot din egen hashtabell och se till att det fungerar!

    Om du kör hemma kan du ladda ner filen här: unique_tracks.txt (84MB)

betyg A: Kraven för C uppfyllda +

  • Förbättra hashtest.py med fler testfall
  • Skriv om hashtest.py med unittest

Alexander Baltatzis created page 14 January 2014

commented 23 February 2014

Kan man även redovisa lab 5 på ett tidigare labtillfälle?

Teacher commented 24 February 2014

Hjälp har första prioritet, men på lugna labbar (speciellt kl 8-10) brukar det finnas tid för redovisning.

commented 28 February 2014

Lite oklart hur avancerad grafiken ska vara, ska vi göra grafikfönster för inmatning av önskad atom också eller endast visning av den atom man söker efter?

Teacher commented 28 February 2014

Det räcker med att du visar grafiken enligt det som står i uppgiften punkt 3, men om du vill lägga till inmatning i GUI:t också så får du mycket gärna göra det!

commented 28 February 2014

Vad är bra värden för "tidshashen" ?

Får mellan : 0.0155770778656 - 0.070965051651

När jag söker på olika artister.

commented 2 March 2014

Jag har problem med "é" och "á" i unique_tracks.txt.
Sparad som utf8, kör på osx och får "UnicodeDecodeError: 'ascii' codec can't decode byte 0xc3 in position 315: ordinal not in range(128)".

Hittar ingen vettig lösning och är tacksam för hjälp!

commented 2 March 2014

Funkar om jag kör i terminalen men jag skulle gärna vilja få lite koll på hur man löser det i idle också..

Teacher commented 2 March 2014

@Anders:

Fundera över vad du förväntade dig för tidsvärde. Vilka faktorer inverkar på tiden?

PS Skriv inte ditt svar här - spara det till redovisningen :-)

Teacher commented 2 March 2014

@David:

Öppnar du filen med open(..., encoding = "utf8") ?

Just IDLE på Mac har en del egenheter - det är egentligen inte värt att ägna tid åt att få något att fungera där (om det funkar i teminalen).

commented 2 March 2014

Hej. 
Blir lite förvirrade angående kravet "Noderna måste innehålla både nyckel och värde" för hashtabellen uppgift 2.  Vilka noder är det egentligen ni syftar på? I hashtest.py som gavs i uppgift 1 används noden "Atom" som innehåller namn och värde, är det denna ni syftar på i kravet ovan?

Teacher commented 2 March 2014

Uppgift 2 börjar så här:

"Nu ska du göra en ny version av klassen Hashtabell (spara den i en ny fil) där du använder en Python-lista för att implementera en egen hashtabell."

Det är de noder du använder i din egen implementation av hashtabellen kravet syftar på. Exakt hur noden ska se ut bestämmer du själv, men den måste alltså ha plats för både nyckel och värde. (Att fundera på: varför måste båda vara med?)

One user removed his/her comment
commented 3 March 2014

När det står "skriv din egen hashfunktion", betyder det alltså att man inte får använda t.ex. pythons inbyggda funktion hash() i sin hashfunktion? 

Teacher commented 3 March 2014

Ja - man ska hitta på en egen!

commented 3 March 2014

För oss som läser DD1321 finns det ännu ingen inlämningslänk för denna laboration. När kan en sådan tänkas dyka upp? :)

Teacher commented 3 March 2014

Vad bra att du frågade - den fanns där, men hette bara "Laboration 5", precis som höstterminens labb. Nu har den rätt namn (liksom sexan och sjuan).

commented 4 March 2014

Om någon som kör windows och har fastnat (som jag gjorde) på att storfil krashar i när den läser in unique_tracks så är här en länk till en ascii konverterad version av filen som borde fungera:

https://www.dropbox.com/s/sxo68za5jw65fga/unique_tracks.txt

commented 6 March 2014

Kommer det komma fler bokningsbara tider att redovisa denna laboration?

Teacher commented 6 March 2014

Ja, dom kommer upp automatiskt efter hand!