Laboration 6: Sökning och sortering

Mål: Kunna jämföra algoritmer med avseende på tidskomplexitet, i teori och praktik.

Läsning

• Läs i kapitel 3 i kursboken (Cormen): Algorithms for Sorting and Searching, och kapitel 4: A Lower Bound for Sorting and How to Beat It

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

Lista med objekt

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)

Testa att inläsningen har fungerat.

Modulen timeit

Läs i dokumentationen för Pythons modul timeit och svara på följande frågor:

• Vad representerar parametern stmt?
• Vad representerar parametern number?
• Vad är det timeit tar tid på?
• Vad skrivs ut av ett anrop av timeit?

Tidtagningen

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 att komma igång har du följande exempel (kursiverade funktioner behöver du skriva själv). När man tar tid på en funktion som har parametrar får man använda lambda.

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")

Du får gärna använda kod (för sortering och sökning) från föreläsningar, kursboken eller andra källor, men var noga med att ange var koden kommer från. Du får ändra och utföra egna tester där du sorterar på låttittel istället för artis eller gör nya objekt där man te.x. sorterar i första hand med avseende på artist och i andra hand med avseende på låttitel för att få en större sökmängd. 

Analys

Skriv upp tidskomplexiteten för de algoritmer du tagit tid på ovan. Stämmer dina resultat med teorin? Skriv en kommentar sist i ditt program där du analyserar dina resultat.förklara skillnaden i tid mellan de olika momenten.

Redovisning

Labben lämnas in på på git och redovisas muntligt av bägge gruppmedlemmarna.

Vid redovisningen ska du kunna

• visa hur dina sök-, och sorteringsfunktioner fungerar,
• förklara och redovisa vilken tidskomplexitet dina algoritmer har,
• motivera upplägget av dina experiment,
• 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.