d4

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

Läs i F12-13 Sortering och F3 Komplexitetsanalys du kan även läsa i Miller-Ranum om Sorting and Searching Links to an external site.

Sökning och sortering

I denna labb ska du arbeta med större datamängder. Labben är uppdelad i delar. Läs igenom hela labben först. 

Del 1 – olika algoritmer löser samma problem

Filen unique_tracks.txt är hämtad från Million Song Dataset Links to an external site.. Den innehåller data om en miljon låtar. Du kan hämta den via din webbläsare, men eftersom den är så stor kan det vara smidigare att hämta den via kommandoraden:

$ curl https://www.csc.kth.se/~lk/unique_tracks.txt > unique_tracks.txt

Varje rad i filen har formatet:

trackid<SEP>låtid<SEP>artistnamn<SEP>låttitel

Lista med låtobjekt

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 både

• i en lista (med listor avses i denna labb Pythons inbyggda vektor exempel v = [] )
• i en dictionary (med t.ex artistnamn som nyckel)

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?

Tidtagning 

Nu ska du skriva ett program som gör följande, och tar tid på varje del:

• Söker efter nästsista  elementet med linjärsökning i osorterade listor.
• Söker efter nästsista elementet med linjärsökning i sorterade listor.
• Sorterar listor med mergesort, quicksort eller heapsort som du kopierar (och förstår) från bok, nät eller föreläsningsanteckning (använd inte Pythons inbyggda sorteringsmetod).
• Söker med linjärsökning efter element i en osorterad lista, redovisa genomsnittssökningen. Sök 1000 olika slumpade element/index och redovisa genomsnittet.
• Söker med binärsökning i sorterade listor, du kan kopiera binärsökningskoden från bok, nät eller föreläsningsanteckningar. 
• Slår upp element i Pythons inbyggda dictionary

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 Links to an external site.. Ditt eget progam kan se annorlunda ut.

def readfile(filename):
	# TODO
def linsok(lista, testartist):
	# TODO
def main():

    filename = "/info/tilda/unique_tracks.txt"
    # file_del2 = "/info/tilda/sang-artist-data.txt"

    lista, dictionary = readfile(filename)
    antal_element = len(lista)
    print("Antal element =", antal_element)

    sista = lista[n-1]
    testartist = sista.artist

    linjtid = timeit.timeit(stmt = lambda: linsok(lista, testartist), number = 100)
    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/söker på låttittel eller något annat istället för artistnamn. Alternativt kan man göra nya objekt där man t ex 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 mängd med unika söknycklar.

Du ska köra flera körningar med  åtminstone testmängderna 250000, 500000 och 1000000. Tips, börja med små filer/testmängder som tar kort tid att köra medan du utvecklar och kör de stora testkörningarna medan du fikar.

Du kan antingen tillverka flera testfiler, t.ex. genom att på kommandorad i unix/ubuntu/mac skriva 

$ head -1000 /info/tilda/unique_tracks.txt > nyfilmed1000forstarader.txt

Eller kan du t.ex. returnera olika stora listor från funktionen som läser från fil

    lista1 = readfile(filename, 1000)
    lista2 = readfile(filename, 100000)

Eller så kan du låta dina funktioner ta ett extra argument som anger storleken på listan och alltid skicka den stora listan.

Anteckna tidskomplexiteten för de algoritmer du tagit tid på ovan. 

Visualisering av resultat

Stämmer dina resultat med teorin? De algoritmer som enligt teorin är linjära, är de det i praktiken?

Skriv ner kommenterade testresultat i ett textdokument. Ha med tabeller och grafer med testmängd och körtid. Skriv kortfattat om teorin stämmer med dina testresultat. Förklara kortfattat skillnaden i tid mellan de olika momenten. 

Du kan rita graferna för hand eller klistra in värdena i något verktyg som matlab, google sheets eller excel. Det finns också ett program Gnuplot, som kan skapa bildfiler i png-format. Det finns förinstallerat på skolans Ubuntu-datorer, och om man vill ha det på sin egen dator kan man ladda ned det från webben. Vill du lära dig mer om Gnuplot kan du läsa Martins introduktion.

Del 2 – när lönar sig sortering?

I den här uppgiften ska du undersöka två olika metoder för att hitta den k längsta låten i en lista av låtar. För att göra det behöver du använda filen sang_artist_data.txt, som förutom artist och titel även innehåller information om låtarnas längder. Även den här filen är ganska stor, så det kan vara smidigare att hämta den via kommandoraden:

$ curl https://www.csc.kth.se/utbildning/kth/kurser/DD1320/sang-artist-data.txt > sang_artist_data.txt

Varje rad innehåller tabbseparerad data (använd .split('\t') i Python) på det här formatet:

artistid	artistnamn	sångtitel	låtlängd	år

Skapa en variant av din låtklass som har plats för att spara information om låtarnas längder. Läs in alla låtar i från sang_artist_data.txt och spara låtobjekten i en lista.

Implementera nedanstående två metoder för att hitta den k längsta låten. Se till att man kan skicka in k som parameter, så att den är lätt att ändra. Antalet låtar ska du hålla konstant, genom att hela tiden låta metoderna operera på samtliga låtar i filen sang_artist_data.txt.

Metod 1 – upprepade linjärsökningar

1. Linjärsök genom listan med låtobjekt och notera den längsta låten. Ta bort den.
2. Upprepa föregående steg k-1 antal gånger.
3. Linjärsök genom listan med låtobjekt och returnera den längsta låten.

Metod 2 – sortera och plocka ut

1. Sortera listan med låtobjekt med den sorteringsmetod du fann var snabbast från del 1.
2. I den sorterade listan, returnera elementet med index k-1.

Teoretisk analys

• Kommer de båda metoderna alltid att ge samma svar, för samma k? Varför/varför inte?
• Vad har de båda metoderna för respektive komplexitet?
• För de 999 988 stycken låtarna i sang_artist_data.txt, uppskatta teoretiskt för vilket k den ena metoden är snabbare än den andra och vice versa. Vid vilket k är de lika snabba?

Praktisk analys

Kör de båda metoderna för olika värden på k och ta tiden på körningarna. Gör det för minst tio olika värden på k och var noga med att få med brytpunkten; det värde på k när den ena algoritmen blir effektivare än den andra. Här är ett kodskelett att utgå från (anpassa gränserna och steglängden för k vid behov):

k = 1

while k <= 30:
   time_1 = timeit.timeit(stmt = lambda: method_1(song_list, k), number = 1)
   time_2 = timeit.timeit(stmt = lambda: method_2(song_list, k), number = 1)

   print(k, time_1, time_2)

   k += 4

Presentera resultatet i ett diagram med k-värdena på x-axeln och körtiderna på y-axeln. Använd gärna Gnuplot för att att skapa diagrammen.

Tips

• Jobba med små datamänger medan du utvecklar. Skriv tillfredsställande kod som testar med olika datamängder. Ta en liten fikapaus när du slutligen kör med stora datamängder.
• .split('<SEP>') och .split('\t') separerar en string till en lista
• .strip() kan ta bort returtecknet i slutet på en string, t.ex. sista elementet på raden
• Öppna filen med UTF8 som teckenkodning. Datafilerna kan innehålla konstiga specialtecken. En del terminaler kan ha svårt att skriva ut specialtecken, det är OK att ta bort enstaka rader från låtfilen om det är specialtecken som ger upphov till fel.
• Man kan använda två fält som dictionary-nyckel genom att konkatenera (lägga ihop) dem som strängar.
• Man kan få utskrift till fil genom att använda > på terminalraden. Exempel:
  $ python3 mittprogram.py > resultatfil.txt
• Man kan lägga till utskrift till en befintlig fil med >> på terminalraden. Exempel:
  $ python3 mittprogram.py >> resultatfil.txt
• Om man vill importera filerna till ett externt program som excel eller google sheets så kan man skriva värdena separerade med , eller ; till en fil som går att importera. Eller kan man skriva värdena i matlab-format till en .m fil som matlab kan läsa in. 

Använd som sagt inte Pythons inbyggda sortering i denna uppgift. Den inbyggda sorteringen är skriven i C-kod och kompilerad till optimerad maskinkod. Den kommer att köra betydligt snabbare än samma algoritm i skriven i Python.

Redovisning

Vid redovisningen ska du kunna

• visa hur dina sök-, och sorteringsfunktioner fungerar,
• visa tabeller och grafer på dina resultat
• förklara och redovisa vilken tidskomplexitet dina algoritmer har,
• motivera upplägget av dina experiment,
• förklara skillnaden i tid mellan de olika momenten.