Använda strängar som ID

[Mattias Gustavsson]

Intressant, är alltid kul med saker som utmanar gamla "sanningar"... Jag har själv bara accepterat primtal som "the way to do it" när det gäller hash-tabeller, men körde ett par tester efter att ha läst det där...

Med min StringId-klass, när jag kör med ordlista, så lagras 3921 unika strängar i tabellen.
Om man gör antalet slots litet, strax över 4000, så borde man få många kollisioner - jag testade med både tabellstorlek på 4096 (inget primtal) och 4093 (primtal):

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. slots:4096  collisions:1887
3. slots:4093  collisions:1844
4.  

och så provade jag att göra en dubbelt så stor tabell, vilket borde ge färre kollisioner - här använde jag storlekarna 8192 (inget primtal) och 8191 (primtal)

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. slots:8192  collisions:896
3. slots:8191  collisions:900
4.  

Jag testade även att byta ut min hash-funktion mot den som hildenborg postade tidigare i den här tråden:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. slots:8192  collisions:911
3. slots:8191  collisions:925
4.  

Men den gav i princip likadan distribution och antal kollisioner

Slutligen så provade jag versionen med slumpmässiga ord, och där lagras 100000 unika strängar i tabellen. Även här testade jag med stora tabellstorlekar, 262144 (inte primtal) och 262147 (primtal)

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. slots:262144  collisions:19176
3. slots:262147  collisions:19154
4.  

Och med den andra hash-funktionen:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. slots:262144  collisions:19066
3. slots:262147  collisions:18999
4.  

Så min slutsats måste bli, att med min hashtabellsimplementation, och med just de här två dataseten, så spelar det ingen roll om man använder ett primtal som modulo eller inte - man får ungefär samma mängd kollisioner iallafall. (och för övrigt verkar de två hash-funktionerna vara i pincip lika bra, men den som hildenborg postade gör något färre operationer på datan, så kan vara snabbare).

Jag lutar åt att se till att använda power-of-two storlekar för mina hashtabeller, eftersom man då kan göra en bitwise-AND istället för en modulo.

[Hildenborg]

Jag får för mig, att med en hash funktion som är hyffsat OK, så finns det säkert en formel i stil med:
Om hash är av x antal bitar, och man har y antal hashningar, så kommer det bli z antal kollissioner.
Och det är förmodligen det du ser i dina test.

Det en hash igentligen gör, är ju bara att räkna ut en checksum, och se till att sprida den så att liknande data's hashning inte kolliderar.
Dvs. i en simpel hash funktion, så skulle strängarna "ABC" och "CBA" kunna kollidera. Men i en avancerad så kolliderar istället strängarna "ABC" och "WOT"...

Så, vad jag vill få fram, är att med ett visst antal hash bitar, så kommer det alltid bli ett visst antal kollissioner om man har ett visst antal hashningar.

Inget av detta stämmer förstås om man har en dålig hash funktion i stil med: hash=(hash+stream)*0;
Men det är väl rätt uppenbart

[Mattias Gustavsson]

Jag får för mig, att med en hash funktion som är hyffsat OK, så finns det säkert en formel i stil med:
Om hash är av x antal bitar, och man har y antal hashningar, så kommer det bli z antal kollissioner.
Och det är förmodligen det du ser i dina test.

Nja, antalet kollisioner beror inte bara av antalet bitar vs antalet hashningar - det beror också i hög grad på vilken data man har, OCH hur många slots/bins man har i hashtabellen. Om vi antar att man har t.ex. 10 slots i hashtabellen, och väljer slot genom formeln slot=hash%10, då kommer ju alla hash-nummer som ger samma modulo-resultat att hamna i samma slot, dvs kollidera (med kollision menas här när två strängar resulterar i samma slot - antingen genom att de har samma hash-värde, eller att de har hash-värden sådana att modulo med antal slots ger samma resultat).

Man får alltid kollisioner i en hash-tabell, och fler desto mer fylld med data den är. I min lösning dubblar jag tabellens storlek när den är fylld till två-tredjedelar.

Men alltså, enligt gammal programmerartradition, så sägs det att man får färre kollisioner om man ser till att tabellen har ett antal slots som är ett primtal. Man antar att när man tar två olika hash-värden, och tar modulo med antal slots, så får man oftare olika värden om antalet slots är ett primtal än om det inte är det. Om man däremot får samma hash-värden från två olika strängar, då blir det ju kollision oavsett vad man tar modulo med.

Enligt den artikeln som dooz postade länk till, så ska det inte spela nån roll om antalet slots är primtal eller inte - och det är det som mina tester bekräftar, att det i mitt fall, med just den här test-datan (både ordlista och slumpsträngar) faktiskt funkar lika bra med tabellstorlekar som är tvåpotenser som med såna som är primtal. Och eftersom antalet kollisioner är samma, så kan man ju få liite högre prestanda genom en AND istället för en modulo... (heh... jag har pulat med lågnivå-optimering på sistone, spiller visst över på andra områden )

[tetsu]

Att tänka på när det gäller antalet slots och effektivitet så hänger det även ihop med hashfunktionen. Vissa hashfunktioner fungerar bättre om antalet slots är primtal. Vissa fungerar lika bra på primtal och icke primtal, men kan vara sämre om antalet är tvåpotens. Bokstavligt talat så är det här en hel vetenskap . Finns säkerligen en massa roliga satistiska analysmetoder att ta till för att få ett hum hur bra en implementation är. Fast senast jag använde sådant var när jag höll på med genetik och det är för länge sen för att jag skall komma ihåg någon bra metod, men google kan säkert vara din vän här .

[Mattias Gustavsson]

Tänkte att det är lika bra att runda av den här tråden som den startade, med en nedladdning av StringId systemet. Har snyggat till och kommenterat den senaste (snabbaste) versionen, och den finns att hämta här:

pixie_stringid_v2.zip

Bra diskussion, och slutade med att jag fick mitt system många gånger snabbare än vad det var från början. Plus att jag vann över Hildenborg

[dooz]

En liten grej; VS2008 hittar inte toupper som används i StringIdTable.cpp, utan vill att man inkluderar ctype.h. Jag har inte testat med någon annan VS, och har inga åsikter om var toupper egentligen borde finnas..

Oh, och så har du satt dina måsvingar fel

[Mattias Gustavsson]

Oh, och så har du satt dina måsvingar fel

nej, faktiskt inte..

följande formatering:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. x=1;
3. y=2;
4.  

innebär två statements som utförs i sekvens - de är på samma indentering

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. if (x==1)
3.     y=2;
4.  

innebär ett statement som är underordnat en if-statement - de utförs alltså inte i sekvens som i exemplet ovan, utan det underordnade är beroend av resultatet av det överordnade

och det här:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. if (x==1)
3.     y=2;
4. z=3;
5.  

är ett if-statement med underordnat assignment-statement, och ett ytterligare assignment som utförs efter if-statementet. Huruvida y=2 görs eller ej är beroende av resultatet av if-satsen, men z=3 utförs sekventiellt efter if-satsen, oavsett

För mig innebär följande formatering:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. if (x==1)
3. {
4.     y=2;
5.     z=3;
6. }
7.  

att man har en if-statement, och sedan har man en block-start statement som utförs i sekvens efter if-satsen (och i sin tur med underordnade assignment statements), vilket känns fel för mig - det är ju inte så koden fungerar (man kan väl kanske hävda att assignment-statementsen faktiskt ska vara underordnade block-start/block-end, men jag tycker inte det - exekveringen av y=2 är ju inte beroende på utkomsten av block-starten, {, utan utförs alltid).

här däremot:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. if (x==1)
3.     {
4.     y=2;
5.     z=3;
6.     }
7.  

har man ett if-statement, och underordnat det har man en sekvens av block-start, assignment, assignment, block-end, vart och ett som utförs i sekventiell ordning. Block-start är beroende av utkomsten av if-statement, och formateringen indikerar att resten av satserna också är det, vilket ju stämmer.

Så det sista exemplet tycker jag visar bättre på hur kodens egentliga flöde är. Men jag hade använt sättet ovanför i många år innan jag bytte till det här, och det tog mig ett tag att vänja mig. Men jag ville inte låta nån fånig personlig preferens hindra mig från att använda en mer korrekt formatering

[dooz]

Hmm, det var rätt intressant. Jag har aldrig tänkt på att se måsvingarna som det sättet att se kodblock, men samtidigt så är jag lite orolig för att försöka lägga semantik på något som kanske inte var tänkt att betyda just det från början.

Jag håller själv på att testa runt olika sätt att formattera (och namnge) min kod, efter att ha haft samma standard i säkert 10 år (med undantag för ungersk notationsflugan), och kör med:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. void tjong()
3. {
4.   if (x == 1) {
5.     y = 2;
6.   }
7. }
8.  

som faktiskt stämmer överens (i princip) med din tolkning av måsvingar och block. Kusligt

[Mattias Gustavsson]

Japp, att formatera enligt:

Radnummer Av/På | Expandera/Minimera | Markera allt

1.  
2. if (x == 1) {
3.    y = 2;
4. }
5.  

är precis lika korrekt enligt mitt sätt att se det. Då när jag bytte över, så testade jag den varianten också, men tyckte det blev svårare att få överblick över koden då, speciellt när man snabbt scannar större kodblock... Så det fick bli den andra istället - en fråga om preferens i det fallet.