Laboration 6

Laboration 6: 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 nästa period.