Laboration 5 del 16

Laboration 5 del 16: 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.