Laboration 2: Aktiehandel

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. 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.

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

Om 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

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.

Ni kan själva välja om ni vill tillåta flera bud per säljare eller köpare (t ex flera förekomster av Bengt S i budlistan), men det ska framgå klart från dokumentationen vilket val ni gjort.

Felhantering

Ert program ska rapportera felaktiga ändringsorder genom utskrifter, t ex när en köpare eller säljare försöker ändra ett icke existerande bud. (För mer "oväntade" fel är det OK att kasta exceptions.)

Ytterligare krav

Implementation

• Laborationen ska implementeras i Haskell eller Java.

• Om aktiehandeln är stor är det viktigt att implementera prioritetsköerna effektivt. Ni ska därför implementera dem med följande datastrukturer:

  • Java: binära heapar.
  • Haskell: leftistheapar.¹

• 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.

• I både binära och leftistheapar 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.

  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 och jämförelser tar konstant tid. (Notera dock att värstafallstidskomplexiteten för att jämföra två strängar av längd l är Θ(l). Bra hashfunktioner för strängar brukar också vara linjära i längden.)

  Om ni väljer att använda Java så rekommenderar vi 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 vi antar att jämförelser tar konstant tid).

  Om ni väljer att använda Haskell så accepterar vi också att ni letar upp elementet genom sökning. Denna sökning måste ha komplexiteten O(n) i värsta fall (om vi antar att jämförelser tar konstant tid).

  Notera att ni inte behöver implementera en ändringsoperation motsvarande decreaseKey. Det räcker med en borttagningsoperation:

      delete :: (Ord p, Eq v) =>
                p -> v -> PriorityQueue p v -> Maybe (PriorityQueue p v)

• Er prioritetsköimplementation måste vara så generell att den kan användas både för köparkön och för säljarkön.

  Om ni använder Java ska prioritetsköns konstruktorer ta komparatorer som argument:

    public PriorityQueue(..., Comparator<? super E> comp, ...) {
        ...
    }

• Programmera modulärt. Stoppa inte in för mycket kod i en och samma metod/funktion.

Testning

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

Dokumentationen ska innehålla:

• En beskrivning (t ex en bild) av 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.

• En förklaring av varför den asymptotiska komplexiteten hos era operationer är den avsedda:

  • Insättning av nytt bud: O(log n), där n är orderbokens storlek.
  • Genomförande av köp: O(log n).
  • Ändring av bud: O(n) (eller O(log n) för den mer effektiva implementationen).

  Ni ska också ange vad den asymptotiska komplexiteten för att skriva ut prioritetsköerna är.

• En beskrivning av era testkörningar.

Tips

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

• En kort beskrivning av hur man implementerar en binär heap i en array.

• Kursboken har en implementation av binära heapar som ni får utgå från. Den kan dock inte kopieras rakt av: Weiss kräver att alla element ska implementera Comparable, men ni måste använda komparatorer.

  En tidigare assistent på den här kursen har skrivit en text om komparatorer.

• 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 ArrayListor istället för arrayer. Då slipper man också tänka på att öka arrayens storlek när den blir full.

• I labb 3 kommer ni att implementera ett reseplaneringsprogram med hjälp av Dijkstras algoritm. Den algoritmen använder sig också av en prioritetskö. Det ni lär er om prioritetsköer i den här labben kanske ni har nytta av i labb 3.