Sökning, indexering och symboltabeller

Att söka i en godtycklig samling

Linjärsökning

Binärsökning

Indexering

1. Hela sekvensen som ska hanteras får inte plats i primärminnet därför att posterna är för stora. Om ett index får plats i primärminnet går det mycket fortare att sortera eller söka i sekvensen genom sortera/söka i indexet och sedan läsa aktuell post på det postnummer som anges.
2. Antag att en samling vars poster innehåller tex personnummer, förnamn och efternamn ska struktureras på något bra sätt så att det går snabbare att söka i den. Antag vidare att vi betraktar personnummer som nyckel och sorterar samlingen efter dem. Då kommer det att gå snabbt att söka efter en post med ett visst personnummer men vill vi hitta ett visst förnamn eller efternamn finns det ingen annan utväg än att använda linjärsökning (se ovan). Detta kan lösas genom att upprätta tre olika index till samlingen, ett som sorteras efter förnamn, ett som sorteras efter efternamn och ett som sorteras efter personnummer. Nu går det, med hjälp av rätt index, att snabbt söka efter en viss post oavsett om förnamn, efternamn eller personnummer är givet.

Symboltabeller

• put(KeyType key, ValueType value)

Spara värdet value som associeras med nyckeln key .
• ValueType get(KeyType key)

Reurnera värdet som är associerat med nyckeln key.
• remove(KeyType key)

Ta bort posten som representeras av nyckeln key.

Benämningen symboltabell är inte helt vedertagen, ibland kallas de hashtabeller i stället, oberoende av hur de är implementerade.

Vi ska nu titta på några olika sätt att implementera en symboltabell. Den första frågan är varför inte sorteringsalgoritmerna i föregående avsnitt kan användas. Vi kom fram till sorteringsalgoritmer med T(n) = O(nlogn), varför inte använda någon av dem för att sortera nycklarna och sedan använda binärsökning för att hitta nycklar i samlingen? För det första för att den strategin inte alls löser problemet att lägga in och ta bort nycklar. För det andra för att det är för långsamt: Om vi sorterade om nycklarna varje gång en nyckel skulle sökas fick get T(n) = O(nlog(n)) och om vi alltid höll nycklarna sorterade skulle put och remove ha T(n) = O(n). Här kommer vi i stället att komma fram till en implementation som har T(n) = O(1) för alla operationer. Priset blir att nycklarna inte är sorterade och därför måste sorteras varje gång vi vill läsa igenom dem i sorterad ordning. Kontentan av detta resonemang är att sökning och sortering är oberoende operationer. Normalt väljer vi en datastruktur som gör att sökning går snabbt. När vi vill ha datat sorterat måste det sorteras med hjälp av någon lämplig sorteringsalgoritm.

Nu över till implementationerna av symboltabeller:

• Ett enkelt alternativ är med en lista , vanligtvis implementerad som en länkad lista. Varja element i listan är då en post i symboltabellen och innehåller både nyckel och värde. Operationen put kan utöras på konstant tid eftersom allt som behöver göras är att allokera minne för en ny nod, lägga in nyckel och värde i noden och placera den först i listan. Detta är oberoende av antalet element i listan. Operationen put får alltså T(n) = O(1). Operationerna get och remove har däremot T(n) = O(n) eftersom de kräver en linjärsökning i listan.


Denna implementation kan göras snabbare med en enkel form av cachning. Ofta är det så att en viss post används flera gånger i snar följd (kallas locality of reference). Detta innebär att det är större sannolikhet att nästa sökning blir efter den senast sökta posten än efter någon annan. Om vi söker efter poster genom att läsa igenom listan från början till slut går det snabbare att hitta en post ju längre fram i listan den står. Detta kan utnyttjas genom att till exempel flytta senast sökta post först i listan eller genom att låta sökta poster byta plats med föregående post eller genom att hålla reda på hur många gånger alla poster är sökta och hålla listan sorterad efter antalet sökningar. Denna typ av listor kallas self-adjusting lists. De bör användas sparsamt eftersom alla dessa optimeringar i sig är tidskrävande och ingen av dem förbättrar W(n), dvs hur smarta vi än är kan det alltid komma en sökning efter listans sista post.

• Ett annat alternativ är att implementera symboltabellen med ett binärt sökträd . I detta fall gäller för alla operationer att T(n) = O(log(n)). Dessutom går det snabbt att traversera alla poster i sorterad ordning eftersom de redan är sorterade i det binära sökträdet.
• Två helt nya datastrukturer som kan avändas till implementationen är hastabell och B-träd. Vi ska nu gå igenom dem.

Hashtabeller

ValueType hashTable[256];

ValueType get(byte key) {
    return hashTable[key];
}

void put(byte key, ValueType value) {
      hashTable[key] = value;
}

Hashfunktioner (Att beräkna hashtal)

Nu är det dags att börja skriva en hashfunktion. Den måste omvandla en godtycklig datatyp till ett heltal, vi låter hashtalen vara av typen int. Vi betraktar nycklarna som en följd av bytes för att vara oberoende av deras typ. Ett enkelt sätt att omvandla dessa bytes till en int är att betrakta den som ett tal med basen 256. Om en nyckel till exempel utgörs av strängen "Hammarby" kan vi omvandla den till en int genom att beräkna 'y' * 256 ⁰ + 'b' * 256¹ + 'r' * 256² + ... + 'H' * 256 ⁷ där 'x' är ASCII-koden för x. Denna enkla lösning fungerar tyvärr inte eftersom 256⁷ = (2 ⁸) ⁷ = 2⁵⁶ och en int knappast innehåller mer än 32 bitar. Tecknet 'H' påverkar alltså inte alls hashtalet varför till exempel "Hammarby" och "Gammarby" får samma hashkod. En bättre metod är att skriva om ett polynom på formen a₃X ³ + a₂X² + a ₁X¹ + A ₀X⁰ till (((a₃ )X + a₂)X + a ₁ )X + a₀. Detta har flera fördelar. För det första undviker vi stora delresultat (som till exempel 'H' * 256 ⁷) vilka direkt försvinner pga overflow. För det andra krävs inga beräkningar av potenser, värdet av ett n-gradspolynom beräknas med endast n multiplikationer och n additioner. För det tredje behöver vi inte veta strängens längd eftersom beräkningen använder tecknen från vänster till höger (detta under förutsättning att strängen slutar med någon sorts stopptecken). Tyvärr kvarstår problemet med overflow eftersom slutresultatet fortfarande inte får plats i en int. Detta löses genom att ta resultatet mod tableSize, där tableSize är sista index i hashtabellen och därmed största tillåtna hashtal. Genom att utföra operationen mod efter varje multiplikation/addition undviker vi att tidiga delresultat tappar betydelse genom att flyttas allt längre ut åt höger i hashtalet. Här kommer ett program med denna hashfunktion, SimpleHash.c . De undersökta nycklarna är alla textsträngar av angiven längd (endast små bokstäver används). Med 1000 olika hashkoder och 456976 olika nycklar ger hashfunktionen detta resultat:

There were 1000 hashCodes
There were 456976 different keys
There were 0 unused hashcodes
There were 455976 collisions, number of keys - number of hash codes = 455976
Max 568 keys got the same hashCode, number of keys / number of hashcodes = 456
Min 414 keys got the same hashCode, number of keys / number of hashcodes = 456

Ett problem med ovanstående funktion är att den långsamma operation modulo utförs en gång per byte i nyckeln. Vi kan snabba upp funktionen genom att endast utföta modulo en gång, precis innan hashtalet returneras. För att förhindra att tidiga tecken försvinner pga overflow multiplicerar vi med 32 i stället för 128 och gör dessutom xor på hashtalet från föregående varv i loopen. Detta innebär att nyckelns byte inte längre betraktas som ett tal med basen 256, men det saknar helt betydelse. Det viktiga är att alla bitar i nyckeln påverkar hashtalet. Denna typ av hashfunktion kallas rotating hash och är en relativt enkel algoritm som står sig väl jämfört med mer komplicerade algoritmer. Notera att denna algoritm resulterar i overflow om nyckeln är tillräckligt lång. Det gör inget så länge alla bitar i nyckeln påverkar hashtalet. En effekt av detta är dock att samma nyckel kan ge olika hashtal på olika typer av datorer. Här kommer ett test av denna algoritm, RotatingHash.c . Det blev lite bättre än föregående algoritm:

There were 1000 hashCodes
There were 456976 different keys
There were 0 unused hashcodes
There were 455976 collisions, number of keys - number of hash codes = 455976
Max 488 keys got the same hashCode, number of keys / number of hashcodes = 456
Min 414 keys got the same hashCode, number of keys / number of hashcodes = 456

En ofta föreslagen optimering (av exekveringshastigheten) för en hashfunktion av denna typ är att använda vänstershift i stället för multiplikation och xor i stället för addition.  Denna typ av optimeringar kan ge önskat resultat men bara om man har mycket god kännedom både den kompilator och den datorarkitektur som används. Dessutom kan funktionen bara optimeras för en viss datorarkitektur, det går inte att göra optimeringar av denna typ som alltid fungerar. Ett test av den optimerade rutinen OptimizedRotatingHash.c visar att exekveringstiden blir identisk med den ooptimerade funktionens exekveringstid på min dator. Det beror säkerligen på att kompilatorn själv gör denna typ av optimeringar. Detta bevisar en än gång optimeringens gyllene regel: Optimera inte utan att det behövs och heller inte utan att kunna verifiera resultatet .

Mycket mer teorier om och exempel på hashfunktioner finns på denna sajt, http://www.burtleburtle.net/bob/ , speciellt på den här sidan, http://www.burtleburtle.net/bob/hash/doobs.html .

Hur hantera krockar?

Den enklaste strategin att hantera krockar, linear probing, är att helt enkelt söka framåt i arrayen tills en ledig plats hittas. Antag att vi har implementerat hashtabellen som en array med tio platser och att det finns en post i cell nio:

Betrakta nu denna tabell:

En annan strategi för att hantera krockar är quadratic probing . Om det blir en krock undersöks då inte cellerna 1, 2, 3... steg framåt utan de som ligger 1², 2², 3 ² , ... steg framåt. Med denna metod undviks primär klustring eftersom andrahandsvalet för nycklar med olika hashkod alltid blir olika. Denna strategi klarar dock inte heller (av andra skäl) L > 0,5 varför vi inte vinner mer än 0,5 undersökta celler i genomsnitt vid put och get (enligt formeln ovan). Detta åstadkoms dessutom till priset av en krångligare algoritm. Därför används quadratic probing sällan.

En vanligare strategi är separate chaining. Här utgörs hashtabellen av en array av länkade listor. hashkoden talar om i vilken lista posten ska finnas. Vid put läggs ett element in på godtycklig plats i rätt lista. Vid get läses listan linjärt tills rätt post hittas, eller tills listan är slut om den sökta posten inte finns. L anger här listornas genomsnittliga längd. Antalet celler som mnåste undersökas blir för put oberoende av L medans det för get blir L om posten inte finns och ungefär 1 + L/2 om posten finns. Ett bra värde på L med denna startegi är 1,0. Ett lägre värde kräver mer minne och ger ingen större prestandaökning. Eftersom beroendet av L är linjärt och inte kvadratiskt som med linear probing innebär ett lite högre värde på L en väsentligt mindre prestandaförlust varför det är lättare att undvika rehashing med denna strategi. Detta är en populär strategi eftersom den är relativt lätt att implementera, har bra prestanda och kräver mindre minne än linear probing. Mindre minne gäller dock bara om posterna är stora jämfört med det extra minne som krävs för pekarna i de länkade listorna. Resonemanget om self-adjusting lists som fördes för det fall att hela symboltabellen implementerades med en lista gäller även här.

Notera innan vi lämnar hashtabellerna att oavsett implementation fanns det ingen operation vars komplexitetsfunktion var beroende av n, vilket var själva motivationen till hashtabellernas exeistens.

B-träd

Ett B-träd fungerar som ett binärt sökträd så tillvida att varje nod innehåller tillräcklig information för att vi ska veta i vilken av dess barn den sökta posten finns. Vidare krävs det (oavsett vilken typ av träd vi har) en diskaccess för att läsa (eller skriva) en nod eftersom vi måste tolka innehållet i en nod för att veta vilken nod som behöver underökas därnäst. Idén med ett B-träd är att desto fler barn en nod har desto grundare blir trädet och desto färre diskaccesser krävs det för att hitta en viss post.

Det finns många varianter på definitionen av B-träd men denna är vanlig:

• Alla poster lagras i löven, övriga noder innehåller endast nycklar.
• Noderna som inte är löv innehåller upp till M-1 nycklar för att avgöra i vilket av dess subträd en viss post finns. Nyckel i är den minsta nyckeln som finns i nodens i+1:a subträd.
• Alla noder som varken är rot eller löv har mellan M/2 och M barn.
• Roten har mellan 2 och M barn.
• Alla löv finns på samma djup och innehåller mellan L/2 och L poster.

Att lägga in och ta bort en nod i ett B-träd blir ganska komplicerade operationer men det är OK om antalet diskaccesser är lågt.  I stora drag blir algoritmerna som följer (det finns många variationer):

• Om vi ska lägga till en post och lövet där den ska ligga redan innehåller L poster delas helt enkelt lövet i två halvor som alltså kommer att innehålla cirka L/2 poster var. Att dela lövet kräver tre extra diskaccesser (två för att skriva de två halvorna och en för att uppdatera deras förälder). Detta är inte bra men vi kan acceptera det eftserom de resulterande löven inte innehåller mer än max L/2 + 1 poster. Det blir alltså minst L/2 skrivningar utan att dela löv för varje gång ett löv delas. Om delningen av lövet innebär att dess förälder innehåller M + 1 barn måste den också delas vilket leder till ytterligare två diskaccesser. Detta behöver dock bara göras högst en gång per M/2 * L/2 nya poster som läggs in. På samma sätt förstätter vi att dela noder så högt upp som behövs.
• Att ta bort en post går till på liknande sätt. Om det löv där posten låg får för få poster tar vi en post från ett angränsande löv. Om det angränsande lövet redan var nere på L/2 poster slår vi ihop de två löven i stället. Detta innebör att deras förälder får ett barn mindre. Om den då har för få barn upprepar vi samma procedur för föräldern.

Hur välja implementation av symboltabellen?

1. Om det är väldigt få poster, säg max 20, är en vanlig länkad lista bäst. De krångligare algoritmerna för de andra strukturerna ger ingen större prestandavinst för så få poster.
2. Om det finns fler poster måste vi välja mellan en hashtabell och ett träd. Hashtabellens fördel är att den är snabbare på att läsa, skriva och ta bort poster(O(1) jämfört med O(logn) för trädet) samt att den inte kräver kännedom om nycklarna. Trädets fördel är att det är snabbare på att läsa största eller minsta element och på att läsa alla elementen i sorterad ordning(O(1) eftersom posterna redan är sorterade jämfört med O(nlog(n)) för hashtabellen där en helt separat sortering krävs). Dessutom tappar trädet (speciellt B-träd) prestanda om inte nycklarna är unika. För att ha unika nycklar måste vi antingen kunna använda nycklarna direkt, utan att beräkna hashkod eller kunna utföra perfect hashing vilket kräver att nycklarna är kända. Valet avgörs alltså dels av om det är vanligt att sortera elementen dels av hur generella nycklar vi vill ha.
3. Om en hashtabell väljs är separate chaining lämplig eftersom det är både enkelt och effektivt. Främsta skälet att inte välja det är om posterna är väldigt små, ungefär som en pekare. Då kan det extra minnesutrymme som krävs för pekarna motivera att i stället välja linear probing. Om separate chaining väljs är det lämpligt att välja en self-adjusting list (tex att flytta senast accessad post först vilket är lätt att implementera) om vi vet att det råder locality of reference vid anropen av symboltabellens operationer.
4. Om vi inte väljer en hashtabell utan ett träd är det lämpligt att använda ett binärt sökträd om hela symboltabellen får plats i primärminnet och ett B-träd om den ska lagras externt.