Labb 6: Sökning och sortering
- Inlämningsdatum 25 sep 2020 av 20:00
- Poäng 10
- Lämnar in en filuppladdning
Mål | Läs i kursboken |
Kunna jämföra algoritmer med avseende på tidskomplexitet, i teori och praktik. Se |
Kap 3 Algorithm analysis Links to an external site. Kap 6 Sorting and searching Links to an external site. (utom avsnittet om Hashing) |
□ Testa binärsökning i Kattis
Som uppvärmning ska du skriva en binärsöknings-funktion och testa den i Kattis Links to an external site.. 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 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..."
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) 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. 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 Links to an external site..
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:
n = 250 000 | n = 500 000 | n = 1 000 000 | |
Linjärsökning | |||
Binärsökning | |||
Sökning i hashtabell |
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:
n = 1000 | n = 10 000 | n = 100 000 | n = 1 000 000 | |
Långsam sorteringsmetod:
|
||||
Snabbare sorteringsmetod:
|
□ 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.