TILDA, ÖVNING 4 26 sept 2007 (Öjvinds grupp)

1 WEBBTOPPEN (Tildatenta 21 mars 1998)

Vissa webbsidor räknar hur många besökare dom har eftersom välbesökta webbsidor ger prestige. Du får i uppdrag att skapa webbtoppen, ett program som för varje dag läser av räknarna för tiotusen webbsidor och sedan publicerar dagens tio i topp. Din första tanke är att spara talen i en vektor med längd tiotusen, leta fram och skriva ut segraren, nollställa segraren och göra detta tio gånger. Hur många jämförelser skulle krävas för denna algoritm? Din andra tanke är att spara talen i en trappa (heap) och sedan ta ut och skriva ut tio tal ur trappan. Hur många jämförelser kan det då bli frågan om? Din tredje tanke är att det borde räcka med en trappa med plats för tio tal. Hur skulle man då göra och hur många jämförelser skulle krävas?

2 LÖNAR SEJ SORTERING

En miljon dumbolotter säljs var månad. För varje lott sparas lottnumret och köparen i en post. En vektor med en miljon poster finns alltså i datorn vid dragningen, då tusen vinstnummer slumpas fram, ett efter ett. För varje nummer måste hela vektorn letas igenom, eftersom den är osorterad. Hur många jämförelser får man räkna med totalt? Lönar det sej att först sortera vektorn, en gång för alla?

3 BILLIG STANDARD SELECTION

Tilda och Totte skrev var sin sorteringsprocedur. Tilda valde en utsökt merge sort medan Totte tog en standard selection sort. När dom provkörde med tusen poster gick ändå Tottes program lika fort, eftersom han har superdator. Men med tiotusen poster vann Tilda. Med hur mycket?

4 HOPPFULL SORTERING

Höjdhoppsfederationens databas över världens alla höjdhoppstävlingsresultat består av poster med bland annat fälten datum, plats, höjd (cm), hoppare och rivit/klarat. På skivminnet ligger posterna i datumordning, men man vill sortera om dom i resultatordning, nämligen klarade hopp före rivna och höga hopp före låga. Vilken sorteringsmetod är bäst? Motivera utförligt.

5 TJUGONDAG KNUT KASTAS JULEN UT (Tildtenta 16 januari 2001)

För att kontrollera sanningen i detta talesätt har man i en fil samlat tre miljoner datum för svenska julgranars utkastning. Man vill veta mediandatum, alltså det datum då hälften av granarna slängts ut, ut, ut och hälften ännu står gröna och granna i stugan. Rangordna följande sex föreslagna metoder efter deras effektivitet. Binärsökning, hashning, insättningssortering, distributionsräkning, djupet-först-sökning, trappsortering (heap sort).

6 SKATTEREGISTRET

Riksskatteverkets databas med nio miljoner svenskar finns sorterad på efternamn. Man vill sortera om den på personnummer. Hur många jämförelser krävs med quicksort? Hur många med den bästa metoden?

7 BÅTFLYTT (Tildatenta 6 april 2002)

Under en seglingstävling vill varje båt hitta den snabbaste vägen till målet. Problemet är att en segelbåt inte kan segla hur som helst och att den seglar olika snabbt beroende på vindriktning och styrka. Antag att havet förenklat består av en massa jämnt fördelade punkter med information om vindstyrka, vindriktning och vilka punkter som finns runt om. Beskriv en algoritm som på ett så effektivt sätt som möjligt tar reda på vilka punkter som ligger utefter den snabbaste seglingsvägen givet en startpunkt och en slutpunkt. Båtägaren är orolig att hans miljövänliga bottenfärg ska nötas bort och vill därför istället ta den väg som är kortast (dvs minst antal steg). Förklara vad som behöver ändras i din föregående algoritm.

8 SILUETTPROBLEMET

Om man på håll betraktar en stad i skymningen ser man inte dom enskilda byggnaderna utan bara siluetten, den yttersta konturen, avteckna sig mot himlen. Hitta på en algoritm som givet varje byggnads kontur beräknar stadssiluetten. < Anta att alla byggnader står på x-axeln, är rektangulära och beskrivs av tripplar (left, height, right) där left är vänsterväggens x-koordinat, right är högerväggens x-koordinat och height är höjden (y-koordinat).

Inmatningen består av n stycken tripplar, ordnade i stigande värden på vänsterväggar, och utmatningen ska vara en rad med x,y-koordinater som från vänster till höger beskriver siluetten. x-värdena anger var på x-axeln siluetten går vertikalt och y anger på vilken höjd siluetten fortsätter efter x-värdet. Den sista y-koordinaten är alltid noll eftersom alla byggnader står på x-axeln.

Exempel: Om n=8 och inmatningen är
(1,11,5) (2,6,7) (3,13,9) (12,7,16) (14,3,25) (19,18,22) (23,13,29) (24,4,28)
så blir utmatningen 

     x= 1  y= 11
     x= 3  y= 13
     x= 9  y= 0
     x= 12 y= 7
     x= 16 y= 3
     x= 19 y= 18
     x= 22 y= 3
     x= 23 y= 13
     x= 29 y= 0

LÖSNINGAR

1 WEBBTOPPEN

Tio genomletningar av vektorn tar 100 000 jämförelser. Inmatning i trappan tar cirka N log N, alltså 130 000 jämförelser och utplockning cirka 20 log N, alltså ytterligare 260 jämförelser. Det smarta är att ha en tioplatsers min-heap! Överst ligger då det tionde i ordningen av alla tal man sett och det är ju det man ska jämföra varje tal med för att se om det ska in bland dom tio bästa. Med normal tur blir det inte så ofta man ska byta ut tionde talet, så antalet jämförelser blir bara drygt tiotusen.

2 LöNAR SEJ SORTERING?

Ja, i osorterad vektor krävs cirka en halv miljon jämförelser för varje sökning, dvs totalt en halv miljard (0.5*1000000 sökningar * 1000 vinstnummer). Sortering med quicksort kräver cirka 1.5 N log N jämförelser, dvs cirka 30 miljoner (1.5*1000000*log2(1000000)) Sedan tar varje binärsökning (O(logN)) bara tjugo jämförelser, dvs tjugotusen totalt (20 jämförelse/vinstnummer * 1000 vinstnummer).

3 BILLIG STANDARD SELECTION


k = en konstant
Selection sort
O(N2); => t = k * N2
N = 10 000 => t2 = k (10 000)2
----------------
N = 1 000 => t1 = k (1 000)2
=> t2/t1 = 100
Tottes 10 000-posters sortering tar alltså 100 gånger så lång tid som 1 000-posters sorteringen.
Merge sort
O(NlogN); => t = k * N log2N
N = 10 000 => t2 = k (10 000) log2(10 000)
---------------------------
N = 1 000 => t1 = k (1 000) log2(1 000)

=> t2/t1=13
Obs! 213 ~ 10 000 så att log2(10 000) ~ 13. 210 ~ 1 000 så att log2(1 000) ~ 10.

Tildas 10 000-posters sortering tar alltså 13 gånger så lång tid som 1 000-posters sorteringen. Tildas 10 000-posters sortering är alltså 100/13 = 8 gånger så snabb som Tottes trots den långsammare datorn!

4 HOPPFULL SORTERING

De hopp som finns är grovt sett 100-300 cm, dvs det finns bara några hundra olika höjdvärden (distributioner) i hoppfilen. Antalet registrerade hopp är väldigt många fler än antalet höjdvärden (distributioner) och då är distributionsräkning bästa sorteringsalgoritmen. Tar vi hänsyn till rivit/klarat får vi dubbelt så många distributioner. Algoritm: Läs igenom filen två gånger, första gången för att räkna hur många hopp det finns av varje rivit/klarat plus höjd. Sedan avsätter man lagom stort segment av vektorn för varje rivit/klarat plus höjd och vid andra genomläsningen av filen kan varje hopp sättas in på rätt ställe i vektorn.

5 TJUGONDAG KNUT KASTAS JULEN UT

Distributionsräkning är bäst (~N) eftersom det bara finns 365 olika datum. Trappsortering är näst bäst (~NlogN) och man kan avbryta när hälften sorterats. Insättning fungerar också (~N2). Hashning är nästan oanvändbart; man bör i så fall vara säker på att hashfunktionen inte kan ge krockar. Binärsökning och djupet-först-sökning är det bara att glömma.

6 SKATTEREGISTRET

Eftersom N=223 tar quicksort 1.5*9000000*23= 300 miljoner jämförelser. Radixsortering (gå igenom alla, dela upp i tio buntar efter sista siffran, lägg samman, gör om med näst sista siffran etc) tar 10*9000000= 90 miljoner. Man kan faktiskt strunta i sista siffran eftersom den är checksiffra. Det finns inte två pnr som bara skiljer sej i den siffran.

7 BÅTFLYTT

Använd bästaförstsökning med en prioritetskö som prioriterar på lägsta seglade totaltiden. Låt varje nod innehålla total seglingstid samt ha en faderspekare (för rekursiv utskrift av vägen då lösning hittats). Princip för genomgång av problemträdet: 1.Lägg startpunktsnoden med totaltiden noll och tom faderspekare i priokön. 2.Upprepa punkterna 3-4 så länge kön inte är tom. 3.Plocka ut en fadersnod ur kön. Om detta är slutpunkten, skriv ut vägen rekursivt och avsluta. 4.Generera en son i taget genom att för varje punkt runt omkring fadersnoden skapa en sonnod med seglingstiden ökad beroende på vindstyrka, vindriktning och placering i förhållande till fadersnoden. Lägg in sonnoden i priokön. Om dumbarnskoll ska utnyttjas måste det ta hänsyn till både punkten och totala seglingstiden till den punkten. Alla söner med sämre tider till samma punkt är då dumsöner. På det viset slipper algoritmen besöka samma punkt flera gånger - den blir effektivare. Eventuellt krävs någon snabb uppslagning av punkternas information, t ex med en hashtabell som hashar på punkternas nummer eller position. Noderna kan innehålla lägsta tid som uppnåtts för att tillåta dumbarnkoll utan att kräva extra minne. För kortaste vägen, använd istället bredden först med en vanlig kö och blanda inte in totala seglingstiden i varje nod. I detta fall måste vi göra dumbarns koll för att sökningen ska bli effektiv. Datastrukturer: Prioritetskö / kö Hashtabell Noder med seglingsdata

8 SILUETTPROBLEMET

Det här knepiga problemet kan vi lösa med hjälp av två heapar. Den ena är en min-heap, som ser till att vi får ut husväggarnas koordinater i ordning från minsta (vänstraste) till största (högraste) x-värde. Den andra är en max-heap som hjälper oss att hitta det just nu högsta huset.

Algoritm:

Programkod 

from maxheap import MaxHeap
from minheap import MinHeap

class House:
    left=None
    height=None
    right=None

    def __init__(self, left, height, right):
        self.left=left
        self.height=height
        self.right=right

def readHousesTo(xheap):
    ins=raw_input("Vilka hus finns? ").split()
    for h in ins:
        h=h.strip("()")
        hs=h.split(",")
        house=House(int(hs[0]), int(hs[1]), int(hs[2]))
        print house
        xheap.put(house, house.left)

xheap = MinHeap(20)
yheap = MaxHeap(20)

readHousesTo(xheap) # Läs in husen

x=0
y=0
while not xheap.isempty():
    house = xheap.get()
    if house.left > x:  # Hus med vänstervägg utplockat
        x=house.left
        if house.height > y:
            y=house.height
            print "x=", x, "y=", y
        xheap.put(House(house.left, house.height, house.right), house.right)
        yheap.put(House(house.left, house.height, house.right), house.height)

    else: # Hus med högervägg utplockat
        if house.height == y: # Det var det just nu högsta huset
            # Sök efter det hus som blir högst nu
            x=house.right
            while not yheap.isempty() and yheap.top().right <= x:
                yheap.get()     # Ta bort hus som ligger...
                                # ...till vänster om x
            if yheap.isempty():
                y=0
            else:
                y=yheap.top().height
            print "x=", x, "y=", y