Till KTH:s startsida Till KTH:s startsida

Laboration 5 del 1

Laboration 5 del 1: Sökning och sortering

Läsning

Läs i kapitel 4 i kursboken om Sorting and Searching, men vänta med avsnittet om Hashning till Labb 5 del 2.

Sökning och sortering

I denna labb ska du arbeta med större datamängder. Filen /info/tilda/unique_tracks.txt (84MB) är hämtad från Million Song Dataset. Den innehåller data om en miljon låtar. Varje rad i filen har formatet:

     trackid<SEP>låtid<SEP>artistnamn<SEP>låttitel

Skriv en klass som representerar en låt enligt ovan. Förutom de vanliga metoderna ska du också implementera __lt__(self, other) som kan jämföra om objektet self är mindre än objektet other, med avseende på artistnamn.

Läs in låtarna från filen, skapa ett objekt för varje rad och spara objekten både

  • i en lista
  • i en dictionary (med artistnamn som nyckel)

Nu ska du skriva ett program som gör följande, och tar tid på varje del:

  • Söker med linjärsökning i den osorterade listan.
  • Sorterar listan med lämplig sorteringsmetod.
  • Söker med binärsökning i den sorterade listan.
  • Slår upp ett element i dictionaryn.

Som hjälp för tidtagningen har du följande huvudprogram (kursiverade funktioner behöver du skriva själv):

def main():

    filename = "/info/tilda/unique_tracks.txt"

    lista, dictionary = readfile(filename)
    n = len(lista)
    print("Antal element =", n)

    sista = lista[n-1]
    testartist = sista.artist

    linjtid = timeit.timeit(stmt = lambda: linsok(lista, testartist), number = 10000)
    print("Linjärsökningen tog", round(linjtid, 4) , "sekunder")

    sorttid = timeit.timeit(stmt = lambda: sortera(lista), number = 1)
    print("Sorteringen tog", round(sorttid, 4), "sekunder")

    bintid = timeit.timeit(stmt = lambda: binsok(lista, testartist), number = 10000)
    print("Binärsökningen tog", round(bintid, 4) , "sekunder")

    dictionarytid = timeit.timeit(stmt = lambda: dictionary[testartist], number = 10000)
    print("Slå upp i dictionary tog", round(dictionarytid, 4) , "sekunder")

Redovisning

Labben lämnas in på kurswebbsidan (se Inlämningsuppgifter i vänstermenyn) och redovisas muntligt av bägge gruppmedlemmarna.

Vid redovisningen ska du kunna

  • berätta vilken tidskomplexitet dina algoritmer har
  • visa hur dina sök-, och sorteringsfunktioner fungerar 
  • förklara skillnaden i tid mellan de olika momenten.

Betyg

Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i period 2.

Teacher Linda Kann created page 21 September 2015

commented 26 September 2015

Är det tänkt att man ska köra linjärsökningsfunktionen 10000 gånger? Det tar runt 3-4 sekunder att köra den 10 gånger

Teacher commented 26 September 2015

Prova då med 10 varv på alla tidtagningarna!

commented 29 September 2015

Hur kommer det sig att dictionaryn har en mycket kortare längd än listan?

Teacher commented 29 September 2015

Mycket bra fråga! Prova att använda trackid som nyckel när du lägger in i dictionaryn och se om det blir någon skillnad...

One user removed his/her comment
commented 2 October 2015

Är tanken att man ska få ut en lista med alla låtar som artisten gjort när man gör dem olika sökningarna eller bara en True/False om man hittar en låt eller inte?

Teacher commented 2 October 2015

Bara True/False!

commented 6 October 2015

Hej, i main så är dictionary inte kursiverat. Ska det vara så? Jag och min labbpartner är lite förvirrade huruvida vi ska skriva en funktion som skapar ett dictionary eller inte.

Teacher commented 6 October 2015

Ni ska skriva funktionen readfile som skapar både en lista och en dictionary med Låtar i.