Thread Adjazenzlisten als Hash oder als Array? (15 answers)
Opened by pktm at 2009-04-19 11:57

LanX-
 2009-04-21 11:27
#120799 #120799
User since
2008-07-15
1000 Artikel
BenutzerIn

user image
Hi Crian,

du hast recht es zu unterscheiden, im Thread kommen beide Begriffe Adjazenzliste als auch -Matrix vor, ich hab nicht darauf geachtet.

http://www.tilman.de/uni/ws03/alp/adjazenz.php


Deine Beispiele pro Knoten eine Kantenliste abzuspeichern sind zwar sowohl als Array als auch als Hash speichereffizient, aber nicht von der Laufzeit.

Man muss eine Liste durchsuchen, um eine Kante zu finden oder auszuschließen!

Bei einer dünnen Matrix in einem Hash kann ich direkt auf eine Kante zugreifen indem ich $hash{"k1"."k2"} abfrage. Das ist sowohl schnell als auch speichersparend und vor allem einfacher implementiert.

OK zugegeben, je dünner die Matrizen werden, umso besser schneiden Adjazenzlisten ab...leere Listen sind recht schnell durchsucht. ;-)

Aber IMHO stammt diese Technik noch aus Algorithmensammlungen bevor Hashes populär wurden.

NACHTRAG:
Code: (dl )
1
2
3
4
5
my %adjazenz = (
V1V2 => 1,
V2V3 => 1,
V2V4 => 1,
);

Last edited: 2009-04-21 11:42:06 +0200 (CEST)

View full thread Adjazenzlisten als Hash oder als Array?