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

Ishka

2006-06-22 22:51

User since
2003-08-04
771 Artikel
HausmeisterIn

Das klappt auch im Allgemeinen nicht. Lediglich, wenn du dir deine Schlüssel so aussuchst, daß sie auf den Hash-Algorithmus passt, kommst du auf O(1), aber das tun vorgegebene Werte leider selten ;)

O(ln x) ist für den allgemeinen Fall das schnellste, was man hinbekommen kann.

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 23:04

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

nicht der allgemeine Fall, sondern im Allgemeinen.
mir ist schon klar, dass es das nicht geben kann; aber in der Theorie braucht es keine Kollision zu geben.

lichtkind

2006-06-23 01:55

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

ja aber wenn man als key keine variable eingibt sondern ein "gqoutetes Bareword" müsste aber O wirklich = 1 sein weil man ja schon beim compilieren des scriptes zu bytcode weiss wo man jachschauen wird.

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

Es beginnt immer mit einer Entscheidung.

esskar

2006-06-23 02:31

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

nö. der interpreter weiß ja nicht, ob sich der hash zwischendurch geändert hat!

lichtkind

2006-06-23 03:09

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

mag sein das er eine referenz auflösen muss aber die speicherzelle in der struktur bleibt gleich also O(1)

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

Es beginnt immer mit einer Entscheidung.

esskar

2006-06-23 09:18

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

nö.

docsnyder

2006-06-23 11:22

User since
2005-09-08
300 Artikel
BenutzerIn

@lichtkind

Kollisionen sind Kollisionen und die Kosten etwas und zwar mehr als O(1). Ist nun mal so ;o)

Gruß, Doc

lichtkind

2006-06-23 12:31

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

das mag ich grad nicht einsehen denn die kollision kann bereits aufgelöst werden wenn die hashstruktur verändert wird und da zu diesem zeitpunkt keine kollision bestand bin ich immernoch überzeugt das sich das problem mit 0(1) lösen lässt, ähnlich dem 0(1) Dispatcher in Linux.

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

Es beginnt immer mit einer Entscheidung.

esskar

2006-06-23 14:12

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

nö.

docsnyder

2006-06-23 14:58

User since
2005-09-08
300 Artikel
BenutzerIn

@lichtkind

Unter Umständen hast Du bereits bei zwei Hash-Einträgen eine Kollision. Das hängt vom implementierten Algorithmus und den Keys ab.