Warning! This is the 2012 course's website! You probably want the current course website.

Inlämningsuppgift 2: Testning av mängder

I denna inlämningsuppgift ska ni testa några olika mängd-implementeringar och beräkna deras tidskomplexitet utifrån körningarna.

Bakgrund

Följande klasser ska ni testa:

• HashSet: Javas egen implementation av en hashtabell med öppen adressering
• TreeSet: Javas egen implementation av ett rödsvart träd
• BinarySearchTree: En väldigt enkel implementation av ett (icke självbalanserande) binärt sökträd
• UnorderedArraySet: En mängd implementerad som en sekvensiell osorterad lista

Ni ska testa på följande två textfiler:

• 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, TestLexiconLookup, som anropas såhär:

  $ java TestLexiconLookup [lexikon-klass] [textfil] [lexikon-storlek] [antal-test]

där lexikon-klass är någon av klasserna ovan, textfil är någon av textfilerna ovan, lexikon-storlek är ett heltal som säger hur många ord som lexikonet maximalt får innehålla, och antal-test säger hur många gånger testet ska köras.

Programmet läser in filen och bygger ett lexikon. Sedan läser den in filen igen och slår upp varje ord i lexikonet, och beräknar hur lång tid varje lexikonuppslagning tog i medeltal. 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: inlupp2.zip. Arkivet är ca 5 MB stort, och packas upp till fem filer om ca 14 MB.

Uppgift

Er uppgift är att beräkna de fyra olika algoritmernas tidskomplexitet i praktiken. En del beter sig linjärt, andra logaritmiskt och åter andra har konstant tidskomplexitet. För varje klass och textfil, ska ni köra testet med olika lexikonstorlekar, och utifrån detta beräkna om komplexiteten är (huvudsakligen) konstant, logaritmisk eller linjär.

• Försök att passa in konstanterna A och B så att antingen T(n) = A·n + B eller T(n) = A·log(n) + 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.
• Börja med att se om komplexiteten är linjär genom att pröva med linjärt ökande lexikonstorlekar, t.ex. 1000, 2000, 3000, 4000, osv.
• Se till att tiden per ord inte är för liten: minst 1–2 μs/ord bör det vara, annars går det helt enkelt för fort för att kunna beräkna A och B.
• Om det går för fort så kan ni försöka med storlekarna 5 000, 10 000, 15 000, 20 000, osv.
• Om det fortfarande går alldeles för fort så kan ni pröva om komplexiteten är logaritmisk, genom att successivt fördubbla storlekarna: 5 000, 10 000, 20 000, 40 000, 80 000, 160 000, osv.
• Märker ni ingen skillnad per ord trots att ni har fördubblat ända upp till mer än 100 000 ord, så kan ni nog anta att komplexiteten är linjär, dvs. att A=0.
• Observera att en viss algoritm kan bete sig helt olika på olika indata. (Hur bör t.ex. ett obalanserat binärt sökträd bete sig på slumpmässig resp. sorterad 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. Lexikonstorleken ska antingen öka konstant med varje rad (t.ex. n_i = 5000·i), eller exponentiellt (t.ex. n_i = 5000·2ⁱ). Om tidsskillanden mellan raderna är (i stort sett) konstant, så kan ni räkna ut tidskomplexiteten.

Rad (i)	Lexikonstorlek (ni)	Uppmätt tid per ord, T(ni)	Skillnad, T(ni) – T(ni-1)

Inlämning

Fyll i en sånhär tabell för varje kombination av lexikon-klass och textfil, alltså totalt 8 tabeller.

Lexikonklass:
Textfil:
Komplexitet:	(linjär, logaritmisk, eller konstant?)
Konstanter:	A =	B =
Lexikonstorlek (n)	Uppmätt tid per ord, T(n)	Beräknad tid T'(n) = A·n + B [alternativt T'(n) = A·log(n) + 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.