Uppgift 2 - PK3 VT-03

Uppgift 2 måste lämnas in senast månadag 5/5 kl. 24:00. Lämna in den med hjälp av inlämningssystemet i slutet av denna sidan. Se till att läsa igenom kodkonventionerna innan du börjar. Dessa skall följas.

Efter denna uppgift ska du kunna

Före uppgiften

Din inlämning

Överst i din fil ska följande finnas (inom kommentartecken):

Se till att du hunnit ge ett svar på varje deluppgift.

Uppgift

Filen listMergeSort.sml innehåller funktionen listMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list, som är en implementering av mergesort med hjälp av listor. 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 på egen hand. Den första implementationen listOptMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list, ska vara en optimering av den givna funktionen listMergeSort. Hur du genomför optimeringen är upp till dig, men algortimen måste även efter optimeringen bygga på listor (och naturligtvis vara en implementation av mergesort)! (Tips: ett lämpligt ställe att optimera är vid uppdelningen av listorna.) Den andra implementationen arrayMergeSort: ('a * 'a -> bool) -> 'a array -> unit, ska vara mergesort med hjälp av arrayer (istället för listor).

Sorteringstiden ska mätas med hjälp av funktionen timeit: ('a -> 'b) -> 'a -> real, som finns att tillgå i filen ranTime.sml, som givit en funktion och dess argument returnerar exekveringstiden för argumentet applicerat på funktionen. 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).

Sorteringstiden ska presenteras grafisk för var och en av de tre implementationerna och med tre olika typer av indata: slumpmässig, sorterad och omvänt sorterad. Sorteringstiden ska även uttryckas matematiskt för var och en av de tre implementationerna, dvs hur sorteringstiden beror på antalet element som ska sorteras. Du ska kommentera dina implementationer, sorteringstiderna (såväl de matematiska som de exprementiellt) och dra slutsatser utifrån det och ditt resultat.

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.
     
  3. Kör de tre sorteringsprocedurerna på arrayer/listor med storlekar från 100 till 3000 element. Gör testet för följande tre olika strukturer på elementen i arrayen/listan:
     
    Tex kommer timeit(arrayMergeSort (op<)) (Array.fromList(Random.rangelist (0, 10000) (1000, Random.newgen()))); att skriva ut hur lång tid det tar för proceduren arrayMergeSort att sortera en slumpmässig array med 1000 element.

    (Förtydligande: funktionerna listMergeSort och listOptMergeSort ska ha listor som input, medan arrayMergeSort ska ha arrayer.)

  4. Sätt samman resultaten i en tabell, ha med minst 15 testvärden i det undersökta intervallet (100-3000 element). Eftersom ni testar tre olika typer av indata blir det tre tabeller för varje sorteringsprocedur, dvs ni ska skapa nio stycken tabeller. För att göra det hela enklare ska ni skriva en testfunktion (bestäm själv namn och parametrar) som skapar en tabell i en separat fil. Testfunktionen ska kunna anropas med parametrar som anger vilken sorteringsprocedur som ska användas (listMergeSort, listOptMergeSort eller arrayMergeSort), ett givet intervall (100-3000), antal testvärden som ska mätas i intervallet (minst 15), typ av data som ska användas i mätningen (slumpmässig, sorterad eller omvänt sorterad) och namnet på filen som ska skapas. Syntaxen för filen som testfunktionen skapar bör se ut som följer (för att GNU-plot ska kunna tolka innehållet i filen, se nästa punkt):

    100 0.2
    300 0.4
    500 0.8
    1000 1.5
    1500 4.3
    .
    .
    .

    Där den första kolumnen anger längden på indatat (arrayen/listan) och den andra kolumen sorteringstiden i sekunder.

  5. Använd GNU-plot för att grafiskt redovisa hur sorteringstiden beror av antalet element som ska sorteras. Det blir allså tre plottar för varje sorteringsprocedur (en för varje typ av indata). Totalt blir det nio plottar som ska redovisas. Redovisa plottarna genom att lämna in URL:en till var och en av dem (dvs placera tex plottarna i din public_html-katalog och ge oss URL till var och en av plottarna). Här följer några användbara kommandon för GNU-plot:
     

     

  6. Beskriv matematiskt hur sorteringstiden beror av antalet element som ska sorteras för var och en av de tre implementationerna.

  7. 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 (svara i procent i förhållande till den långsammaste).

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

Din redovisning ska innehålla

Din inlämning ska vara körbar. Dvs det som inte är kod ska vara bortkommenterat!

SML-dokumentation

Array.tabulate(n, f): int * (int -> '_a) -> '_a array
returns a new array of length n whose elements are f 0, f 1, ..., f (n-1), created from left to right. Raises Size if n<0 or n>maxLen.

Array.fromList(xs): '_a list -> '_a array
returns an array whose elements are those of xs. Raises Size if length xs > maxLen.

Random.newgen(): unit -> generator
returns a random number generator, taking the seed from the system clock.

Random.rangelist(min, max) (n, gen): int * int -> int * generator -> int list
returns a list of n integral random numbers in the range [min, max). Each number is created with the generator gen. Raises Fail if min > max.

Mosml.time (f) (arg): ('a -> 'b) -> ('a -> 'b)
applies f to arg and returns the result; as a side effect, it prints the time (cpu, system, and real time) consumed by the evaluation.

Inlämning

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.

ID:
PIN:
formulär för inlämning