* Jesper Gødvad
[denne kommer til å bli lang]
[snip]
> Nej, sådan er det ikke. Men når det drejer sig om performance er det
> jo ikke så godt hvis det kun er hurtigt i teorien.
I praksis er O(1) raskere enn O(logn) for alle n > K. Det eneste som
er avgjørende er K'en. Med tanke på hvordan map er implementert, og
hvordan en typisk hashtabell er implementert vil man i _snittet_ får
adskillig raskere oppslag/innsetting.
[snip]
> Nu er der måske noget jeg har misforstået, men hvis hash-tabellen skal have
> random access O(1) er det vel en forudsætning at der er et array med faste
> størrelser på keys?
Størrelsen av en hashtabell er en funksjon av antall elementer som er
satt inn, _ikke_ av størrelsen av nøkkelrommet.
> Jeg tillader mig at forsimple dit eksempel til blot at være datoer i
> ååmmdd-format, så:
>
> 000101 til 000131 = første 31 mulige keys (0-30)
> 000201 til 000231 = næste 31 mulige keys (31-61)
> osv.. (tager ikke højde for forskellige antal dage i månederne)..
>
> i alt = 31 x 12 x 100 keys = 37.200 stk.
>
> Hvis din key-beregning giver et resultat mellem 0 og 36.199 kunne du jo lige
> så godt bruge en std::vector.
Du er klar over at det ekstremt idiotisk å allokere 37200 entries,
dersom man har fx. 1000 elementer i programmet. La oss si at
nøkkelrommet er i størrelseorden 2^32, men man skal ta vare kun på
10000 nøkler. Det er feil å allokere 4GB da. Under noen omstendigheter
holder det med en (bit)vector (ta en titt i fx. "Programming Pearls",
2ed), men generelt er std::vector rettferdiggjort kun når forholdet
antall_elementer/størrelsen_på_nøkkelrommet nærmer seg 1 (vel, dette
er en nødvendig men neppe tilstrekkelig forutsetning). Hashtabeller
egner seg når dette forholdet er nærmere 0.
> Hvis du ikke regner keys mellem 0 og 36.199, men i stedet bruger
> ååmmdd som key, må forudsætningen for random access O(1) da være at
> hash-tabellen har "reserveret" 000101 til 991231 = 991.130 pladser i
> sin tabel.
Nei, det er ikke slik hashtabeller fungerer.
La oss si at man skal ta være på 1000 elementer. Nøklene til disse
elementene er heltall (dvs. størrelsen på nøkkelrommet, S, er på
2^32). La oss anta videre at vi ikke vet annet enn #elementer/S er
veldig nærme 0.
Det som kommer til å skje er at hashtabellen vil ettehvert vokse
dynamisk som en funksjon av antall elementer som er satt inn (man vil
typisk allokere flere plasser enn det er elementer, men det er nå så).
Da ender man opp typisk med en tabell på noen tusen entries (>1000,
men ikke så veldig mye mer enn 2x eller 3x).
Du kan regne selv hvor mange plasser man vil måtte allokere for en
vector. Det som er mer interessant er hvor mye plass en hashtabell
bruker i forhold til en std::map, men det er nå så.
> Hvis hash-tabellen _ikke_ har reserveret de 991.130 pladser (men kun
> dé som indeholder værdier) må det da være nødvendigt for den at
> benytte samme funktionalitet som fra et std::map.
Nei. Jeg anbefaler en titt i "Algorithms in C" av R. Sedgewick eller
"The Art of Computer Programming, Vol III -- Sorting and Searchiing"
av D. E. Knuth.
[snip]
> En god hashfunktion kræver vel altid at du kender dine data
> forholdsvist godt?!
Nei. Når man kjenner inputdataene, så kan man lage en perfekt
hashfunksjon (dvs. den som vil aldri gi kollisjoner).
Sagt på en annen måte: gitt en god hashfunksjon, eksisterer det input
som er slike at _alle_ nøklene vil hash'es til samme verdi/bucket.
_Sannsynligheten_ for at noe slikt inntreffer er ofte lavere enn det
at datamaskinen blir truffet av et lyn.
> Hvis du ikke på forhånd kender værdierne kan du ikke beregne en
> "semi-unik" key og du vil dermed få O(1)+ access.
Hva skulle "O(1)+" bety? Selv om flere forskjellige nøkler hash'es til
samme "bucket", betyr ikke det nødvendigvis at hashtabellen vil få
logaritmisk (eller verre) oppslag. Det _kan_ hende, men
sannsynligheten for det er liten (dersom hashfunksjonen er god).
> Hvis du ikke kender mængden er resultatet det samme, ellers på du
> bruge performance på at resize.
?
> > Sludder. Oppslaget kan forekomme i en indre løkke. Hvorvidt algoritmen
> > er O(n^2) eller O(n^2logn) har kanskje litt å si.
>
> Ak, jeg ved for lidt om logaritmer.
Ok, men n == 10^3, vil den første bruke tiden proporsjonal med 10^6,
mens den andre vil bruke tiden proporsjonal med 10 * 10^6 (altså #2 er
10 ganger saktere).
> Vil du give et eksempel på hvor mange access der skal laves i de to
> tilfælde? Jacob Atzen gav et eksempel på 1 milliard elementer, men
> det anser jeg for rimelig teoretisk, så hvad med 1 million.
Ok, si at man tar være på 10^6 strenger (nøkler) som er knyttet til
verdier. Et oppslag i std::map tar O(logN) tid, dvs. man må regne med
å foreta rundt 20 sammenligninger, da et RB-tre, iirc, er et binært
tre (litt mindre, strengt tatt). For hver av disse sammenlignes deler
av strengen. Dersom den sistnevnte er på 30 tegn, foretar man rundt 20
* 30 == 600 sammenligninger (pekerdillemikk er ikke inkludert) (med
tanke på hvor mange noder det er på hvert nivå, vil #nivåer man
traverserer i gjennomsnittet kanskje ikke være så langt unna 20).
Dersom man har en hashtabell med en god hashfunksjon, kan vi si at
gjennomsnittslengden på en bucket er 5. Hashverdien regnes 1 gang, og
så traverserer vi listen bestående av 5 elementer i snitt. Dette er
150 sammenligninger + beregning av hashverdien. Altså ca. 1/4 del av
oppslagstiden i std::map (det er en rekke antagelser i dette
regnestykket, men i _gjennomsnittet_ er disse ikke så langt fra
sannheten).
> > > - Hvis du alligevel er oppe i at sammenligne O(logN) med hash, så
> > > tager det sikkert også en del tid at regne de store hash-nøgler.
> >
> > Huh?
>
> Jeg forestillede mig, at det ville tage tid at beregne meget store
> hash-keys, men jeg kan godt se at det ikke behøver at være sådan nu.
For strings spesielt er dette en typisk hashfunksjon:
unsigned int
hash( const char *s )
{
unsigned int h = 0U;
unsigned char *p;
for ( p = (unsigned char*)s; *p; ++p )
h = MULTIPLIER * h + *p;
return h % HASHSIZE;
}
HASHSIZE er størrelsen på hashtabellen, mens MULTIPLIER kan fx. settes
til 31 eller 37 ("gode" primtall).
Dette innebærer at man gjør traversering av strengen en gang, og
dertil gjøres det _svært_ lite for hvert tegn (med MULTIPLIER == 31
snakker vi om 1 shift, 1 substraksjon og 1 addisjon per tegn (jada,
strength-reduction er nyttig)).
> > > - Endelig kan man jo bare regne en hash-key og bruge den som nøgle i
> > > std::multimap hvis det er nødvendigt.
> >
> > Og så?
>
> Ja, så har jeg svært ved at se hvordan hash skulle kunne slå
> std::map i performance (så fremt vi forudsætter at std::vector
> løsningen er kasseret). Hvis keys ikke er fra x til x+y og der ikke
> er reseveret plads til ikke-eksisterende værdier så må hash da
> fungere på samme måde som std::map, ikke?!
Ok, du insisterer tydeligvis på at vi skal time'e ting (helvetet som
jeg hater gnøkkakompilatorer som er altfor hjerneskadde til å gi en
ordentlig feilmelding! FSCK!):
$ ./a.out /usr/share/lib/dict/words 10th 100000
there are: 25143; 25143 entries
Measuring lookup of 10th...done!
User: 1.82
System: 0
Measuring lookup of 10th...done!
User: 0.59
System: 0
$ ./a.out /usr/share/lib/dict/words larva 100000
there are: 25143; 25143 entries
Measuring lookup of larva...done!
User: 2.08
System: 0
Measuring lookup of larva...done!
User: 0.61
System: 0
$ ./a.out /usr/share/lib/dict/words zygote 100000
there are: 25143; 25143 entries
Measuring lookup of zygote...done!
User: 3.2
System: 0
Measuring lookup of zygote...done!
User: 0.61
System: 0
$
(10th er det 'første' ordet, larva er i ca. midten mens zygote er det
siste ordet i lokal kopi av /usr/share/lib/dict/words). Det må sies at
dette er kanskje ikke helt rettferdig, da input'en har en ganske så
bestemt struktur, men men...
Legg merke til hvordan tiden for oppslaget varierer for std::map, men
ikke for hash_set.
Programmet:
$ cat timing.cpp
/*
*
* $Id$
*
* Copyright (C) 2001 by Igor V. Rafienko, <igorr@ifi.uio.no>
*
*/
#include <iostream>
#include <string>
#include <hash_map>
#include <map>
#include <sys/times.h>
#include <limits.h>
#include <fstream>
#include <utility>
using namespace std;
template< typename Cont >
void
time_container( Cont &c, const string &s, size_t runs )
{
cout << "Measuring lookup of " << s << "...";
unsigned int i = 0;
struct tms t1, t2;
times( &t1 );
for ( size_t j = 0; j != runs; ++j )
i += c[ s ];
times( &t2 );
cout << "done!\n";
cout << "User: " << (t2.tms_utime - t1.tms_utime)/(1.0*CLK_TCK) << "\n";
cout << "System: " << (t2.tms_stime - t1.tms_stime)/(1.0*CLK_TCK) << "\n";
}
struct SGI_STL_is_braindead
{
hash< const char * > h;
size_t operator()( const std::string &s ) const {
return h( s.c_str() );
}
};
int
main( int argc, char *argv[] )
{
const char *name = argc > 1 ? argv[1] : "/usr/share/lib/dict/words";
string word = argc > 2 ? argv[2] : "larva";
size_t runs = argc > 3 ? (size_t)strtol( argv[3], NULL, 10 ) : 1000;
map< string, int > m;
hash_map< string, int, SGI_STL_is_braindead > hm;
ifstream ifs( name );
if ( !ifs )
exit( 1 );
string next;
while ( ifs >> next ) {
m[ next ] = 1;
hm[ next ] = 1;
}
cout << "there are: " << m.size() << "; " << hm.size() << " entries\n";
time_container( m, word, runs );
time_container( hm, word, runs );
}
$
Mao, hash_set (som bruker en _veldig_ primitiv hashfunksjon) er et
sted mellom 3 og 5 ganger raskere enn std::map. Dersom du vil vite
_hvorfor_ det er tilfellet, har jeg nevnt et par bøker som forklarer
forskjellen.
Hvis ikke det overbeviser en pragmatiker som deg, så vet ikke jeg...
(dagens trivia: lag en input der hash_set vil være dårligere enn std::map).
[snip]
> > "Practice Of Programming", B. Kerninghan, R. Pike, Ch. 3
>
> Kan du ikke poste koden. Jeg kan jo ikke blive ved med at købe alt
> som dig og Mogens anbefaler
Du trenger ikke å kjøpe disse bøker dersom du ikke vil -- det finnes
biblioteker her i landet og jeg er ganske sikker på at de ikke er
avskaffet i Danmark enda.
ivr
--
The UNIX Guru's View of Sex:
# nslookup girl; rdate girl; cd $HOME; unzip ; strip ; touch ; finger ;
mount ; fsck ; more ; yes ; umount ; sleep