/ Forside / Teknologi / Udvikling / C/C++ / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
C/C++
#NavnPoint
BertelBra.. 2425
pmbruun 695
Master_of.. 501
jdjespers.. 500
kyllekylle 500
Bech_bb 500
scootergr.. 300
gibson 300
molokyle 287
10  strarup 270
hashfunktion
Fra : Benedikte


Dato : 04-06-01 13:47

Er der en som kan forklare mig hvordan en hashfunktion i pascal virker
(H:= værdien MOD tabelstørrelse)
Jeg skal til programmeringseksamen på torsdag.
på forhånd tak

--
Leveret af:
http://www.kandu.dk/
"Vejen til en hurtig løsning"


 
 
Jacob Bunk Nielsen (04-06-2001)
Kommentar
Fra : Jacob Bunk Nielsen


Dato : 04-06-01 13:54

"Benedikte" <Benedikte.news@kandu.dk> writes:

> Er der en som kan forklare mig hvordan en hashfunktion i pascal virker

Prøv at spørge i news:dk.edb.programmering.pascal, der tror jeg du har
større chance for at få hjælp med det der har med Pascal at gøre.

> (H:= værdien MOD tabelstørrelse)

MOD (% i C) giver dig resten af divisionen mellem 'værdien' og
'tabelstørrelse'.

> Jeg skal til programmeringseksamen på torsdag.

Held og lykke!

--
Jacob
Uh-oh ... let's pretend I didn't do that, OK?

Thomas Jespersen (04-06-2001)
Kommentar
Fra : Thomas Jespersen


Dato : 04-06-01 14:21

"Benedikte" <Benedikte.news@kandu.dk> writes:

> Er der en som kan forklare mig hvordan en hashfunktion i pascal virker
> (H:= værdien MOD tabelstørrelse)

Jeg ved ikke hvordan Pascal versionen adskiller sig fra den generelle
hash-funktion, men jeg ved hvordan den generelle hash-funktion
virker. En hash-funktion beregner en tal-værdi (nøgle) ud fra de
objekter du skal gemme i din hash-tabel. Denne nøgle-værdi er så den
position dit objekt vil få i hash-tabellen (tabellen er tit blot et
array og nøglen er indekset ind i arrayet). Hvis to objekter bliver
tildelt den samme nøgle-værdi vil der opstå en kollision i tabellen og
det vil man gerne undgå. Derfor gælder det om at hash-funktionen helst
skal distribuere nøgle-værdierne jævnt ud over indgangene i
hash-tabellen. Den hash-funktion du nævner er et simpelt eksempel. Den
finder en værdi der ligger mellem 0 og 'tabelstørrelse' ved at tage
modulo (rest ved division) tabelstørrelse på nøgleværdien. Hvis du
tænker lidt over det kan du nok se at en division med 'tabelstørrelse'
aldrig vil give en rest større end tabelstørrelse-1, og resten vil
altid være mindst 0.

Fordelen ved en hash-tabel er at opslag i tabellen i bedste fald kan
udføres i konstant tid.

> Jeg skal til programmeringseksamen på torsdag.

held og lykke!

Thorbjørn Ravn Ander~ (04-06-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 04-06-01 23:40

Thomas Jespersen wrote:

> Fordelen ved en hash-tabel er at opslag i tabellen i bedste fald kan
> udføres i konstant tid.

Det gælder vel alle datastrukturer hvis det er det første element man
kigger på, som er det man leder efter.

De hashtabeller jeg har set, har benyttet lister af elementerne i samme
hashtabelindgang. Hvis tabellen er for fuld, bliver der derfor en vis
træghed.
--
Thorbjørn Ravn Andersen "...plus...Tubular Bells!"
http://bigfoot.com/~ravn



Peter Gade Jensen (05-06-2001)
Kommentar
Fra : Peter Gade Jensen


Dato : 05-06-01 03:18

"Thorbjørn Ravn Andersen" <thunderbear@bigfoot.com> wrote in message
> De hashtabeller jeg har set, har benyttet lister af elementerne i samme
> hashtabelindgang. Hvis tabellen er for fuld, bliver der derfor en vis
> træghed.

Det er osse derfor at man taler om forventet konstant tid for opslag i en
hash-tabel..
Mener jeg da.... =)

mvh
Peter Gade



Thorbjørn Ravn Ander~ (05-06-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 05-06-01 08:56



Peter Gade Jensen wrote:
>
> "Thorbjørn Ravn Andersen" <thunderbear@bigfoot.com> wrote in message
> > De hashtabeller jeg har set, har benyttet lister af elementerne i samme
> > hashtabelindgang. Hvis tabellen er for fuld, bliver der derfor en vis
> > træghed.
>
> Det er osse derfor at man taler om forventet konstant tid for opslag i en
> hash-tabel..
> Mener jeg da.... =)

Valget af hashfunktion er vigtigt, og det kan godt betale sig at
undersøge flere hvis man skal lave fx en symboltabel til en compiler.
Det er dumt hvis de foruddefinerede ord ikke har en indgang for sig selv
allerede fra starten.

Men hvis man programmere Java får man en klasse forærende, og så behøver
man ikke tænke meget mere på dét.
--
Thorbjørn Ravn Andersen "...plus...Tubular Bells!"
http://bigfoot.com/~ravn

Mogens Hansen (05-06-2001)
Kommentar
Fra : Mogens Hansen


Dato : 05-06-01 16:46


"Thorbjørn Ravn Andersen" <thunderbear@bigfoot.com> wrote in message

>
> Valget af hashfunktion er vigtigt, og det kan godt betale sig at
> undersøge flere hvis man skal lave fx en symboltabel til en compiler.

Nemlig - hashfunktionen er afgørende for performance, og dens implementering
afhænger af hvilke data der forventes.

>
> Men hvis man programmere Java får man en klasse forærende, og så behøver
> man ikke tænke meget mere på dét.

hashfunktionen skal man vel altid tænke over.

Man får også hash-container klasser forærende i C++.
Se f.eks. www.stlport.org
De adskiller sig formodentlig fra de næsten tilsvarende Java klasser ved at:
* være mere effektive på run-time
* statisk type sikre
* findes på flere platforme

De er ikke en del af standarden, men det betyder jo ikke at de ikke findes.

Venlig hilsen

Mogens Hansen




Jesper Gødvad (09-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 09-06-01 15:51

> > Men hvis man programmere Java får man en klasse forærende, og så behøver
> > man ikke tænke meget mere på dét.
>
> hashfunktionen skal man vel altid tænke over.
>
> Man får også hash-container klasser forærende i C++.

Ja, jeg spør' bare, men hvorfor ville man overhovedet bruge en
hash-container i C++?

Jeg har læst om hash-tabeller, men så vidt jeg kan se er det kun noget der
er værd at kigge på hvis man insisterer på at benytte et forud defineret
array i stedet for dynamiske containerklasser.

Hvad kan en hash-tabel som fx. et multimap ikke kan?

Da hash-keyen alligevel er en beregnet størrelse kunne man jo også bare
skippe beregningen og putte elementerne i et set eller et multiset afhængigt
af hvad man skal bruge.

Ja, jeg undrer mig bare...

mvh. jesper



Igor V. Rafienko (09-06-2001)
Kommentar
Fra : Igor V. Rafienko


Dato : 09-06-01 16:23

* Jesper Gødvad

[snip]

> Ja, jeg spør' bare, men hvorfor ville man overhovedet bruge en
> hash-container i C++?


Av de samme grunnene som man ville ha gjort det i ethvert annet språk.


> Jeg har læst om hash-tabeller, men så vidt jeg kan se er det kun
> noget der er værd at kigge på hvis man insisterer på at benytte et
> forud defineret array i stedet for dynamiske containerklasser.
>
> Hvad kan en hash-tabel som fx. et multimap ikke kan?


Aksess til en vilkårlig element i O(1) framfor O(logN). Dersom man har
skal representere en _mengde_ elementer der (element)nøklene ikke har
en strict weak ordering, så kan man ikke bruke map/multimap (hashing
krever riktignok at elementene er hashable, men jeg innbiller meg at
det er lettere å finne en hashverdi heller enn en ordning à la op<()
(om ikke annet så kan man bruke memory-adressen til objektene)).

Dog, det skal sies at noen ganger bruker man (vel, iallfall jeg :))
std::map som om det var en hashtabell. Hvorvidt det er smart er jo et
spørsmål.


> Da hash-keyen alligevel er en beregnet størrelse kunne man jo også
> bare skippe beregningen og putte elementerne i et set eller et
> multiset afhængigt af hvad man skal bruge.


En 'std::set' er en _mengde_ (som er ordnet, merkelig nok), en
hashtabell er en funksjon fra nøkler til verdier. Det er 2
forskjellige ting, så sammenligningen holder egentlig kun for
hashtabell vs. std::map/std::multimap.





ivr
--
Amy: Psst... look what life was like before genetic engeneering.
Leela: Those poor 20th century women...
-- Futurama, "Why must I be a Crustacean in love?"

Jesper Gødvad (09-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 09-06-01 20:07

Hej Igor

[haps]

> > Hvad kan en hash-tabel som fx. et multimap ikke kan?
>
> Aksess til en vilkårlig element i O(1) framfor O(logN). Dersom man har
> skal representere en _mengde_ elementer der (element)nøklene ikke har
> en strict weak ordering, så kan man ikke bruke map/multimap (hashing
> krever riktignok at elementene er hashable, men jeg innbiller meg at
> det er lettere å finne en hashverdi heller enn en ordning à la op<()
> (om ikke annet så kan man bruke memory-adressen til objektene)).

Er det ikke meget teoretisk?

Jeg mener:
- Hvis du er sikker på O(1) access kunne du jo lige så godt bruge en
std::vector.
- Hvis du ikke er sikker på O(1) access må det påregnes at du skal iterere
O(x) (??) gange og resize din hash-tabel.
- Når O(logN) bliver langsom har du formentlig brugt alt din ram for lang
tid siden og så bliver flaskehalsen din I/O access.
- 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.
- Jeg kan da bare også bruge pointere i std::multimap
- Endelig kan man jo bare regne en hash-key og bruge den som nøgle i
std::multimap hvis det er nødvendigt.
- std::map er garanteret O(logN). Hash er ikke garanteret O(1).

> Dog, det skal sies at noen ganger bruker man (vel, iallfall jeg :))
> std::map som om det var en hashtabell. Hvorvidt det er smart er jo et
> spørsmål.

Hvorfor skulle det ikke være smart? Jeg prøver at komme på et konkret
eksempel hvor man ville opnå en fordel ved at bruge hash, men der er så
mange 'hvis'er at jeg ikke kan se hvorfor man overhovedet skulle bruge det.

> > Da hash-keyen alligevel er en beregnet størrelse kunne man jo også
> > bare skippe beregningen og putte elementerne i et set eller et
> > multiset afhængigt af hvad man skal bruge.
>
> En 'std::set' er en _mengde_ (som er ordnet, merkelig nok), en
> hashtabell er en funksjon fra nøkler til verdier. Det er 2
> forskjellige ting, så sammenligningen holder egentlig kun for
> hashtabell vs. std::map/std::multimap.

Enig, men der er jo ikke være langt mellem funktionaliteten i praksis.

mvh. jesper





Jacob Atzen (10-06-2001)
Kommentar
Fra : Jacob Atzen


Dato : 10-06-01 11:02

"Jesper Gødvad" <Xesper@goedvad.dk> writes:

> Er det ikke meget teoretisk?
>
> Jeg mener:
> - Hvis du er sikker på O(1) access kunne du jo lige så godt bruge en
> std::vector.
> - Hvis du ikke er sikker på O(1) access må det påregnes at du skal iterere
> O(x) (??) gange og resize din hash-tabel.
> - Når O(logN) bliver langsom har du formentlig brugt alt din ram for lang
> tid siden og så bliver flaskehalsen din I/O access.
> - 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.
> - Jeg kan da bare også bruge pointere i std::multimap
> - Endelig kan man jo bare regne en hash-key og bruge den som nøgle i
> std::multimap hvis det er nødvendigt.
> - std::map er garanteret O(logN). Hash er ikke garanteret O(1).
<snip>

En hash kan give dig et element i et vilkårligt stort array i løbet af meget
kort tid. Selvom dit array har 1 mia. indgange kan du finde det element du
søger i løbet af meget få sammenligninger, hvis det er en ordentlig hash
funktion du bruger.

Jeg skal ikke kunne sige, noget om de C++ specifikke ting du nævner ovenfor.

- Jacob

Igor V. Rafienko (10-06-2001)
Kommentar
Fra : Igor V. Rafienko


Dato : 10-06-01 22:00

* Jesper Gødvad


> > Aksess til en vilkårlig element i O(1) framfor O(logN). Dersom man
> > har skal representere en _mengde_ elementer der (element)nøklene
> > ikke har en strict weak ordering, så kan man ikke bruke
> > map/multimap (hashing krever riktignok at elementene er hashable,
> > men jeg innbiller meg at det er lettere å finne en hashverdi
> > heller enn en ordning à la op<() (om ikke annet så kan man bruke
> > memory-adressen til objektene)).
>
> Er det ikke meget teoretisk?


Og så...? (er det slik at såsnart argumentet er teoretisk, så mister
det sin verdi?).


> Jeg mener:
> - Hvis du er sikker på O(1) access kunne du jo lige så godt bruge en
> std::vector.


Nei, det kunne jeg ikke. En _nødvendig_ forutsetning for bruk av
std::vector er at indeksene er fortløpende fra A til A+n. Dersom jeg
trenger O(1) oppslag og indeksene mine _ikke_ har denne egenskapen
(fx. personnumre i Norge er 11-sifrede tall, der de 6 første er
fødselsdato og de 5 siste er et magisk tall), så er std::vector
ubrukelig, med mindre det finnes en (relativt enkel (å beregne))
funksjon som map'er mine N nøkler i intervallet [0, N+1).


> - Hvis du ikke er sikker på O(1) access må det påregnes at du skal
> iterere O(x) (??) gange og resize din hash-tabel.


Hæ? En god hashfunksjon og en tilfeldig input vil i gjennomsnittet gi
O(1) aksess til et vilkårlig element. Dersom man må _garantere_ det
uansett forhold, så er en hashtabell et dårlig valg. Dersom
sannsynligheten for at man skal foreta 100 sammenligninger framfor 1
er lavere enn at datamaskinen blir truffet av en meteoritt, og kravet
om oppslag i konstant tid ikke er tilstedet, så er en hashtabell et
greit valg fra ingeniørmessig synspunkt.


> - Når O(logN) bliver langsom har du formentlig brugt alt din ram for
> lang tid siden og så bliver flaskehalsen din I/O access.


Sludder. Oppslaget kan forekomme i en indre løkke. Hvorvidt algoritmen
er O(n^2) eller O(n^2logn) har kanskje litt å si.


> - 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 kan da bare også bruge pointere i std::multimap


Huh?


> - 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å?


> - std::map er garanteret O(logN). Hash er ikke garanteret O(1).


Helt korrekt. Og hver brukes til sine formål.


> > Dog, det skal sies at noen ganger bruker man (vel, iallfall jeg :))
> > std::map som om det var en hashtabell. Hvorvidt det er smart er jo et
> > spørsmål.
>
> Hvorfor skulle det ikke være smart?


Tja, fordi std::map<> ordner sine elementer i henhold til en eller
annen 'strict weak ordering', noe jeg noen ganger ikke er interessert
i. Og denne ordningen koster tid, om ikke plass.


> Jeg prøver at komme på et konkret eksempel hvor man ville opnå en
> fordel ved at bruge hash, men der er så mange 'hvis'er at jeg ikke
> kan se hvorfor man overhovedet skulle bruge det.


"Practice Of Programming", B. Kerninghan, R. Pike, Ch. 3

[snip]


> > En 'std::set' er en _mengde_ (som er ordnet, merkelig nok), en
> > hashtabell er en funksjon fra nøkler til verdier. Det er 2
> > forskjellige ting, så sammenligningen holder egentlig kun for
> > hashtabell vs. std::map/std::multimap.
>
> Enig, men der er jo ikke være langt mellem funktionaliteten i
> praksis.


Jo, det vil det: en hashtabell kan tenkes på som en mengde av par
<nøkkel, verdi>. En std::set er en mengde med verdier som ikke har
noen nøkler. For å ikke nevne at std::set og SGI's hash_set stiller
forskjellige krav til elementene.





ivr
--
Good news, everyone...
   Pr. Farnsworth, all Futurama episodes.

Jesper Gødvad (12-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 12-06-01 16:53


"Igor V. Rafienko" <igorr@ifi.uio.no> wrote in message
news:xjv4rtom4ny.fsf@jormunrekk.ifi.uio.no...
> * Jesper Gødvad
>
>
> > > Aksess til en vilkårlig element i O(1) framfor O(logN). Dersom man
> > > har skal representere en _mengde_ elementer der (element)nøklene
> > > ikke har en strict weak ordering, så kan man ikke bruke
> > > map/multimap (hashing krever riktignok at elementene er hashable,
> > > men jeg innbiller meg at det er lettere å finne en hashverdi
> > > heller enn en ordning à la op<() (om ikke annet så kan man bruke
> > > memory-adressen til objektene)).
> >
> > Er det ikke meget teoretisk?
>
> Og så...? (er det slik at såsnart argumentet er teoretisk, så mister
> det sin verdi?).

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.

> > - Hvis du er sikker på O(1) access kunne du jo lige så godt bruge en
> > std::vector.
>
> Nei, det kunne jeg ikke. En _nødvendig_ forutsetning for bruk av
> std::vector er at indeksene er fortløpende fra A til A+n. Dersom jeg
> trenger O(1) oppslag og indeksene mine _ikke_ har denne egenskapen
> (fx. personnumre i Norge er 11-sifrede tall, der de 6 første er
> fødselsdato og de 5 siste er et magisk tall), så er std::vector
> ubrukelig, med mindre det finnes en (relativt enkel (å beregne))
> funksjon som map'er mine N nøkler i intervallet [0, N+1).

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?

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.

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.

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.


> > - Hvis du ikke er sikker på O(1) access må det påregnes at du skal
> > iterere O(x) (??) gange og resize din hash-tabel.
>
> Hæ? En god hashfunksjon og en tilfeldig input vil i gjennomsnittet gi
> O(1) aksess til et vilkårlig element. Dersom man må _garantere_ det
> uansett forhold, så er en hashtabell et dårlig valg. Dersom
> sannsynligheten for at man skal foreta 100 sammenligninger framfor 1
> er lavere enn at datamaskinen blir truffet av en meteoritt, og kravet
> om oppslag i konstant tid ikke er tilstedet, så er en hashtabell et
> greit valg fra ingeniørmessig synspunkt.

En god hashfunktion kræver vel altid at du kender dine data forholdsvist
godt?!
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.
Hvis du ikke kender mængden er resultatet det samme, ellers på du bruge
performance på at resize.

> > - Når O(logN) bliver langsom har du formentlig brugt alt din ram for
> > lang tid siden og så bliver flaskehalsen din I/O access.
>
> 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. 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.

> > - 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.

> > - Jeg kan da bare også bruge pointere i std::multimap
> Huh?

Du angav, at du kunne bruge memory-adressen som key i hash. Det kan man jo
også gøre i std::map.

> > - 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?!

> > > Dog, det skal sies at noen ganger bruker man (vel, iallfall jeg :))
> > > std::map som om det var en hashtabell. Hvorvidt det er smart er jo et
> > > spørsmål.
> >
> > Hvorfor skulle det ikke være smart?
>
> Tja, fordi std::map<> ordner sine elementer i henhold til en eller
> annen 'strict weak ordering', noe jeg noen ganger ikke er interessert
> i. Og denne ordningen koster tid, om ikke plass.

Ok, det er selvfølgelig en forskel der har indflydelse.

> > Jeg prøver at komme på et konkret eksempel hvor man ville opnå en
> > fordel ved at bruge hash, men der er så mange 'hvis'er at jeg ikke
> > kan se hvorfor man overhovedet skulle bruge det.
>
> "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

mvh. jesper




Igor V. Rafienko (12-06-2001)
Kommentar
Fra : Igor V. Rafienko


Dato : 12-06-01 19:21

* 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

Thomas Krog (13-06-2001)
Kommentar
Fra : Thomas Krog


Dato : 13-06-01 15:15

> 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).

Desuden er der den fordel ved en hashtable at man kan styre
gennemsnitslængden af en bucket. Hvis kørselstiden er meget vigtig og man
ved der er lige omkring 10000 elementer er hukkommelsen efterhånden så
billig at man fint kan allokere plads til 50000 entries. Dermed vil
kørselstiden formodentlig komme ned på omkring 1/12 (har dog ikke regnet
efter) af et opslag i std::map



Thomas Krog (13-06-2001)
Kommentar
Fra : Thomas Krog


Dato : 13-06-01 15:31

> 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).

Så vidt jeg kan se kan man antage at den i gennemsnit finder det søgte
element efter at have undersøgt 2,5 elementer i en bucket. Dvs at der
igennemsnit skal udføres 75 sammenligninger pr opslag i hashtabellen. Altså
en kørselstid svarende til 1/8 del af opslagstiden i std::map.

I en map ligger ca. halvdelen af elementerne i bladene af træet så et map
drager kun ringe fordel af chancen for at finde det søgte element på et
tidligt tidspunkt.



Igor V. Rafienko (13-06-2001)
Kommentar
Fra : Igor V. Rafienko


Dato : 13-06-01 16:02

* Thomas Krog

> Så vidt jeg kan se kan man antage at den i gennemsnit finder det søgte
> element efter at have undersøgt 2,5 elementer i en bucket. Dvs at der
> igennemsnit skal udføres 75 sammenligninger pr opslag i hashtabellen. Altså
> en kørselstid svarende til 1/8 del af opslagstiden i std::map.


Stemmer, takk.


> I en map ligger ca. halvdelen af elementerne i bladene af træet så et map
> drager kun ringe fordel af chancen for at finde det søgte element på et
> tidligt tidspunkt.


Det illusterte jo testen :)






ivr
--
Good news everyone: I've taught the toaster to feel love
         Pr. Farnsworth, Futurama

Thomas Krog (13-06-2001)
Kommentar
Fra : Thomas Krog


Dato : 13-06-01 16:18

> > Så vidt jeg kan se kan man antage at den i gennemsnit finder det søgte
> > element efter at have undersøgt 2,5 elementer i en bucket. Dvs at der
> > igennemsnit skal udføres 75 sammenligninger pr opslag i hashtabellen.
Altså
> > en kørselstid svarende til 1/8 del af opslagstiden i std::map.

eller for at være helt korrekt bliver gennemsnittet 3 undersøgelser:
(1+2+3+4+5)/5 = 3

> Det illusterte jo testen :)

:)



Jesper Gødvad (17-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 17-06-01 15:07


Hej Igor

"Igor V. Rafienko" <igorr@ifi.uio.no> wrote in message
news:xjvofrtmuej.fsf@andvarefoss.ifi.uio.no...
> * Jesper Gødvad

Jeg starter lige med at klippe

[klip]


> 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.

Ja, gu'er det idiotisk og det er jo bl.a. en af grundene til at jeg ikke
kunne forstå hvad man skulle bruge en hash-tabel til.

Igor! Jeg har læst dit brev adskillige gange for at finde udaf hvad det er
jeg åbenbart ikke kan forstå.

Jeg har lige skrevet et langt brev med et eksempel på hvorfor en hash var
"dårlig", men så fandt jeg udaf at jeg havde resoneret forkert så det er
lige blevet slettet.

Jeg har købt Sedgewicks bog og læst om hash. Ved kollisioner bruger han
linier probing eller alternativt linked list's. Jeg kan se at hele primtals
divisionen/multiplikationen skal reducere altallet af kollisioner, men der
er ingen garanti for at samtlige elementer ikke vil ligge i den samme linked
list?!

Hvis man med en hash-tabel på 101 elementer har en masser af kollisioner kan
man "risikere" at fjerne alle kollisioner ved at udvidde størrelsen til 103.

I praksis bør antallet af kollisioner kun stige efterhånden som
hash-tabellen bliver fyldt idet man ellers skal kigge på den måde man
beregner sin hash-key på.

Når hash-tabellen bliver fyldt stiger antallet af kollisioner og den skal
derfor udviddes. En udviddelse af tabellen kræver ( så vidt jeg kan se ) en
gen-beregning af samtlige nøgler der findes i tabellen og efterfølgende
gen-placering.

Hvis man på forhånd intet kender til antallet af elementer kan det reducere
performance væsentligt, fordi man dynamisk skal udvidde. Hvis man på forhånd
kender ca. antallet af elementer kan man lave en passende tabel før man
indsætter.

Når Sedgewick konkluderer at hash er "simplere" end btræer som std::map er
det alene udfra en betragtning om at man selv skal programmere dem og det er
der jo ingen grund til.

I dine eksempler bruger du en string som key, hvilket tvinger std::map til
string-compare. Hvis jeg fx. har string keys der maksimalt er 8 chars og
ikke er case-sensitive kan jeg reducere antallet af comparisons væsentligt
ved at omregne min key til int. Det vil ikke være hurtigere end hash, men
forskellen indsnævres og jeg behøver ikke tænke på at den tid det tager at
udvide hash-tabellen. Mit problem bliver dog ret tydeligt, hvis min
string-længde vokser til fx. 25 karakterer.

Eksemplet med at hash'e en hel bog kunne bruges af en søge maskine til at
finde den bog hvor 'C++' optræder flest gange, men ellers er det svært at
finde på et formål (ja-ja, noget med compilere fordi ordene ikke er
sorterede. Jeg går udfra at det er derfor du oftest bruger et std::map og
fordi det er en del af Standard Library.

Har jeg efterhånden forstået hashtabeller korrekt?

Hvis ikke, har jeg valgt 'Avancerede Algoritmer' på næste semester og bliver
forhåbentligt klogere.

Mange tak for forklaringerne og eksemplerne. Det er en stor hjælp at du
bruger din tid på os der spør'

mvh. jesper


> 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.

Mit problem er ikke prisen, men den tid de tager at læse og forstå. Hvis
det var omvendte var tilfældet ville jeg være en lykkelig mand.







Igor V. Rafienko (17-06-2001)
Kommentar
Fra : Igor V. Rafienko


Dato : 17-06-01 16:39

* Jesper Gødvad

[snip]

> Jeg har købt Sedgewicks bog og læst om hash.


Meget bra.


> Ved kollisioner bruger han linier probing eller alternativt linked
> list's.


Den mest vanlige implementasjonen som jeg vet om er "separate
chaining" -- de elementene som hash'es til samme bucket lagres i en
liste på denne nøkkelen. Linear (eller quadratic) probing er et litt
mer sjeldent beist, svjv.

Forøvrig, Sedgewick dekker en rekke utvidelser av "plain vanilla"
hash.


> Jeg kan se at hele primtals divisionen/multiplikationen skal
> reducere altallet af kollisioner, men der er ingen garanti for at
> samtlige elementer ikke vil ligge i den samme linked list?!


Nei, det er ingen garanti for det. Det går an å konstruere input som
vil være slik at _alle_ elementene vil hashes til samme bucket. Men
det er _veldig lite sannsynlig_ at dette kommer til å skje med et
gjennomsnittlig (og/eller tilfeldig) input.

[snip]


> Hvis man på forhånd intet kender til antallet af elementer kan det
> reducere performance væsentligt, fordi man dynamisk skal udvidde.
> Hvis man på forhånd kender ca. antallet af elementer kan man lave en
> passende tabel før man indsætter.


Det stemmer, bortsett fra at "vesentlig" trenger ikke å være så
dramatisk: en std::vector som vokser dynamisk må også realloc()'es med
jevne mellomrom. Det er som er viktig er at kostnaden av N
push_back()s vokser som O(N). Det tilsvarende gjelder hashtabellen --
man må sørge for at selv om en innsettelse av et nytt element skulle
medføre en reallokering av hele hashtabellen, så skal kostnaden av å
sette inn N elementer vokser fremdeles som O(N). Den "klassiske" måten
å gjøre det på er, iirc, å doble størrelsen av tabellen for
std::vector. Man bruker sikkert en tilsvarende teknikk for
hashtabeller.


> I dine eksempler bruger du en string som key, hvilket tvinger
> std::map til string-compare.


Ehh... ja? Det var bare for å komme med ett eksempel der (imho) en
hashtabell ville ha vært et bedre valg.


> Hvis jeg fx. har string keys der maksimalt er 8 chars og ikke er
> case-sensitive kan jeg reducere antallet af comparisons væsentligt
> ved at omregne min key til int.


Sikkert. Poenget mitt var at det finnes situasjoner der en hashtabell
er bedre enn en map.


> Det vil ikke være hurtigere end hash, men forskellen indsnævres og
> jeg behøver ikke tænke på at den tid det tager at udvide
> hash-tabellen. Mit problem bliver dog ret tydeligt, hvis min
> string-længde vokser til fx. 25 karakterer.


Husk på at det å sette inn N elementer i std::map tar tid som er
proporsjonal med O(NlogN) (og så vidt jeg husker er balansering av
trær forholdsvis tidskrevende). Det å sette inn N elementer i en
hashtabell kan gjøres på O(N) (alltid (også worst case)) til tross for
eventuelle "resize" som man måtte foreta underveis. Forøvrig koster
det _veldig_ lite å sette et element i en hash (i motsetning til en
std::map).

Dersom man ser på N inserts etterfulgt av M oppslag, så er ikke bildet
fullt så pent når det gjelder hashtabeller og garantert ytelse, men
det er fremdeles meget brukbart. Det som er temmelig interessant å se
på er hvor vanskelig det er å konstruere en fornuftig input på et gitt
problem som er slik at en "god" hashfunksjon gjør det veldig dårlig
for nettopp denne input'en.

Derimot, dersom man trenger også å holde elementene sortert, så er
ikke en hashtabell et alternativ, da den ikke har noe ordning blant
elementene.

Valget av datastrukturen er neppe trivielt noen ganger.


> Eksemplet med at hash'e en hel bog kunne bruges af en søge maskine
> til at finde den bog hvor 'C++' optræder flest gange, men ellers er
> det svært at finde på et formål (ja-ja, noget med compilere
> fordi ordene ikke er sorterede.


Det er ikke alltid man trenger en ordning blant elementene. Som sagt,
"The Practice of Programming", ch. 3.


> Jeg går udfra at det er derfor du oftest bruger et std::map og fordi
> det er en del af Standard Library.


Jeg bruker std::map fordi dette er den eneste containeren i stdlib som
greier å representere en funksjon f : K -> V[*], der K er et
ikke-heltallig nøkkelrom og V er verdirommet. Hadde man hatt både hash
og map, ville valgene mine variere mellom disse to, alt ettersom hva
applikasjonen måtte garantere.

BTW:

[quote me -> B. Stroustrup]

IVR> Why doesn't C++ STL have a HashTable class?

BS> because they were completed and proposed too late in the
BS> standards process.

[/quote]


> Har jeg efterhånden forstået hashtabeller korrekt?


FWIW -- så vidt jeg ser, ja.


> Hvis ikke, har jeg valgt 'Avancerede Algoritmer' på næste semester
> og bliver forhåbentligt klogere.


Du bør følge det kurset uansett hvorvidt du føler at du har forstått
poenget med hashtabeller eller ej. Hash vs. RB-tree er neppe det
eneste tema som blir tatt opp.

[snip]





ivr
[*] En nyttig abstraksjon er å tenke på en array, en hash, en map
o.l. som funksjoner fra nøkkelrommet til verdirommet. Da begynner
(aref table index) gi veldig bra mening framfor table[index].
PS: Er ikke vi veldig off-topic nå?
--
Amy: Psst... look what life was like before genetic engeneering.
Leela: Those poor 20th century women...
-- Futurama, "Why must I be a Crustacean in love?"

Mogens Hansen (10-06-2001)
Kommentar
Fra : Mogens Hansen


Dato : 10-06-01 20:59

Hej Jesper,
"Jesper Gødvad" <Xesper@goedvad.dk> wrote in message
news:9ftcss$ies$1@sunsite.dk...
> > > Men hvis man programmere Java får man en klasse forærende, og så
behøver
> > > man ikke tænke meget mere på dét.
> >
> > hashfunktionen skal man vel altid tænke over.
> >
> > Man får også hash-container klasser forærende i C++.
>
> Ja, jeg spør' bare, men hvorfor ville man overhovedet bruge en
> hash-container i C++?

For hurtigt at kunne finde ud af om et givent element findes - er dermed
også få adgang til information, der er relateret til elementet.

>
> Hvad kan en hash-tabel som fx. et multimap ikke kan?
>

Hurtigt (i gennemsnit, men ikke nødvendigvis i værste tilfælde) finde ud af
om et givent element findes.
Til gengæld kan den ikke bruges til at andre operationer, der baserer sig på
sortering af elementerne.

Jon Bentley angiver et eksempel i bogen "Programming Pearls, Second
Edition", side 162-164, hvor antal forekomster af ordene i King James Bible
beregnes, at anvendelsen af en hjemme lavet hash-tabel i stedet for
"std::map" giver en performance forbedring på omkring en faktor 10.

Venlig hilsen

Mogens Hansen



Jesper Gødvad (12-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 12-06-01 17:03


Hej Mogens


> > Hvad kan en hash-tabel som fx. et multimap ikke kan?
> >
> Hurtigt (i gennemsnit, men ikke nødvendigvis i værste tilfælde) finde ud
af
> om et givent element findes.
> Til gengæld kan den ikke bruges til at andre operationer, der baserer sig

> sortering af elementerne.

Kan du ikke give et eksempel på hvornår du sidst har brugt en hash?

Jeg vil gerne vide hvad det er jeg ikke fatter, men har stadig svært ved at
se hvornår man med fordel - i praksis - kan anvende en hash.

> Jon Bentley angiver et eksempel i bogen "Programming Pearls, Second
> Edition", side 162-164, hvor antal forekomster af ordene i King James
Bible
> beregnes, at anvendelsen af en hjemme lavet hash-tabel i stedet for
> "std::map" giver en performance forbedring på omkring en faktor 10.

Jeg skal stadig i gennem Accelerated C++ og The C++ Programming Language, så
bogen må vente lidt.

I Thinking C++ er et tilsvarende eksempel hvor der bruges et std::map og en
overloaded + operator til at tælle ordene. Jeg kan godt se, at std::map skal
finde ordet ved hver eneste forekomst, men hvordan skulle hash kunne gøre
det hurtigere hvis ikke den har entries/nøgler fra "A" til "ZZ"?

mvh. jesper





Mogens Hansen (12-06-2001)
Kommentar
Fra : Mogens Hansen


Dato : 12-06-01 21:01

Hej Jesper,
"Jesper Gødvad" <Xesper@goedvad.dk> wrote in message
news:9g5e75$bl1$1@sunsite.dk...
>
> Hej Mogens
>
>
> > > Hvad kan en hash-tabel som fx. et multimap ikke kan?
> > >
> > Hurtigt (i gennemsnit, men ikke nødvendigvis i værste tilfælde) finde ud
> af
> > om et givent element findes.
> > Til gengæld kan den ikke bruges til at andre operationer, der baserer
sig
> på
> > sortering af elementerne.
>
> Kan du ikke give et eksempel på hvornår du sidst har brugt en hash?

Jeg kan ikke huske at jeg nogensinde har brugt en hash tabel.
Jeg bruger som regel std::map<string, ???> - det er nemt at bruge og stadig
tilstrækkeligt hurtigt i de fleste tilfælde. Det svarer iøvrigt til "A note
on performance" i "Accelated C++", side 136.
Alligevel er det væsentligt at være opmærksom på flere mulige optimeringer i
stedet for at bruge std::map.

>
> Jeg vil gerne vide hvad det er jeg ikke fatter, men har stadig svært ved
at
> se hvornår man med fordel - i praksis - kan anvende en hash.

Det er ofte i forbindelse med behandling af tekst.

To eksempler fra den virkelige verden:

I en compiler kan man bruge det til symbol-tabel, hvor man ved hjælp af
symbolnavnet kan slå op om det f.eks. er en variabel eller en funktion.

Et andet eksempel, som jeg dagligt bruger (men ikke selv skriver - eller
ser), er i forbindelse med CORBA (en netværksteknologi, til at lave objekt
orienteret remote procedure call).
Man definerer et interface (svarende til en abstrakt klasse), med en række
(navngivne) funktioner.
Når CORBA serveren modtager et netværkstelegram, står der i tekst hvilken
funktion der skal kaldes. For hurtigst muligt at kalde den rigtige funktion,
bruges en hash-tabel der konverterer fra funktionsnavnet til en pointer til
den funktion, der skal aktiveres (meget forenklet beskrevet).
Denne anvendelse udmærker sig ved at de lovlige funktionsnavne er bestemt på
compileringstidspunktet (i modsætning til symboltabellen i en compiler). Det
gør at man kan lave en "perfect hashing" funktion, som _garanterer_ O(1)
opslagstid. Hash-tabellen har det samme antal entries som interfacet har
funktioner, så der i hvert "slot" i hash-tabellen er netop eet element.
I forbindelse med build-processen sendes samlingen af funktionsnavne gennem
et værktøj, der genererer hash-funktionen og hash-tabellen.

>
> > Jon Bentley angiver et eksempel i bogen "Programming Pearls, Second
> > Edition", side 162-164, hvor antal forekomster af ordene i King James
> Bible
> > beregnes, at anvendelsen af en hjemme lavet hash-tabel i stedet for
> > "std::map" giver en performance forbedring på omkring en faktor 10.
>
> Jeg skal stadig i gennem Accelerated C++ og The C++ Programming Language,

> bogen må vente lidt.

Der er nok at se til :)

>
> I Thinking C++ er et tilsvarende eksempel hvor der bruges et std::map og
en
> overloaded + operator til at tælle ordene. Jeg kan godt se, at std::map
skal

Det eksempel vil du også finde i "Accelerated C++"

> finde ordet ved hver eneste forekomst, men hvordan skulle hash kunne gøre
> det hurtigere hvis ikke den har entries/nøgler fra "A" til "ZZ"?

Fordi der skal laves langt færre tekst-sammenligninger.
Tekst-sammenligninger er dyre - i forhold til opslag i en vektor med et
indeks.



Venlig hilsen

Mogens Hansen



Jesper Gødvad (17-06-2001)
Kommentar
Fra : Jesper Gødvad


Dato : 17-06-01 15:34


Hej Mogens

> > Kan du ikke give et eksempel på hvornår du sidst har brugt en hash?
>
> Jeg kan ikke huske at jeg nogensinde har brugt en hash tabel.
> Jeg bruger som regel std::map<string, ???> - det er nemt at bruge og
stadig
> tilstrækkeligt hurtigt i de fleste tilfælde. Det svarer iøvrigt til "A
note
> on performance" i "Accelated C++", side 136.

Ja, det gør det minsandten

> To eksempler fra den virkelige verden:
>
> I en compiler kan man bruge det til symbol-tabel, hvor man ved hjælp af
> symbolnavnet kan slå op om det f.eks. er en variabel eller en funktion.

Ak, det skulle du have sagt noget før. Jeg kan godt se idéen og nu har jeg
jo lige programmeret en sql-server med lexer, parser og symboltabel så det
havde været rart at vide. I stedet troede jeg at find() var en
memberfunction til std::vector, men det viste sig kun at være i Borlands
compiler. Så for at få g++ til at kompilere blev det i stedet til linær
søgning.

Nu har sql-serveren flaskehalse der nok er 1000 gange langsommere, så det
betyder intet for performance, men det ville have været rart at lave det
rigtigt.

> Et andet eksempel, som jeg dagligt bruger (men ikke selv skriver - eller
> ser), er i forbindelse med CORBA (en netværksteknologi, til at lave objekt
> orienteret remote procedure call).
> Man definerer et interface (svarende til en abstrakt klasse), med en række
> (navngivne) funktioner.
[klip]

Ja, det kan jeg godt se en fordel i, da man i modsat fald skulle navngive
funktionerne alfabetisk efter hvor meget de bliver brugt. Lidt fjollet vil
nogen måske mene ;)

Tak for hjælpen.

mvh. jesper




Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste