Warning! This is the 2012 course's website! You probably want the current course website.
Fel i beskrivningen!
Alldeles för sent har jag upptäckt att det stod ett allvarligt fel i beskrivningen, som gjorde att de studenter som försökte sig på uppgiften fick väldigt konstiga tider som inte alls passade in i de förväntade komplexiteterna!
Felet var att i denna uppgift så ska man absolut inte räkna med tiden per ord, utan med tiden för att sortera hela listan! Tyvärr hade jag kopierat tabeller och annan text från förra inlämningsuppgiften, och glömt att ändra på alla ställen i texten.
Jag ber så mycket om ursäkt, och förstår varför många av er tyckte att uppgiften var meningslös… för det var den. Nu är beskrivningen nedan ändrad, och den som vill får gärna försöka igen. Och testprogrammet är ändrat så att det inte skriver ut några tider per ord!
Men: Ni har redan ägnat tillräckligt med tid åt detta, så härmed godkänner jag alla som har lämnat in tabeller med mätningar. Även om ni inte har beräknat några konstanter, eller om ni inte har beräknat några konstanter alls!
Ni som inte har lämnat in labben i tid måste fortfarande göra testerna, men ni behöver inte beräkna några konstanter. Däremot en enkel text där ni jämför de olika algoritmerna med varandra. Hämta det uppdaterade testprogrammet också, och kompilera om!
Inlämningsuppgift 3: Testning av sorteringsalgoritmer
I denna inlämningsuppgift ska ni testa några olika sorteringsalgoritmer och beräkna deras tidskomplexitet utifrån körningarna.
Bakgrund
Följande klasser ska ni testa:
- InsertionSort: Kursbokens implementering av insättningssortering.
- MergeSort: Kursbokens implementering av sammanflätningssortering.
- HeapSort: Kursbokens implementering av heap-sortering.
- QuickSort: Kursbokens implementering av "snabbsortering".
public <T extends Comparable<T>> void sort(T[] table);
Ni ska testa på samma två textfiler som i inlämningsuppgift 2:
- swahili-wikipedia.txt (11MB stor): innehåller hela Wikipedia på swahili, totalt ca 1,8 miljoner löpande ord; korpusen innehåller lite drygt 160 000 unika ord, varav 100 000 förekommer endast en gång (dvs. de är hapax-ord)
- swahili-sorted.txt (1,4MB stor): samma korpus, fast med orden redan sorterade i alfabetisk ordning, och inga dubletter; denna fil innehåller alltså ungefär 160 000 ord
Till er hjälp finns ett testprogram, TestSortAlgorithm, som anropas såhär:
$ java TestSortAlgorithm [sorteringsklass] [textfil] [antalord] [antaltest]där sorteringsklass är någon av klasserna ovan, textfil är någon av textfilerna ovan, antalord är ett heltal som säger hur stort fält som ska sorteras, och antaltest säger hur många gånger testet ska köras.
Programmet läser in antalord från filen och skapar ett fält. Sedan sorterar den fältet, och beräknar hur lång tid sorteringen tog. Detta gör programmet det givna antalet gånger och skriver ut en tabell. När ni ska beräkna komplexiteten nedan så ska ni alltid utgå från det bästa resultatet, dvs. den snabbaste körningen! (Anledningen till detta är att förseningar antagligen har mer med att göra med Garbage Collection och liknande saker, än med algoritmernas effektivitet).
Ladda ner
Filerna finns i ett zip-arkiv: inlupp3.zip. Arkivet är ca 4.2 MB stort, och packas upp till åtta filer om ca 13 MB.
Uppgift
Er uppgift är att beräkna de fyra olika algoritmernas tidskomplexitet i praktiken. De kan bete sig linjärt, O(n), eller som O(n log n), eller kvadratiskt, O(n2). För varje klass och textfil, ska ni köra testet med olika fältstorlekar, och utifrån detta beräkna om komplexiteten är (huvudsakligen) linjär, n log n, eller kvadratisk.
- Försök att passa in konstanterna A och B så att antingen T(n) = A·n + B eller T(n) = A·n·log(n) + B, eller T(n) = A·n2 + B blir så bra som möjligt. (Där n är lexikonstorleken).
- Testa minst 5–10 olika storlekar, så att ni får tillräckligt många datapunkter.
- Pröva med linjärt ökande lexikonstorlekar: ni kan utgå från 1000, 2000, 3000, 4000, …, ända tills ni har tillräckligt mycket på fötterna.
- Räkna inte med tiden per ord (som i inlämningsuppgift 2), utan det är den totala tiden som är viktig!
- Om skilladen mellan testtiderna är konstant, så är komplexiteten linjär. Om däremot skillnaden ökar, men bara lite åt gången, så kan vi gissa på n log n-komplexitet. Om slutligen skillnaden ökar, med konstant skillnad, så är komplexiteten kvadratisk.
- Observera att en viss algoritm kan bete sig helt olika på olika indata.
- Det blir rätt så många testkörningar (4 algoritmer som ska testas på 2 texter var, med 5–10 olika storlekar), så räkna med att det blir en del monotont arbete.
Ett tips är att skapa en enkel tabell där ni mäter tider och skillnaden mellan närliggande rader, samt skillnaden mellan skillnaderna. Lexikonstorleken ska öka konstant med varje rad (t.ex. ni = 1000·i). Om tidsskillanden mellan raderna är (i stort sett) konstant, så blir komplexiteten linjär. Om derivatan (skillnaden mellan skillnaderna) är (i stort sett) konstant, så blir komplexiteten kvadratisk. Om skillnaden ökar (för större n), samtidigt som derivatan minskar, så kan vi (när det gäller sorteringsalgoritmer) gissa på n log n-komplexitet.
| Rad (i) | Lexikonstorlek (ni) | Uppmätt tid, Ti | Skillnad, T'i = Ti – Ti-1 | Derivata, T''i = T'i – T'i–1 |
|---|---|---|---|---|
| 1 | 1000 | |||
| 2 | 2000 | |||
| 3 | 3000 | |||
| 4 | 4000 | |||
| 5 | 5000 | |||
| 6 | 6000 |
Inlämning
Fyll i en sånhär tabell för varje kombination av lexikon-klass och textfil, alltså totalt 8 tabeller.
| Sorteringsalgoritm: | ||
|---|---|---|
| Textfil: | ||
| Komplexitet: | (linjär, n log n, eller kvadratisk?) | |
| Konstanter: | A = | B = |
| Lexikonstorlek (n) | Uppmätt tid, T(n) | Beräknad tid T'(n) = A·n + B
[alternativt T'(n) = A·n·log(n) + B] [alternativt T'(n) = A·n2 + B] |
Skriv även en kort rapport (max en halv A4-sida) om hur det gick, vilka svårigheter ni hade, slutsatser man kan dra utifrån resultaten, etc.