----------------------------------------------------------------------- 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 ... -----------------------------------------------------------------------
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.
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.
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).
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?
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.
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?
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.
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?
0.5*1000000 sökningar * 1000 vinstnummerSortering 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).
O(N2); t = k * N2Tottes 10 000-objekts sortering tar alltså 100 gånger så lång tid som 1 000-objekts sorteringen. Merge sort
N = 10 000 ger t2 = k (10 000)2
N = 1 000 ger t1 = k (1 000)2
t2
-- = 100
t1
O(NlogN); t = k * N * 2logNObs! 2(13) = 8 192 så att 2log(10 000) ~ 13.
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
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!
Vilken sorteringsmetod är bäst? Motivera utförligt.
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.
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).
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.
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.
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