Problem mit Zugriff auf struct mittels Pointer

Schnelle objektorientierte, kompilierende Programmiersprache.
mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Problem mit Zugriff auf struct mittels Pointer

Beitrag von mfro » Di Jan 09, 2018 3:51 pm

Xin hat geschrieben:
mfro hat geschrieben: ...
Das hat allerdings den möglicherweise unerwünschten Seiteneffekt, dass für nicht erkannte Zeichen neue "leere" Map-Einträge erzeugt werden (was dann allerdings auch bedeutet, dass die gehasht werden und das Programm mit mehr solcher Einträge immer schneller werden müsste).
Dass es schneller wird, halte ich für eine interessante Theorie, ich würde jetzt eher vermuten, je voller die map, desto langsamer...
Ich habe da an etwas Spezielleres gedacht: so ungefähr das Langsamste, was einem mit einer Hashmap passieren kann, ist die Suche in einer ziemlich vollen Map nach einem nicht vorhandenen Schlüssel. Das müsste m.E. schneller werden.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Problem mit Zugriff auf struct mittels Pointer

Beitrag von Xin » Di Jan 09, 2018 4:15 pm

Die Idee einer Hashmap ist ja, dass die Tabelle klein bleibt (um Speicherplatz zu sparen) und der Key zu einem Hash-Wert geändert wird. So könnte man ein char einfach % 16 rechnen und hätte eine Tabelle mit 16 Einträgen, die zum Beispiel auf eine Liste von maximal 16 Key-Value-Paaren verweisen würde, womit die durchschnittliche Suche eines voll besetzten Datensatzes von 128 Vergleichen auf 8 reduziert wird. Je leere die Listen sind, desto schneller ist man aber auch durch. Wenn die Liste nach dem Hash nun 3 Elemente hat, weiß man nach dem dritten Element, dass der gesuchte Key nicht existiert. Legt man ihn nun an, kostet das Zeit und man macht nun vier Vergleiche für den nächsten nicht existierenden Key.
Ich glaube, meine Lösung ist schneller. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Problem mit Zugriff auf struct mittels Pointer

Beitrag von mfro » Di Jan 09, 2018 6:15 pm

Xin hat geschrieben:... So könnte man ein char einfach % 16 rechnen und hätte eine Tabelle mit 16 Einträgen, die zum Beispiel auf eine Liste von maximal 16 Key-Value-Paaren verweisen würde, womit die durchschnittliche Suche eines voll besetzten Datensatzes von 128 Vergleichen auf 8 reduziert wird. ...
Das könnte man. Wenn man täte. Ich habe da mal ein wenig weiter geforscht.

Tatsächlich sieht's aber so aus, dass std::hash<char> für unseren char-Key einen prima 4 bytes langen int-Hash bastelt, in dem es unseren (signed) char vorzeichenrichtig auf 32 Bit erweitert. Wir reden also - wie's aussieht - tatsächlich von einer eher dünn besetzten Hash-Tabelle ...
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Problem mit Zugriff auf struct mittels Pointer

Beitrag von Xin » Di Jan 09, 2018 6:42 pm

mfro hat geschrieben:Tatsächlich sieht's aber so aus, dass std::hash<char> für unseren char-Key einen prima 4 bytes langen int-Hash bastelt, in dem es unseren (signed) char vorzeichenrichtig auf 32 Bit erweitert. Wir reden also - wie's aussieht - tatsächlich von einer eher dünn besetzten Hash-Tabelle ...
Und hast Du mal nachgeforscht, wie groß die Tabelle ist? 32 Bit erlaubt 4 Milliarden Hash-Werte. Mit 8 Multipliziert, also der nachfolgenden Adresse, sind das 32GB für die Tabelle, die dann wirklich sehr dünn besetzt ist. Ich glaube aber nicht, dass die so groß ist ;)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten