Till KTH:s startsida Till KTH:s startsida

Laboration 3

Laboration 3 - Ordträd

Laborationens tema är binära sökträd.

  • Första uppgiften är att skriva en klass för binära sökträd och testa den.
  • Andra uppgiften är att bygga upp ett sökträd från en fil med svenska ord. Alla dubbletter ska skrivas ut.
  • Tredje uppgiften är att kolla orden i en engelsk text mot det svenska sökträdet. Finns det några skenbart svenska ord ska dom skrivas ut, men bara den första förekomsten av varje svenskt ord. (För att veta vilka ord man redan hittat sparar man förstås dom i ett extra sökträd.)

Skriv en klass för binära sökträd

Först måste du implementera ett binärt sökträd.

Tänk dig först ett abstrakt binärt sökträd. Eftersom man med Python kan jämföra ord (bokstavsordning) så går det bra att lagra ord i sökträdet, t ex så här:

   svenska = Bintree()              # Skapa ett trädobjekt
   svenska.put("gurka")		    # Sortera in "gurka" i trädet	
   - - -
   if svenska.exists("gurka"):      # Kolla om "gurka" finns i trädet
      - - -
   svenska.write()                  # Skriver alla ord i bokstavsordning

Klassen Bintree ska alltså ha tre metoder:

  • put(x) som sorterar in x i trädet
  • exists(x) som kollar om x finns i trädet
  • write() som skriver ut trädet

Men i filen bintreeFile.py ska du dessutom definiera tre hjälpfunktioner. När trädobjektets put("gurka") anropas skickar trädet sin rotpekare och det nya ordet till en rekursiv funktion putFunc som ser till att en ny nod skapas på rätt ställe. Analogt gör de övriga anropen, alltså så här.

class Bintree:
    def __init__(self):
        self.root=None

    def put(self,newvalue):
        self.root=putFunc(self.root,newvalue)

    def exists(self,value):
        return existsFunc(self.root,value)

    def write(self):
        writeFunc(self.root)
        print("\n")



Här är klassen slut men sedan kommer definitionerna av funktionerna putFunc, existsFunc och writeFunc. Trädet ska bara lagra en upplaga av varje objekt som läggs in.

Det finns förstås också en class Node i bintreefilen som innehåller ett värde och två pekare:left och right.

Andra uppgiften: Bygg träd och skriv ut dubbletter


Nu ska du läsa in ett ord i taget från filen word3.txt och lägga in det ditt binära sökträd. Ord som förekommer flera gånger (dubbletter) ska skrivas ut.

from bintreeFile import Bintree
svenska = Bintree()
with open("word3.txt", "r", encoding = "utf-8") as svenskfil:
    for rad in svenskfil:
        ordet = rad.strip()                # Ett trebokstavsord per rad
        if svenska.exists(ordet):
            print(ordet, end = " ") 
        else:
            svenska.put(ordet)             # in i sökträdet
print("\n")



Om du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap.

Tredje uppgiften: Två binära sökträd med ordlistor

När du nu har ett sökträd med alla svenska trebokstavsord kan du blixtsnabbt kolla om ett givet ord finns med. Du ska nu läsa filen engelska ord för ord och putta in orden i ett annat sökträd. Nu vill du inte ha dubbletterna utskrivna, så kolla först if engelska.exists(...). Om ordet redan fanns gör du ingenting, men om det är nytt ska du också kolla om det råkar finnas som svenskt ord. I så fall ska det skrivas ut på skärmen.

Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap!

Redovisning

När allt fungerar som det ska bör du ta en extra titt på koden. Är den kommenterad och begriplig?

Kontrollera att du gjort alla uppgifterna ovan. Den här labben ska redovisas tillsammans med labb 2 och 4.

Betyg

betyg E: Ditt program ska lösa uppgifterna ovan.
Vid redovisningen ska du också

  • kunna rita och berätta hur binärträdet byggs upp,
  • förklara varför det går snabbt att söka i ett binärträd,
  • förklara idén bakom att ha put som anropar putFunc, exists som anropar existsFunc och write som anropar writeFunc

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å:

  • Kunna redogöra för vilka olika fall man bör testa för att försäkra sig om att klassens metoder fungerar.
  • Testa sökningen praktiskt. Jämför tidsåtgången vid sökning i trädet med linjärsökning i en lista. Använd t ex time.time().

betyg A: Kraven för C uppfyllda + en av följande extrauppgifter:

  • Söt tös: Undersök vilka trebokstavsord som blir andra ord baklänges. Varje ordpar ska bara skrivas ut en gång och symmetriska ord inte alls.
  • Alpin pinal: Undersök vilka fembokstavsord som blir ett annat ord när dom två första bokstäverna flyttas sist. Du kan använda ordlistan word5.txt.



Alexander Baltatzis created page 14 January 2014

commented 31 January 2014

Hej!

Har jag förstått rätt om funktionerna putta( ), finns( ) och skriv( ) ska vara rekursiva alla tre?
Och vad menas med "Analogt gör de övriga anropen, alltså så här. "?

Teacher commented 1 February 2014

Ja, putta( ), finns( ) och skriv( ) ska vara rekursiva alla tre.

"Analogt..." syftar på att även metoderna exists() och write() ska anropa rekursiva funktioner. Titta på kodskelettet för Bintree så ser du hur det är tänkt!

commented 9 February 2014

Vad hände med kravet för A att inte blanda svenska och engelska i funktions och variabelnamn? Bör ni inte föregå med gott exemepel i uppgiftsbeskrivningarna, eller gäller detta inte i den här upgiften? Se http://www.csc.kth.se/utbildning/kth/kurser/DD1320/tildav14/granskningshjalp.html#språk

Teacher commented 9 February 2014

Mea culpa. Dessutom saknas det mellanslag. Tack för påpekandet - snart ser det bättre ut!

commented 9 February 2014

Funktionerna put och exists och klassen treenode står skrivna i kurslitteraturen. Är det ok att använda dem (med vissa modifikationer)?

commented 9 February 2014

Ok, bra tack! Har ett litet huvudbry. Mitt sökträd/python verkar tycka att "ä" kommer före "å". Är det här någon känd bugg, eller har jag gjort något fel. (Om det verkar som att jag har gjort något fel, räcker det med att ni påpekar det så löser jag problemet).

Tack på förhand!

commented 9 February 2014

Kan ju bifoga mitt shell test.. 

>>> if "ä" < "å":
... print("OK")
...
OK
>>> if "å" < "ä":
... print("Ehm")
...

(Inget printas hä'r)

Teacher commented 9 February 2014

Jag gick igenom åäö-problemet på en av föreläsningarna i veckan. De är felsorterade i asciitabellen se plats 228, 229 för å och ä. 

Det går att sortera rätt på många sätt. Vi kommer att gå igenom sorteringsalgoritmer om du vill skriva sorteringen gör hand. Om man letar efter ett inbyggt sätt att sortera enligt den lokala teckenstandarden så brukar det i de flesta programmeringsspråk finnas ett nyckelord locale

I det paketet bör du kunna hitta en jämförelsefunktion som fungerar. 

Jag kan visa hur om du frågar på nästa föreläsning som jag tror handlar om sortering (eller om det är nästnästa som är sortering). 

commented 9 February 2014

Okej, tack så mycket! Jag har tyvärr inte möjlighet att gå på många av föreläsningarna på grund av dubbelbokningar i schemat med mitt KEX.

commented 10 February 2014

locale.strcoll fungerade bra, kommer det någon sorteringslabb? Om inte vill man ju skriva sorteringsalgoritmen själv.

commented 10 February 2014

locale.strcoll fungerade bra för mig också men på skolans datorer var jag först tvungen att sätta: 

import.locale

locale.setlocale(locale.LC_ALL, 'sv_SE.utf-8')

commented 10 February 2014

Finns det någon anledning att inte ha hjälpfunktionerna putFunc, existsFunc, writeFunc i klassen? Får man ha det om man vill?

commented 11 February 2014

Jag tror jag vet varför Hjalmar... om man läser ordagrant för betyg C:

Du ska också:

  • Kunna redogöra för vilka olika fall man bör testa för att försäkra sig om att klassens metoder fungerar.

--> Eftersom de mer komplexa rekursiva funktionerna inte ligger i klassen så behöver vi inte testa dem ..

(Självklart är inte så fallet, men jag vill bara att ni (lärare), ska lära er att skriva mer begripliga uppgiftsbeskrivningar)

Teacher commented 11 February 2014

Hmm, är det inte så att klassens metoder anropar funktionerna?

commented 11 February 2014

hmm jo, och det är det enda de gör..

One user removed his/her comment
One user removed his/her comment
commented 12 February 2014

Är tanken att time.time() skall användas för att mäta tidsåtgången av de givna uppgifterna (dvs de som printar ut "hemliga budskap") eller för att testa sökningen i sig? Om jag exempelvis mäter tiden före och efter att klassmetoden exists gjort sitt jobb får jag nämligen ut 0.0 sekunder i skillnad. Jag får även 0.0 s om jag mäter före och efter att 'in'-operatorn undersökt en lista.

Teacher commented 12 February 2014

Hur många värden söker du bland? 

One user removed his/her comment
commented 12 February 2014

Motsvarande trädobjektet 'svenska' som bildas av word3.txt utan dubletter, då inga större träd angivits i labben.

commented 12 February 2014

Uppdatering:

I vissa fall, efter att jag trots många upprepningar inte ser något återkommande mönster, kan det faktiskt bli en liten skillnad i söktiderna.

Test

Låt mig gärna veta om det - med era egna resultat som facit - kan finnas någonting jag missuppfattat med uppgiften :)

Teacher commented 12 February 2014

Du behöver fundera lite mer på hur du ska genomföra testerna!

Här är ett tips till:

Vilka faktorer beror söktiden på rent teoretiskt?

commented 13 February 2014

Jag har haft lite svårigheter med att mäta tiden, det går för fort, har lagt in en lista med ord som båda metoderna ska leta efter, men time.time() visar bara 0.0000 för båda. Finns det några hints till hur man ska kunna jämföra tiden?

commented 13 February 2014

time.clock() funkar istället för time.time(), men den ger tillbaka väldigt många värdesiffror

Teacher commented 13 February 2014

Hints i repris:

  • Hur många värden söker du bland? 
  • Vilka faktorer beror söktiden på?

 

Teacher commented 13 February 2014

Abstraktion också ingår ju också i kursen. Att fundera över:

  • Vilken sorts data kan man lagra i en lista?
  • Vilken sorts data kan man lagra i ett binärt sökträd?

One user removed his/her comment
One user removed his/her comment
commented 15 February 2014

Vad menar du med abstraktion i det här sammanhanget?

Menar du att jag ska fundera över skillnaden mellan objekt av klasser som jag själv har skapat och färdiga typer i python, exempelvis strängar?

För att expandera på ämnet, (och visa att jag har funderat):

Alla objekt du kan lagra i ett binärt sökträd, kan man även lagra i pythons mycket flexibla lista. MEN det här gäller nödvändigtvis inte omvänt. Med andra ord; alla objekt som du kan lagra i en lista, exempelvis python strängar, kan du inte utan vidare lagra i ett binärt sökträd. Förklaring:

För att lagra data i ett binärt sökträd måste vi kunna kategorisera eller sortera den data vi lägger in. I vårt fall har vi strängar av bokstäver och symboler som kan sorteras med hjälp av ASCII-tabellen eller metoder i pythons locale modul. Dessutom måste vi kunna hålla reda på datans förhållande till annan data vi har lagt in. Vi vill alltså ha något som talar om något om var någonstans datan finns i det binära trädet. Det här löser vi med hjälp av noder, som (i vårt fall) är en datatyp som sparar en sträng samt både möjliggör strukturen i trädet och talar om förhållandet till underliggande noder. Detta gör noden genom att spara vilken nod som sorteras till höger och vänster om sig. Vad som är höger eller vänster är upp till dig, men exempelvis är höger ett högre sortingsvärde och vänster är ett lägre. Datan, både strängen som vi vill lagra och de underliggande noderna, sparas i "Nod" klassens attribut. Vi har nu med Nod klassen på sätt och vis skapat vår egen "python typ", som både håller en sträng och två förhållanden.

Teacher commented 15 February 2014

Mycket insiktsfull och bra sammanfattning!

commented 15 February 2014

Tack! Men min fråga kvarstår: Vad menar du med abstraktion i det här sammanhanget?

Teacher commented 16 February 2014

Just det jag skrev - att man kan lagra olika typer av data! Ni har ju implementerat ett Binärt sökträd (och testat det med strängar). Men man kan ju lagra vilka objekt som helst i den, med begränsningen du angav ovan - att man måste kunna jämföra objekten.