Datastrukturer (DAT037), lp2 2017

I denna labb får ni implementera en första ADT, mängd, en första datastruktur, dynamisk array, och en klassisk algoritm, binärsökning (binary search). Ni får repetera java-koncepten gränssnitt och klass och i del B också generics och standardinterfacet Comparable. Ni får mäta exekveringstid empiriskt och analysera programkods tidskomplexitet. Labben består av två delar, A och B.

A. Heltalsmängd

Ett enkelt sätt att implementera den abstrakta datatypen mängd är genom att lagra elementen i en array. Datastrukturen ska kunna lägga till element, ta bort element och avgöra om ett heltal är medlem i mängden.

Datastrukturen är tänkt att användas i tillämpningar där det sker relativt få förändringar av mängden men många förfrågningar om ett tal ingår i mängden. Implementationen ska alltså vara snabb på att avgöra om ett tal är medlem i en mängd, men behöver inte vara så snabb på att lägga till och ta bort element. Ett sätt att åstadkomma detta är att använda en array, lagra elementen sorterat och leta efter element med binärsökning. Detta ska ni göra.

I del A av labben ska ni implementera en datastruktur för en mängd av heltal. Implementera följande gränssnitt (filen IntSet.java):

public interface IntSet {
    public void add(int element);
    public boolean contains(int element);
    public void remove(int element); 
}

Interfacet har tre metoder som motsvarar ungefär de metoder med samma namn i standardgränssnittet Set.

Den klassen som implementerar gränssnittet ska heta BinSearchIntSet och ha en konstruktor utan argument (BinSearchIntSet()) som skapar en tom mängd. Elementen ska lagras i en primitiv array (typen ska vara int[]).

Ni ska implementera en dynamisk array, d.v.s. varje gång den är full ska kapaciteten (arrayens storlek) ökas multiplikativt (multipliceras med konstant större än 1, t.ex. 2). Den initiala kapaciteten kan sättas till något litet tal, t.ex. 1. Tänk på att skilja på den logiska storleken (mängdens storlek) och arrayens faktiska storlek (kapaciteten). Arrayens kapacitet behöver aldrig minskas (men får minskas om ni vill) vid borttagning av element.

Elementen ska lagras sorterade (i växande eller sjunkande ordning) i arrayen. Metoden contains ska använda binärsökning för att lokalisera den plats i array där det eftersökta heltalet måste finnas om det är medlem i mängden.

Om ni vill kan även add och remove lokalisera rätt plats med hjälp av binärsökning. Implementera i så fall en hjälpmetod som utför binärsökning och anropas av alla de tre metoderna. Att använda binärsökning för add och remove är valfritt för det påverkar inte väsentligt exekveringstiden för dem.

Klasser och metoder från standardpaket (förutom java.lang) eller andra källor får inte användas.

Manuell testning

Testa er implementation genom att skriva en körbar klass där en instans skapas och några operationer utförs och kontrollera sedan att resultaten av anropen till contains är de förväntade.

Exempelvis:

class ManTest {
    public static void main(String[] args) {
        IntSet set = new BinSearchIntSet();
        set.add(1);
        set.add(2);
        set.add(1);
        set.remove(3);
        set.remove(1);
        System.out.println(set.contains(1));
        System.out.println(set.contains(2));
        System.out.println(set.contains(3));
    }
}

Denna kod bör skriva ut

false
true
false

Testa några olika sekvenser av operationer.

Automatisk testning

Filen Test.java är ett program som automatiskt testar implementeringar av gränssnittet IntSet. För att testa er klass BinSearchIntSet kör ni programmet så här:

java Test BinSearchIntSet

Programmet kör tester i fem sekunder. Om en bugg hittas så visas den sekvens av operationer som exponerade buggen. Denna sekvens kan ni kopiera och köra som ett manuellt test. Det gör det enklare att avlusa programmet och komma underfund om vad som är fel.

Innan ni skickar in labben ska er BinSearchIntSet klara testprogrammet, d.v.s. det ska köras i 5 sekunder, avsluta och säga att inga fel hittats.

Empirisk mätning och analys av exekveringstid

Filen Benchmark.java är ett program som mäter den genomsnittsliga exekveringstiden för metoden contains i en implementering av IntSet. Den gör det för olika storlekar på mängden. För att mäta exekveringstiden för contains i er klass BinSearchIntSet kör ni programmet så här:

java Benchmark BinSearchIntSet

Att körningen avslutar med timeout leder i sig inte till att ni underkänns. Det är okej så länge ni får tillräckligt många tider för att kunna analysera utvecklingen (4-5 stycken).

Den givna filen LinSearchIntSet.java är en implementering av IntSet där linjärsökning används i contains. Ni kan beräkna exekveringstiderna för denna implementering genom att skriva

java Benchmark LinSearchIntSet

Begrunda hur förändringen av exekveringstiderna skiljer sig åt för de två implementeringarna då storleken på mängden blir stor.

Skriv en textfil med namnet komplexitet.txt som innehåller följande:

B. Generisk mängd

Nu ska ni implementera en generisk datastruktur för mängder, d.v.s. en datastruktur där elementtypen inte är fixerad till heltal. Skriv en klass med namnet BinSearchGenSet som implementerar följande gränssnitt (filen GenSet.java).

public interface GenSet<E> {
    public void add(E element);
    public boolean contains(E element);
    public void remove(E element); 
}

Liksom i del A ska klassen ha en konstruktor utan argument som skapar en tom mängd.

För att kunna lagra elementen sorterat behöver det finnas en ordning definierad för elementtypen, E. Kräv detta genom att specificera att E ska implementera standardgränssnittet Comparable. Detta kan man göra genom att ge klassen följande deklaration:

public class BinSearchGenSet<E extends Comparable<? super E>> implements GenSet<E>

Detta innebär att metoden compareTo kan användas i koden i klassen för att jämföra objekt av typen E. (Den komplicerade deklarationen <E extends Comparable<? super E>> förklaras i kursboken i sektion 1.5.5 andra upplagan och sektion 1.5.6 in den tredje.)

I denna implementation ska inte en primitiv array användas. De fungerar inte så bra tillsammans med generics. Använd istället standardklassen ArrayList. I del B slipper ni alltså hantera växande av arrayen samt insättning och borttagning på angivet index.

Metoden contains ska återigen använda binärsökning. Kopiera och anpassa koden ni skrev i del A för det generiska fallet.

Med undantag av ArrayList får klasser och metoder från standardpaket (förutom java.lang) eller andra källor inte användas.

Manuell testning

Testa er implementation manuellt på samma sätt som i del A. Ni kan t.ex. testa den med strängar som element, exempelvis börja med dessa programrader:

        GenSet<String> kurser = new BinSearchGenSet<>();
        kurser.add("DAT037");
        System.out.println(kurser.contains("DAT037"));

Automatisk testning

Filen BinSearchGenSetAsIntSet.java är en wrapper-klass som omvandlar er klass BinSearchGenSet till en IntSet. Använd denna för att köra det automatiska testet på er BinSearchGenSet. Skriv så här:

java Test BinSearchGenSetAsIntSet

Innan ni skickar in labben ska er BinSearchGenSet klara testprogrammet.

Empirisk mätning av exekveringstid

Jämför exekveringstiden för den generiska och ickegeneriska varianten av binärsökning. Skriv

java Benchmark BinSearchGenSetAsIntSet

och jämför med värdena för BinSearchIntSet. Tiderna bör bara skilja sig lite åt. Om inte så är något fel. Med "lite" menas i detta fall att tiderna inte skiljer sig mer än några gånger. Att BinSearchGenSet är dubbelt så långsam som BinSearchIntSet är helt okej. Ni behöver inte rapportera resultatet av jämförelsen, men måste se till att exekveringstiden för den generiska varianten är rimlig.

Givet material

Rapportering

Se till att ni noga följer de allmänna reglerna och riktlinjerna för laborationerna.

Innan ni skickar in ska ni se till att er kod klarar de automatiska tester som beskrivs ovan. När ni lämnar in kompileras och testas er kod automatiskt. Den testas med samma automatiska testprogram som ni har tillgång till.

Skicka in följande filer: