□ Testa binärsökning i Kattis

Leta rätt på en binärsöknings-funktion. Använd gärna generativ AI (t ex ChatGPT) för att skapa funktionen. Det finns också flera implementationer i föreläsningsanteckningarna och i boken att inspireras av. OBS! Den rekursiva versionen är långsammare.

Använd programmet nedan för att provköra funktionen binary_search som du har letat rätt på.  

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

Testa nu funktionen i Kattis:Binärsökning Links to an external site..

• Första testfallet i Kattis-beskrivningen är Sample Input 1
• Var noga med att se till att utskriften för ditt program motsvarar Sample Output 1 i Kattis-beskrivningen.

□ 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 Links to an external site.. 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..."

När du öppnar filen kan du behöva ange encoding (utf-8 eller latin1).

Behöver du mindre filer att provköra med? (uppdelad med  csplit -s unique_tracks.txt antal_rader)

□ 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) Links to an external site. 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 Links to an external site. 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. Använd pythons dict som är en hashtabell.

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 (readfile och linsok behöver du skriva själv). När man tar tid på en funktion som har parametrar kan man använda lambda Links to an external site..

def main():

    filename = "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 ChatGPT, 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 så att den bara tar tid på en körning (sätt parametern number = 1). Om det tar för lång tid att köra: ange tiden för det största n som är rimligt (du behöver inte köra programmet i timmar).

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. Det går också bra att skriva en separat fil och lämna in den tillsammans med koden. Förklara skillnaden i uppmätta tider när storleken på listan varieras:

• mellan de olika sökningsmetoderna
• mellan de olika sorteringsmetoderna.

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 sökningsmetoderna och mellan de olika sorteringsmetoderna.