FÖRBÄTTRINGSARBETE PÅGÅR!
TILDA, ÖVNING 4
Hashning, sortering, prioritetskö, bästaförstsökning
______________________________________________________________________
**********************************************************************
Tabell över ungefärliga tvåpotenser:
-----------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
-----------------------------------------------------------------------
2 4 8 16 32 64 128 250 500 1000 2000 4000 8000 16000 32000 64000 130000 ...
-----------------------------------------------------------------------
______________________________________________________________________
**********************************************************************
______________________________________________________________________
**********************************************************************
3 PERFEKT HASHFUNKTION
Hitta på en perfekt hashfunktion för atomer. Hur stor blir
hashtabellen?
______________________________________________________________________
Låt a=1, b=2, ..., z=26 och A=0, B=27, ..., Z=675 (25*27)
Då blir hash("A")=0 och hash("Zz")=701, så det behövs
702 platser i hashtabellen (dvs ca sex gånger mer än antalet element).
Ingen extra luft - det blir inga krockar!
I labb 5 ska ni inte göra en så här stor tabell utan istället
använda kvadratisk probning.
______________________________________________________________________
**********************************************************************
4 HÅLL REDA PÅ MEDIA (Tildatenta 030308)
Under gulfkriget var det väldigt svårt för armestaben att hålla reda
på alla TV-bolag som for omkring och rapporterade i öknen. För att
hålla reda på dem användes en hashvektor. Koden fungerade inte som
avsett och man har nu gett i uppdrag åt en f.d. tildastudent att
titta på en misstänkt del av koden:
from string import find
p = 100;
hashvektor = [0]*p
alfabet = "abcdefghijklmnopqrstuvxyz"
def put(tvbolagsnamn, tvbolag):
hashcode = 0
for i in range(len(tvbolagsnamn)):
alfanum = find(alfabet, tvbolagsnamn[i])+1
hashcode += alfanum
hashcode = hashcode % p
hashvektor[hashcode] = tvbolag
Vad är det för fel på koden? Beskriv hur man kan förbättra den.
Namnen på TV-bolagen kan antas bestå av högst tre bokstäver.
Det kommer inte att förekomma mer än 75 TV-bolag.
______________________________________________________________________
Det som gör att koden inte fungerar är att det inte finns någon
krockhantering.
hashvektor[hashcode] = tvbolag;
För att lösa det kan man använda t.ex. krocklistor eller linjär
probning. Linjär probning fungerar så att om det är upptaget på
den givna positionen så söker man tills man antingen hittar
nyckeln (den var redan instoppad sedan tidigare) eller tills
man hittar ett tomt element i vektorn.
Hashkoden är ganska korkat implementerad. Strängarna "AB" och
"BA" får samma värde.
alfanum = find(alfabet, tvbolagsnamn[i])+1
hashcode += alfanum
För att lösa det kan man vikta genom att multiplicera med
t.ex. 1, 100 och 10000.
Längden på hashvektorn är lite för liten och dessutom inget
primtal. Välj istället hashvektorns storlek till exempelvis 151
(dubbelt så stor som förväntade antalet element).
______________________________________________________________________
**********************************************************************
5 Nix till telefonförsäljning (TILDA-tenta 000603)
Föreningen för konsumentskydd vid marknadsföring per telefon
har startat ett register dit den som inte vill bli uppringd av
telefonförsäljare kan anmäla sig.
Till att börja kommer kontrollen att ske genom att företaget sänder
sin telefonlista till nix och får tillbaka en lista där de nixade
numren markerats.
Vilka av följande metoder kan föreningen använda sig av?
Vilken är bäst?
Binärträd, bloomfilter, hashtabell.
Ett framtida mål är att kontroll också skall kunna ske över internet.
Då måste kontrollen ske snabbt men man vill också försäkra sig om att
ingen ska kunna få ut en lista över alla nixade telefonnummer.
Vilken metod passar bäst för internet-kontrollen?
______________________________________________________________________
Just nu ringer många och anmäler sig till NIX-registret så det måste
gå lätt att lägga till nya.
Binärträd går snabbt att söka i men man måste se till att
det inte blir obalanserat när nya telefonnummer läggs till.
Bloomfilter är besvärligt att stoppa in nya nummer i.
Hashtabell se bloomfilter ovan.
Bloomfilter är det bästa alternativet för den framtida internet-
kontrollen. Man kan räkna med att många har registrerat sig så
snabb sökning är nödvändig.
Dessutom har bloomfilter fördelen att ingen användare kan få ut
telefonnummerlistan.
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 lista 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?
______________________________________________________________________
Tio genomletningar av listan tar 10*10 000 = 100 000 jämförelser.
Inmatning i trappan tar cirka N log N, alltså 130 000 jämförelser
och utplockning cirka 10 log N, alltså ytterligare 130 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 (Tildatenta 4 april 1997)
En miljon dumbolotter säljs var månad. För varje lott sparas
lottnumret och köparen i ett objekt. En lista med en miljon objekt finns
alltså i datorn vid dragningen, då tusen vinstnummer slumpas fram, ett
efter ett.
För varje nummer måste hela listan 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 listan, en gång för alla?
______________________________________________________________________
Ja. I en osorterad lista 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 N log N jämförelser, dvs
cirka 20 miljoner
(1000000*2log(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 (Tildatenta 3 mars 1996)
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 objekt gick ändå Tottes program lika fort,
eftersom han har superdator. Men med tiotusen objekt vann Tilda. Med
hur mycket?
______________________________________________________________________
k = en konstant
Selection sort (urvalssortering)
O(N2); t = k * N2
N = 10 000 ger t2 = k (10 000)2
N = 1 000 ger t1 = k (1 000)2
t2
-- = 100
t1
Tottes 10 000-objekts sortering tar alltså 100 gånger så lång tid
som 1 000-objekts sorteringen.
Merge sort
O(NlogN); t = k * N * 2logN
N = 10 000 ger t2 = k * (10 000) * 2log(10 000)
N = 1 000 ger t1 = k * (1 000) * 2log(1 000)
t2 10*13
-- ~ ---- ~ 13
t1 10
Obs! 2(13) = 8 192 så att 2log(10 000) ~ 13.
2(10) = 1 024 så att 2log(1 000) ~ 10.
Tildas 10 000-objekts sortering tar alltså 13 gånger så lång tid
som 1 000-objekts sorteringen.
Tildas 10 000-objekts sortering är alltså 100/13 = 8 gånger
så snabb som Tottes trots den långsammare datorn!
______________________________________________________________________
**********************************************************************
4 HOPPFULL SORTERING
Höjdhoppsfederationens databas över världens alla
höjdhoppstävlingsresultat består av objekt med bland annat fälten
datum, plats, höjd (cm), hoppare och rivit/klarat. På skivminnet
ligger objekten 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.
______________________________________________________________________
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 listan 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 listan.
______________________________________________________________________
**********************************************************************
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).
______________________________________________________________________
Vi vill sortera datumen och plocka ut det mittersta.
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ättningssortering 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 går inte att använda för att hitta medianen.
______________________________________________________________________
**********************************************************************
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?
______________________________________________________________________
Eftersom N=223 tar quicksort 9 000 000*23= 207 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 (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.
______________________________________________________________________
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 prioritetskö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 prioritetskö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
______________________________________________________________________
======================================================================