□ Testa binärsökning i Kattis

Som uppvärmning ska du skriva en binärsöknings-funktion och testa den i Kattis. Det finns flera implementationer i föreläsningsanteckningarna och i boken att inspireras av.

Utgå från programmet nedan, och infoga din egen funktion binary_search:

def main():
    #Läs in listan
    indata = input().strip()
    the_list = indata.split()
    #Läs in nycklar att söka efter
    key = input().strip()
    while key != "#":
        print(binary_search(the_list, key))
        key = input().strip()

main()

□ Sökning och sortering

I denna labb ska du arbeta med större datamängder. Filen 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

Ladda ner filen från webbläsaren genom att högerklicka och välja "Save link as..."

Om du kör på skolans Ubuntu-datorer så ligger filen här: /info/tilda/unique_tracks.txt

□ 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 i en lista. 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

Sökning

Här ska du jämföra sökning på tre olika sätt:

1. Linjärsökning i en osorterad lista.

2. Binärsökning i en sorterad lista. Sortera listan först med pythons sort-metod.

3. Sökning i hashtabell. Här kan du antingen använda pythons dict eller din egen hashtabell (om du redan gjort labb 7).

Skriv ett program som tar tid på varje variant av sökning ovan. 

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 kan man använda lambda.

def main():

    filename = "/info/tilda/unique_tracks.txt"

    lista = 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 själv välja vad du ska söka efter (låttitel alternativt artistnamn). Du får också välja vilket element du ska söka efter. Exemplet ovan söker efter den sista artisten. Är det en bra idé?

Fyll i tiderna i följande tabell:

För att göra en kortare lista kan du använda slicing:

 mindreLista = storLista[0:250000]

Sortering

Här ska du jämföra två olika sorteringsmetoder. Du får välja vilka metoder du vill (som du kan förklara). Välj en långsammare och en snabbare metod. Du får gärna använda kod (för sorteringen) från föreläsningar, kursboken eller andra källor, men var noga med att ange var koden kommer från.

Du kan välja att sortera på låttittel eller artistnamn. Modifiera din tidtagningskod från sökningen ovan. (Att sortera 1000 gånger kan ta lite väl lång tid.)

Fyll i tiderna i följande tabell:

□ Analys

Skriv upp tidskomplexiteten för de algoritmer du tagit tid på ovan. Stämmer dina resultat med teorin? Om inte - vad kan det bero på?

Skriv en kommentar sist i ditt program där du analyserar dina resultat. 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.

Redovisning

Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!

Vid redovisningen ska du kunna

• Visa hur dina sök-, och sorteringsfunktioner fungerar,
• Förklara och redovisa vilken tidskomplexitet dina algoritmer har,
• Förklara skillnaden i tid mellan de olika momenten.