Chalmers | Göteborgs universitet
Data- och informationsteknik

  DIT960 | LP4 | VT2012 Datastrukturer DV[an error occurred while processing this directive]: Lab 2

[Kursinformation] [Schema] [Övningar] [Laborationer] [Tentamen] [Fire] [Kursutvärdering]

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

Laboration 2. Aktiehandel

Inledning

På en aktiebörs handlar man med aktier i stora bolag. Man kan göra detta via internet om man har en banktjänst för aktiehandel. Man kan där ange om man vill köpa eller sälja ett visst aktieslag och ange det pris man är villig att betala.

Antag att du vill köpa aktier i Ericsson för 70 kr styck. Ditt bud kommer då att jämföras med säljkursen, dvs det lägsta pris någon säljare är villig att acceptera för sina Ericssonaktier. Om säljkursen är 70 kr eller lägre accepteras ditt bud och du får köpa aktierna för 70 kr. Man kallar en sådan genomförd affär ett "avslut". (Det är förstås oklokt att bjuda över lägsta säljkurs, men även sådana bud måste hanteras.) Om säljkursen är högre än 70 kr kommer ditt bud att läggas i Ericssons "orderbok" där alla ej genomförda bud registreras. Om det senare kommer in en ny säljare som är villig att sälja för 70 kr kommer ditt köp genomföras då i stället.

För att underlätta lösningen av uppgiften så ges här en beskrivning för hur ni bör gå till väga för att lösa den:

Översikt av Uppgiften

Er uppgift är att implementera ett Javaprogram för aktiehandel enligt ovan. För enkelhets skull behöver ni bara kunna handla med ett aktieslag och alla bud avser bara en aktie i taget. Det finns däremot flera olika säljare och köpare. Buden ska anges i hela kronor.

Orderboken består av två prioritetsköer: en för säljare och en för köpare. I prioritetskön för säljare innebär lägre pris högre prioritet. I prioritetskön för köpare innebär däremot högre pris högre prioritet. Om aktiehandeln är stor är det viktigt att implementera dessa prioritetsköer effektivt. Du ska därför implementera dem med (binära) heapar.

Lägga bud

En användare kan göra tre saker: köpa, sälja, samt ändra ett redan lagt bud. Exempelvis skriver vi 

  Ada K 70

om Ada vill köpa aktien för 70 kr. På motsvarande sätt skriver vi 

  Bengt S 71

om Bengt vill sälja aktien för 71 kr, 

  Bengt NS 71 70

om Bengt ändrar sitt säljbud från 71 till 70 kr (NS = ny säljkurs), och 

  Ada NK 70 72

om Ada ändrar sitt köpbud från 70 till 72 kr (NK = ny köpkurs).

Registrera avslut

Ni får anta att indata är sådant att varje person har som mest ett enda bud i prioritetskön.

I det fall att ett bud accepteras ska ert program registrera köpet på kommandoraden. I ovanstående fall ändrade Bengt sitt säljbud till 70 kr vilket matchar Adas köpbud. Då ska programmet skriva: 

  Ada köper från Bengt för 70 kr

Skriva ut orderböcker

Efter det att ditt program skrivit ut alla genomförda köp, ska det till slut skriva ut orderboken. Säljare och köpare ska listas i prioritetsordning enligt följande exempel: 

  Orderbok:
  Säljare: Cecilia 70, Bengt 71, David 73, Erika 77
  Köpare: Ada 69, Fredrik 68, Gustaf 68

Ändring av prioriteten

I en binär heap har båda operationerna insättning och borttagning av högst prioriterat element värstafallskomplexiteten O(log n) (där n är köns storlek, jämförelser tar O(1) tid, och arrayen inte ändrar storlek). Att ändra en prioritet tar O(n) eftersom man i värsta fall måste söka genom hela heapen efter det element vars prioritet ska ändras.

Ni ska dock åstadkomma O(log n) även för ändringsoperationen genom att använda en uppdaterbar heap. I en uppdaterbar heap har men en hjälpdatastruktur som håller reda på var i heapen ett visst element är lagrat. Ni ska använda en hashtabell som lagrar elementens positioner i heapen. På det sättet kan man hitta ett givet element i heapen med komplexiteten O(1) (om man har en perfekt O(1) hashfunktion).

Format för indata och utskrift

Ert huvudprogram ska heta Lab2.java. Det har en parameter Budlista som är en fil med en lista av bud enligt ovanstående format med ett bud per rad: 

  Ada K 70
  Bengt S 71
  Cecilia S 70
  Bengt NS 71 72
  David K 72
  Erik S 73
  Frida S 71
  Gustaf K 69
  Hanna S 72

När ni skriver java Lab2 Budlista ska ert program skriva ut en lista av avslut följt av aktuell orderbok enligt följande format: 

  Ada köper från Cecilia för 70 kr
  David köper från Bengt för 72 kr

  Orderbok:
  Säljare: Frida 71, Hanna 72, Erik 73
  Köpare: Gustaf 69

Det ska också gå att skriva: 

  java Lab2 < Budlista

Filens innehåll finns då i System.in.

Testning

Det finns ett testprogram som genererar indata (listor med kommandon av ökande storlek) för ert program. Var noga med att använd detta för att testa ert program efter varje steg innan ni går vidare!

För att vara säkra på att ert program fungerar så ska ni klara minst 2 miljoner testfall. Anledning för att köra så många test är att testen som skapas bygger listor med kommandon av ökande storlek där antalet testfall växer exponentiellt med längden av listan. Så ju fler testfall som testas, desto längre prioritetsköer skapas av ert huvudprogram. Om ni kör få testfall, så kan det hända att ni missar fel som endast uppstår för längre prioritetsköer.

Tänk på att testprogrammet endast gör det troligt att det inte finns något fel i er kod. Eftersom ni inte kan köra oändligt många testfall så bör ni tänka igenom er kod noga och inte gissa er till tills testprogrammet inte hittar några fel.

Spara testprogrammet (testing.jar) i samma katalog som ni har er kompilerade java-kod (dvs .class-filerna). Starta sedan en terminal och i samma katalog kör: 

  java -ea -jar testing.jar lab2test.Lab2GenTest Lab2

Om testprogrammet verkar hänga sig (ger inga utskrifter) så har ni antagligen en oändlig loop i ert program. Kör då istället: 

  java -ea -jar testing.jar -v 5 lab2test.Lab2GenTest Lab2

Det sista testfallet är då det fall som programmet hänger sig för.

Andra sätt att använda programmet

Det finns ett flertal flaggor som kan användas. För att se dem, kör: 
  java -ea -jar testing.jar --help

  java -ea -jar testing.jar lab2test.Lab2GenTest "Lab2 --help"

Ni kan t.ex hoppa över tidiga testfall med 

  java -ea -jar testing.jar -s 2000000 lab2test.Lab2GenTest Lab2

Om ni har angett ett paketnamn för er kod, så måste ni ange paketnamnet så att testprogrammet hittar er kod, t.ex: 

  java -ea -jar testing.jar lab2test.Lab2GenTest lab2.Lab2

Det går också att köra: 

  java -ea -jar testing.jar -t -1 lab2test.Lab2GenTest "lab2.Lab2 -p"

för parallell testning. Detta testar eventuellt snabbare genom att köra flera testfall parallellt. Detta använder metoden pureMain(String[]) som tar en array med alla kommandon och returnerar en sträng med all utdata istället för att skriva till System.out. Användning av System.out/System.err bör i detta undvikas helt eftersom det då blandas mellan olika test och kan vara missvisande.

Ledning: Steg 1: komma igång

Ert program ska bestå av följande klasser:

Lab2

Detta är ert huvudprogram som det har beskrivits ovan. Utgå ifrån Lab2.java. Förstå ungefär vad den existerande koden gör (och vad de bitar som saknar ska göra) innan ni fortsätter. Ni kan vänta med att fylla i de bitar som saknar tills ni har börjat på er prioritetskö. Ni får ändra på den existerande koden hur mycket ni vill.

(en klass för bud)

Denna klass beskriver ett bud. Ni kan utgå ifrån Bid.java.

Se till så att inga instanser av klassen går att ändra (alla instansvariabler ska vara "final"). t.ex strängar går inte att ändra. se boken sidan 620. Implementera inte Comparable, använd separata komparatorer istället för att jämföra bud. Se nedan.

(två komparatorer)

Dessa är till för att beskriva prioriteten av elementen i era två prioritetsköer. Ni behöver en för säljare och en för köpare. compare är vanligtvis kompatibel (se compare) med equals, alltså att compare ger 0 om och endast om equals ger true, men då måste ni också jämföra strängar. Detta behövs inte för er prioritetskö, utan det räcker med att jämföra priset.

(en prioritetskö)

Ni måste använda en ArrayList med generiska element. Använd alltså inte en array. Konstruktorerna måste ta en komparator som parameter. Komparatorn använder ni för att bestämma prioritetsordningen av elementen i heapen.

Ni bör läst igenom kapitel 6.5 innan ni implementerar er prioritetskö. Ni kan också läsa om heapar på wikipedia. Utgå gärna från koden i kursboken på sidan 339-341. Ni behöver inte skriva av koden, utan hittar den på Student Companion Site, men kom ihåg att ändra paketnamn, klassnamn, författare, osv.. Ta bort metoden compare som följer med och använd endast komparatorn ni får in, eftersom ni inte kommer använda compareTo.

Ni måste inte implementera något specifikt gränssnitt, men ni måste på valfritt sätt minst implementera:

..eftersom detta behövs i ert huvudprogram.

För att implementera en oeffektiv uppdatering så söker ni igenom hela heapen efter det element vars prioritet ska ändras. Välj vad ni vill göra då ni inte hittar det. Om ni hittar det, så byt ut elementet mot det nya och jämför sedan med parent/left/right för att återställa heapegenskapen. Det blir lättare om ni skapar 2 hjälpmetoder som flyttar ett element neråt (eller uppåt) tills elementet är på en lämplig plats. Ni flyttar alltså ut den kod ni redan har för att skapa dessa metoder. De kan sedan användas när ni tar ut det minsta respektive sätter ett nytt element, och de kan också användas när ni uppdaterar. På detta sätt behöver ni inte implementera en speciell algoritm för att flytta ett element när ni uppdaterar, utan det räcker med att endast jämföra med parent för att ta reda på om ni ska använda algoritmen för att flytta uppåt eller neråt.

Ledning: Steg 2: klassinvariant, testning, och debugging

klassinvariant

En bra idé är att beskriva den klassinvariant som måste uppfyllas och testa att den håller i början och slutet av varje anrop till publika metoder (vilket är exakt då den måste hålla). Använd assertions för att testa klassinvarianten. För att assertions ska testas när ni kör er kod så måste ni ange flaggan -ea, annars testas de inte.
Ni kan visa tillståndet av heapen liknande som i lab1 om er invariant inte håller.

Exempel på hur ni kan testa er invariant: 

       public void insert(E element){
                assert invariantCheck() : showHeap();

                ... // inserting the element and restoring the invariant

                assert invariantCheck() : showHeap();
       }

       private boolean invariantCheck(){
                Set<E> vs = new HashSet<E>();
                for(int i=1 ; i<heap.size() ; i++){
                        E e = heap.get(i);
                        if( e == null || vs.contains(e) )return false;
                        vs.add(e);
                }
                return true;
        }

        private String showHeap(){
                // return description of heap contents
        }

invariantCheck beskriver den invariant som ni vill ha för er prioritetskö. T.ex så borde heapordningen uppfyllas.

I koden ovan kommer showHeap att anropas när invarianten inte håller. Ni bör implementera denna metod så att den visar hur er heap ser ut, så att ni kan se hur heapen ser ut och därmed lättare komma på vad som gick fel. Alternativt så kan ni istället skriva assert invariantCheck();, som innebär att ni endast får ett exception om att invarianten inte håller.

För att använda HashSet (och också HashMap som ni kommer använda senare) måste ni implementera hashCode i Bid så att hashkoden är samma när equals säger att två bud är samma (se hashCode). Om detta inte stämmer så får ni konstiga fel när ni använder HashMap eller HashSet. Tänk på hur hashCode används där. Det räcker med att använda hashCode för strängar i er hashCode.

testning

Skriv en fil med indata till ert program och se om det verkar fungera. Använd sedan testprogrammet för att se om ert program fungerar. Om testprogrammet ger indata som ert program ger fel utdata för, ger ett oväntat exception, eller då er klassinvariant inte håller, så måste ni analysera vad som gått fel.

debugging

Ni kan göra utskrifter för debugging var som helst i er kod, men använd då System.err (inte System.out). Testprogrammet skriver ut allt efter varje test. Hittar ni inte lätt ett fel som testprogrammet ger så spara den indata som testprogrammet antav i en fil och kör ert program själva med filen som argument. Använder ni eclipse så kan ni ange filens namn som argument, och använda debuggern som finns i eclipse för att stega igenom programmet.

Ledning: Steg 3: förbättrad insättning/uttagning

Nu när ni har testat er kod och vet att den fungerar, så ska ni förbättra den.

Algoritmen i boken sätter först in det nya elementet sist i heapen och bubblar sedan elementet uppåt tills heapegenskapen är återställd. Detta leder till att det sker en swap-operation för varje steg uppåt i heapen. En alternativ algoritm är att vid insättning inte sätta in elementet, utan att endast jämföra det elementet man vill sätta in med elementen i heapen tills man har hittat det stället i heapen där man vill ha elementet. Implementera denna algoritmen (för både insättning och uttagning) och använd den istället för koden ni fick ifrån boken.

Följande pseudo-kod beskriver denna uppdatering för insättning. 

algorithm insert(element)
  increase size of heap by one

  # declare variable for the hole index
  var hole ← last index of heap

  # loop until an appropriate location in the heap has been found
  while hole is not the first index
    # declare variable for the parent index
    var parent ← (hole − 1) / 2

    # we know parent index is a valid and above the hole index
    assert (0 ≤ parent) and (parent < hole)

    # stop when the element can be written at the current hole index
    if heap[parent] ≤ element then end loop

    # move the parent element down
    heap[hole] ← heap[parent]
    hole ← parent
  end while

  # write element at the hole index
  heap[hole] ← element

När ni tar ut det minsta gör ni på liknande sätt. Istället för att sätta in det sista elementet först får ni ett hål på index 0 och ett element (ta ut det sista) som ni ska jämföra med.

Ledning: Steg 4: effektiv uppdatering

Ni ska nu implementera en effektiv uppdatering. Använd en Map<E,Integer> (se Map) för att hålla reda på var varje element ligger i heapen. Ni ska använda HashMap för detta.

Varje gång ni flyttar ett element i heapen så måste ni uppdatera er Map. Då kommer den alltid innehålla rätt index för varje element. När ni uppdaterar behöver ni nu bara fråga er Map för att ta reda på var de gamla elementet ligger istället för att leta igenom hela heapen på linjär tid.

Ni bör nu också hitta på en starkare invariant genom att också kolla att er Map överenstämmer med er heap på lämpligt sätt. Tänk på hur de förhåller sig till varandra. Alla element i er Map måste finnas med i heapen, och alla element i heapen måste finnas med i er Map.

Inlämning

Innan ni laddar upp era filer till fire och skickar in, se till att er kod uppfyller följande krav:

Extrauppgifter

Här är några extra uppgifter för de som har tid och vill lära sig mer:

 

Denna fil ändrades senast: 2012-04-20, kl 09.51