Thread Adjazenzlisten als Hash oder als Array?
(15 answers)
Opened by pktm at 2009-04-19 11:57
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: Last edited: 2009-04-21 11:42:06 +0200 (CEST) me and my writeups
|