grosse hashes optimieren: 800-900 keys (Allgemeines zu Perl)

lichtkind

2006-06-21 22:38

User since
2004-03-22
5679 Artikel
ModeratorIn + EditorIn

ich überlege grad ob ich den hash aufsplitte in portionen zu ca 200 keys die dann subhashes (HOH) liegen würden oder wären oder ob ich mir sage so wie Perl das intern optimiert kann ich eh nich besser machen.und ich pack alles in einen hash. any erfahrungen?

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

ptk

2006-06-22 00:45

User since
2003-11-28
3645 Artikel
ModeratorIn
[default_avatar]

Keine Erfahrungen, aber es gilt immer der Grundsatz: Opcodes minimieren. Wenn du Subhashes benutzt, verbrätst du eher mehr Opcodes...

docsnyder

2006-06-22 13:43

User since
2005-09-08
300 Artikel
BenutzerIn

800-900 Hashes sind meines Erachtens nicht viel und Perl wird das denkbar effizient handeln können. Alle anderen Kunstgriffe (z.B. HoH) wären Overhead, denke ich.

Gruß, Doc

esskar

2006-06-22 13:59

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

was sind denn das für keys?

lichtkind

2006-06-22 16:33

User since
2004-03-22
5679 Artikel
ModeratorIn + EditorIn

tastenkombinationen, da es in wx nur einen key event gibt, (höchstens enter ist ne ausnahme) muss ich nach schaun welche taste gedrückte wurde und damit es schnell geht sind die coderefs bereits in einem hash dessen key ich nur noch einfüge um commando zu starten. und es werden ca 600 denn es gibt an die 80 normale tasten und 7 möglichekeiten für umschalttasten ok etwas übertrieben 560 kommt letztlich bei 400 was raus, 800 war wirklich zu hoch gegriffen solang ich noch nicht emacs verhalten emulier. da aber umschalttasten eh extra abfragen muss denn row key codes wäre nicht portabel werde ich aber es trotzdem erstmal mit HOH versuchen eben weil der erste Hash nur 7 einträge hat aber die anzahl im unterhash auf ein siebtel kürzt. vielleicht benchmark ich es mal.

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

Taulmarill

2006-06-22 18:17

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

also ich kann kaum einen unterschied zwischen einem hash mit 26 und einem mit 676 keys feststellen.

Code: (dl )

use strict;
use warnings;
use Benchmark qw/cmpthese/;

sub hashmap { my $cnt = 1; map { $_, $cnt++ } @_; }

my @sml_list = ( 'a'..'z' );
my @big_list = map { my $char = $_; map { "$char$_" } 'a'..'z' } 'a'..'z';
my %sml_hash = hashmap( @sml_list );
my %big_hash = hashmap( @big_list );

cmpthese( -1, {
    sml => sub { defined $sml_hash{ $sml_list[ rand @sml_list ] }; },
    big => sub { defined $big_hash{ $big_list[ rand @big_list ] }; },
} );

$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78 0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B

Ishka

2006-06-22 19:02

User since
2003-08-04
771 Artikel
HausmeisterIn

Es bringt einen Geschwindigkeitsgewinn, wenn du die Hashes aufteilst nach (vielen) selten und (wenig) häufig verwendeten Schlüsseln. Ansonsten ist das intern schon ziemlich optimal aufgebaut. Und da der so Vorteil so minimal ist, würde ich aber erst bei 100 000 Schlüsseln anfangen mir darüber Gedanken zu machen.

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}

esskar

2006-06-22 21:35

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

die idee von hashtabellen ist ja, dass man auf die Elemente in O(1) zugreifen kann. Wieviele Schlüssel dann da sind, ist in der Theorie egal.

Ishka

2006-06-22 21:42

User since
2003-08-04
771 Artikel
HausmeisterIn

ist aber nicht O(1), sondern O(ln x). ln x ist aber meist klein genug ;)

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}

esskar

2006-06-22 22:01

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

[quote=Ishka,22.06.2006, 19:42]ist aber nicht O(1), sondern O(ln x). ln x ist aber meist klein genug ;)[/quote]
in perl, ja.
ich hab da jetzt nur von der idee von hashtabellen im allgemeinen gesprochen.