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 f n ä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.

Uppgiften

Er uppgift är att implementera ett program för aktiehandel enligt ovan, antingen i Haskell eller i Java. 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. (Det är förstås enkelt att skriva ett mer generellt program som hanterar fler aktieslag och där godtyckligt antal aktier kan hanteras i en order.)

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 följande datastrukturer:

• Java: binära heapar.
• Haskell: antingen nodbalanserade heapar eller binomiella heapar. (Notera dock att det kan vara svårt att implementera uppdateringsoperationen – decreaseKey – på ett effektivt sätt för de här datastrukturerna. För en funktionell prioritetsködatastruktur med en någorlunda effektiv uppdateringsoperation, se Hinzes prioritetssökköer, som tyvärr verkar vara något komplicerade att implementera.)

Lägga bud

En användare kan göra tre saker: köpa, sälja, samt ändra ett redan lagt bud. T ex 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

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 både binära och binomiella heapar gäller att insättning, samt borttagning av det högst prioriterade elementet, har värstafallstidskomplexiteten O(log n) (där n är köns storlek, och givet att jämförelser tar konstant tid). Tidskomplexiteten för att ändra en prioritet är O(n), eftersom man i värsta fall måste söka genom hela heapen efter det element vars prioritet ska ändras.

Om ni väljer att använda Java: För binära heapar går det att implementera ändringsoperationen med tidskomplexiteten O(log n) genom att använda en hjälpdatastruktur som håller reda på var i heapen ett visst element är lagrat. Man kan t ex använda en hashtabell som lagrar elementens positioner i heapen. På så sätt kan man hitta ett givet element i heapen med komplexiteten O(1) (om man har en perfekt O(1) hashfunktion). Vi rekommenderar att ni implementerar heapen på det här sättet, men den mindre effektiva metoden att leta upp elementet genom sökning accepteras också. Denna sökning måste dock ha komplexiteten O(n) i värsta fall.

Om ni väljer att använda Haskell: Vi accepterar att ni letar upp elementet genom sökning. Denna sökning måste dock ha komplexiteten O(n) i värsta fall.

Detaljer

• Ni kan själva välja om ni vill tillåta flera bud per säljare eller köpare, men det ska framgå klart från dokumentationen vilket val ni gjort.
• Om ni väljer att använda Java bör prioritetsköns konstruktorer ta komparatorer som argument:
  public PriorityQueue(..., Comparator<? super E> comp, ...) {...};
  Om ni väljer att använda Haskell så kan ni t ex definiera lämpliga Ord-instanser för de typer ni använder.
• På Wikipedia finns en kort beskrivning av hur man implementerar en binär heap i en array.

Format för indata och utskrift

Ert huvudprogram ska heta Lab2.java eller Lab2.hs. Det ska acceptera 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 (för Java) eller ./Lab2 BudLista (för Haskell) 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 eller ./Lab2 < Budlista.

Om ni vill får ni utgå från följande kod: Lab2.java eller Lab2.hs.

Felhantering

Test

Skriv själva några textfiler med budsekvenser för att testa att ert program fungerar. Gör tillräckligt många tester för att kontrollera att både säljbud, köpbud och ändringar fungerar. Under testningen kan det vara bra att skriva ut orderboken efter varje bud.

Det finns ett testprogram som bör användas. Lösningar som inte accepteras av testprogrammet kan underkännas utan närmare granskning av koden.

Dokumentation

• En beskrivning (t ex en bild) över alla objekt (om ni använder Java) eller viktiga funktioner (om ni använder Haskell) som visar hur de är relaterade till varandra.
• Den väl dokumenterade koden med API-kommentarer.
• Motivering till att den asymptotiska komplexiteten hos era operationer är den avsedda. D v s att genomförande av ett köp är O(log n), insättning av nytt bud är O(log n) och att ändring av bud är O(n) (eller O(log n) om ni gjort den mer effektiva versionen). Vad är den asymptotiska komplexiteten för att skriva ut prioritetsköerna?
• Resultaten av era testkörningar.

Ledning

• Ni ska implementera er egen prioritetskö. Ni får inte använda implementationen av prioritetsköer i Java Collections Framework, eller någon implementation på Hackage. Förutom att avsikten med denna labb är att lära sig hur man implementerar prioritetsköer, är implementationen i Java Collections Framework inte helt anpassad till er situation eftersom dess iterator inte löper genom elementen i prioritetsordning. En annan nackdel är att den inte är effektivt uppdaterbar.
• Boken har en implementation av binära heapar i kapitel 6.3 (från sidan 202 och framåt) som ni får utgå från. Vi rekommenderar dock att ni inte kopierar den rakt av. Notera att Weiss kräver att alla element skall implementera Comparable. Om man istället gör som rekommenderas ovan och använder komparatorer blir det lättare att själv styra hur element skall prioriteras i kön. Tänk även på att göra er kod såpass generell så att den kan användas både för säljarkön, köparkön och senare även för hållplatskön i labb 3.
• P g a begränsningar i Java går det inte att skapa en generisk array på följande sätt:
  E[] arr = new E[8];
  Man kan istället skapa en array av typen Object och sedan "casta" om den till rätt typ:
  E[] arr = (E[]) new Object[8];
  För att undvika detta problem kan man använda ArrayLists istället för arrayer. Då slipper man också tänka på att öka storleken på arrayen när den blir full.
• Tänk på att programmera modulärt! Stoppa inte in för mycket kod i en metod/funktion utan dela i stället upp den i flera metoder/funktioner.
• I labb 3 kommer ni att implementera ett reseplaneringsprogram med hjälp av Dijkstras algoritm. Denna algoritm använder sig också av en prioritetskö. Det ni lär er om prioritetsköer i den här labben kan ni ha nytta av i labb 3.