bild
Skolan för
elektroteknik
och datavetenskap

Uppgift 6 våren 2010

Uppgiften ska lämnas till din övningsledare på övningen den 5/3. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka. Börja i god tid.

För godkänt måste du ha gjort samtliga deluppgifter (utom den valfria). Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift

Läs den här texten om quicksort.

Skriftlig uppgift

Tidsmätning i Java

Klassen Stopwatch implementerar ett enkelt stoppur. Som du ser i TimingExample så är det lätt att mäta tiden det tar att exekvera ett kodavsnitt, men resultaten kan variera kraftigt mellan körningar.

Tänk ut och beskriv en bra strategi för tidsmätning i Java.

  • Hur hanterar du problemet att det ibland tar extra lång tid de första gångerna man kör ett kodavsnitt?
  • Hur hanterar du problemet att resultaten varierar mellan körningar?

Quicksort

Du ska implementera några varianter av quicksort i Java och mäta deras hastighet. Din algoritm ska sortera en vektor av heltal (int) och du ska testa följande varianter av algoritmen:

  • I stället för att använda ett fixt element i vektorn som pivot-element, prova en variant där pivot-elementet väljs slumpmässigt med hjälp av Javas slumptalsgenerator.
  • I stället för att avbryta rekursionen när vektorn består av högst ett element, prova en variant där delvektorer som innehåller högst k element sorteras med insättningssortering. (Insättningssortering har visserligen kvadratisk värstafallstid men är mycket enklare, och därmed snabbare, än quicksort för små datamängder.) En lämplig brytpunkt k bestämmer du med hjälp av ett experiment.

Glöm inte att testa alla fyra kombinationer: med och utan slumpmässigt pivot-element, samt med och utan insättningssortering. Tag dessutom med Javas egen sorteringsalgoritm Arrays.sort(int[]) i dina experiment.

Quicksort är ganska klurig att implementera. Var därför noga med att skriva bra och utförliga tester. Det underlättar kodning och felsökning. Återanvänd gärna testkoden och implementationen av insättningssortering från förra terminen.

Du ska testa att sortera vektorer av olika storlek (t.ex. från 1.000 till 1.000.000 element) och olika typer av data. Följande måste vara med

  • En vektor med slumpmässiga tal.
  • En vektor av redan sorterade tal.
  • En vektor av tal som är baklänges sorterade.
  • En vektor där alla tal är lika.

Om du vill, får du gärna prova även andra typer av indata och ytterligare optimeringar och varianter av algoritmen. Resultaten av dina experiment ska presenteras i en kort rapport.
  • Det ska framgå tydligt vilka tester du har gjort och vilka testdata du har använt.
  • Du ska beskriva hur du gjorde tidsmätningarna.
  • Du ska beskriva hur du beräknade brytpunkten där din algoritm byter till insättningssortering.
  • De experimentella resultaten ska presenteras på ett överskådligt sätt i diagramform. Tänk på att läsaren (dvs din övningsledare) snabbt ska kunna se vilka experiment du har gjort och vilka resultat du har kommit fram till. Man ska inte behöva läsa din kod för att förstå. (Däremot ska du som vanligt lämna in en utskrift av koden.)
  • Rapporten ska innehålla en diskussion där du försöker förstå och förklara dina experimentella resultat.

Implementationstips

I den här uppgiften ska du göra upprepade tester och mätningar på olika varianter av samma algoritm. För att slippa kodupprepning kan du med fördel definiera ett gränssnitt som beskriver en metod som sorterar en vektor av heltal. Till exempel så här:

public interface IntSorter {
    /**
     * Sorts the array into ascending numerical order.
     */
    void sort(int[] v);
}

Om du skriver dina sorteringsalgoritmer i klasser som implementerar IntSorter så kan du sedan lätt skriva test- och mätkod som arbetar på sådana objekt.

Det kan också vara praktiskt att representera indata med hjälp av en klass. Eftersom den här uppgiften är ganska stor så har jag gjort en del av jobbet. Klassen Data.java kan skapa alla typer av indata som behövs i uppgiften. Tag gärna en titt på main-metoden. Den innehåller exempel på hur man kan använda klassen.

Med hjälp av de här två datatyperna är det lätt att skriva en generell mätmetod. Till exempel så här:

/**
 * Measures the time to sort the data using the sorter.
 * Prints the results of the measurement to stdout.
 */
private void measure(IntSorter sorter, Data data) {
    if (isBroken(sorter)) { // returns true if sorter doesn't pass tests
       System.out.println(sorter + " is broken");
       return;
    }
    ...
    sorter.sort(Data.get());
    ...
    System.out.println("Sorted " + data + " with " + sorter);
    ...
}
Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2010-03-01