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.