Till KTH:s startsida Till KTH:s startsida

Laboration 6

Laboration 6: Sökning och sortering

Läsning

Läs i kapitel 4 i kursboken om Sorting and Searching,

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 via git 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 nästa period.

Alexander Baltatzis created page 18 January 2016

commented 17 February 2016

Hur ska vi ta hänsyn till ,att vissa artister har flera låtar, i en dictionary. Dictionaryn sparar bara det sista objektet till nyckeln med artistnamnet? Eller är det i senare labbar som det ska tas hänsyn till?

commented 28 February 2016

Jag undrar också över samma sak som Linnéa. För övrigt undrar jag hur vi ska hantera att vissa rader saknar data under "låttitel" (exempelvis TRWEQAA128EF36407B<SEP>SOVICLT12A58A7C4D0<SEP>Milton<SEP>).

När vi ska linjärsöka efter sista.artist, vilket är ett typisk "worst case", men samtidigt förekommer samma artist på plats 75 (tror jag det var), vilket resulterar i enbart 75 istället för 1000000 jämförelser, vilket nästan är "best case" och därför inte säger någonting om hur snabb en sökalgoritm är. 

commented 29 February 2016

Jag är sjuk idag. Ska min labbpartner redovisa på bokad tid i e.m, eller kan vi redovisa tillsammans nästa vecka? Labben är inlämnad via Git.

Teacher commented 29 February 2016

@Linnea, det är valfritt hur ni hanterar flera låtar per artist. 

@Eric Gör flera olika sökningar och redovisa. 

@Erik Om du är sjuk bör du stanna hemma och inte smitta ner någon. Skriv epost till mig hemifrån idag eller imorgon så tar vi ditt ärende separat.