Uppgift 2 -- AD1 VT04 -- Uppsala Universitet

Din inlämning

• Ditt namn och klass.
• Om du löser uppgiften tillsammans med en annan student, ange den andra studentens namn. I så fall ska endast en av er lämna in en lösning, men båda ska meddela namn, klass och labpartner via inlämningssystemet.
• Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså).
• En kort beskrivning (en rad) av vad det är för fil.
• Notera att alla kommentarer och all dokumentation ska vara på engelska.

Uppgift

listMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list

Du ska undersöka hur sorteringstiden för mergesort skiljer sig mellan den implementationen och två andra implementationer av mergesort. De två andra implementationerna ska du skriva själv.

Den första implementationen

listOptMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list

Den andra implementationen

ArrayMergeSort: ('a * 'a -> bool) -> 'a array -> 'a array

Tiden för enstaka sorteringar kan mätas med hjälp av funktionen timeIt: ('a -> 'b) -> 'a -> real, som finns i filen ranTime.sml och tar en funktion f och ett argument a och returnerar exekveringstiden för f applicerat på a.

Vid redovisning av uppgiften ska du använda funktionen go: unit -> unit i filen u2test.sml (som inhåller filen ranTime.sml). Funktionen testkör de tre implementationerna på sorterat, omvänt sorterat och slumpmässigt data och genererar nio filer som sedan kan plottas med gnuplot.

Det ni ska sortera är endast heltal, och predikatet som ska jämföra heltalen är < -operatorn (skriv op< som första argument till sorteringsfunktionerna).

Uppgiften består av följande moment:

1. Ladda ner filerna listMergeSort.sml och ranTime.sml till ditt konto och öppna dem i en texteditor (förslagsvis Emacs).
2. Implementera sorteringsprocedurerna listOptMergeSort och arrayMergeSort. Om du vill testköra på lite större indata kan du generera slumpmässiga listor och arrayer med följande kommandon:

   För att skapa en slumpmässig lista, skriv:

   ArrRandom.rangelist (0, 10000) (numOfElms, Random.newgen())

   För att skapa en slumpmässig array, skriv:

   Array.fromList (Random.rangelist (0, 10000) (numOfElms, Random.newgen()))

3. Redovisa resultatet med hjälp av funktionen go: unit -> unit i filen u2test.sml. Funktionen testkör de tre implementationerna på sorterat, omvänt sorterat och slumpmässigt data. Nio filer genereras, till exempel lmsS.txt för listMergeSort på sorterat data, lmsOC.txt för listOptMergeSort på omvänt sorterat data och amsR.txt för arrayMergeSort på slumpmässigt data.

   Filen plotta innehåller en serie gnuplot-kommandon som läser de nio filerna och skapar grafer för de tre sorteringsalgoritmerna på filen sort.ps. Skriv gnuplot plotta vid unix-prompten för att skapa grafen ifrån de tre filerna med mätdata.

4. Beskriv matematiskt hur sorteringstiden beror av antalet element som ska sorteras för var och en av de tre implementationerna.
5. Kommentera experimentet och vilka slutsatser man kan dra av det. I din slutsats ska det framgå vilken av implementationerna som är den snabbaste, och med ungefär hur mycket snabbare den är än den långsammaste (ange resultatet i procent).

Din redovisning ska innehålla

• Din implementation av sorteringsprocedurerna listOptMergeSort och arrayMergeSort samt proceduren listMergeSort (se punkt 2 ovan).
• Sökvägar (URL) till en fil med de tre plottarna (se punkt 3 ovan).
• Matematiska uttryck för hur sorteringstiden beror av antalet element som ska sorteras för var och en av de tre implementationerna (se punkt 4 ovan).
• Dina kommentarer till experimentet och vilka slutsatser man kan dra av det (se punkt 5 ovan).

Glöm inte att alla funktioner ska dokumenteras enligt kodkonventionerna (dvs även listMergeSort).

Frivilliga extrauppgifter

Hall of Fame: De snabbaste implementationerna av mergesort på listor respektive arrayer kommer att presenteras på kurssidan. Att hamna i Hall of Fame ger inga bonuspoäng men äran är väl belöning nog. Vi kommer att ta emot tävlingsbidrag även efter sista inlämningsdatum.

Inlämning