Adjazenzlisten als Hash oder als Array? (Allgemeines zu Perl)

[thread]13402[/thread]

Adjazenzlisten als Hash oder als Array?

Leser: 29

Articles: hide open all | hide show old branches

+16 replies
pktm

2009-04-19 11:57

User since
2003-08-07
2921 Artikel
BenutzerIn

Hallo!

Wie würdet ihr eine Adjazenzliste für gerichtete Graphen realisieren? Als Array oder als Hash? Warum?

Grüße, pktm
http://www.intergastro-service.de (mein erstes CMS :) )
- pq
  
  2009-04-19 12:11
  
  User since
  2003-08-04
  12208 Artikel
  Admin1
  
  titel korrigiert s/Aa/Ad/
  Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. -- Damian Conway in "Perl Best Practices"
  lesen: Wie frage ich & perlintro brian's Leitfaden für jedes Perl-Problem
- +2 replies
- murphy
  
  2009-04-19 15:01
  
  User since
  2004-07-19
  1776 Artikel
  HausmeisterIn
  
  Ich finde, das kommt ganz darauf an, welche Informationen zu dem Zeitpunkt, zu dem man die Nachbarn eines Knoten bestimmen will, bereitstehen und was man mit der Information über die Nachbarknoten anfangen will.
  
  Wenn zum Beispiel jeder Knoten ein Objekt ist und man zum Zeitpunkt der Abfrage bereits eine Referenz auf das Objekt hat, würde ich die Nachbarn weder in einem Array noch in einem Hash sondern in einem Feld des Knotenobjektes speichern. Wenn man die Knoten durchnummeriert hat und per Index auf sie zugreift, würde ich ein Array benutzen und ansonsten eher einen Hash.
  
  Wenn man zu einem Knoten alle Nachbarn ermitteln will, reicht es, diese als Liste geliefert zu bekommen. Wenn man Beziehungen zwischen Knoten testen will, wäre eventuell ein Hash mit Nachbarn als Schlüssel nützlich. Um lediglich zu testen ob zwei Knoten benachbart sind, braucht man überhaupt keinen vollen Satz von Nachbarn sondern kann einmal in die eine und einmal in die andere Richtung prüfen ob einer der Knoten ein Kind des anderen ist.
  When C++ is your hammer, every problem looks like your thumb.
  - pktm
    
    2009-04-20 10:47
    
    User since
    2003-08-07
    2921 Artikel
    BenutzerIn
    
    Ich habe mich jetzt für den Hash entschieden. Einerseits, weil die Knoten-IDs nicht immer fortlaufend sind, und auf der anderen Seite, weil ich so auch etwas anderes als Integer als Knoten-ID verwenden kann (z.B. komplexe Zustandsnamen, wie sie bei der Determinisierung entstehen). Dann kann ich das Knoten-Modell nämlich auch in den Algos selbst verwenden, in denen diese komplexen Zustandsnamen entstehen.
    
    Vielen Dank für eure Antworten.
    http://www.intergastro-service.de (mein erstes CMS :) )
- +12 replies
- moritz
  
  2009-04-19 21:35
  
  User since
  2007-05-11
  923 Artikel
  HausmeisterIn
  
  2009-04-19T09:57:18 pktm
  Wie würdet ihr eine Adjazenzliste für gerichtete Graphen realisieren? Als Array oder als Hash? Warum?
  
  Als Array wenn die Adjazenzmatrix dicht ist, als Hash wenn sie spärlich ist.
  Perl 6 - Perls Zukunft
  - +11 replies
  - Hagen
    
    2009-04-20 06:57
    
    User since
    2007-09-06
    233 Artikel
    BenutzerIn
    
    2009-04-19T19:35:21 moritz
    Als Array wenn die Adjazenzmatrix dicht ist, als Hash wenn sie spärlich ist.
    
    Mit welcher Begründung? Ich habe mich zwar damit noch nie beschäftigt und 'nur' gerade eben bei Wikipedia überflogen, aber habe ich mit einem Array nicht mehr Möglichkeiten bzw. wäre ist damit nicht einfacher, insbesondere bei bei gerichteten Graphen. Wie würdest du diese Matrix/Information (sinnvoll) in einem Hash speichern?
    
    Ggf. wäre ja auch noch der Speicherverbrauch interessant.
    Gruß
    Hagen
    - +10 replies
    - Gast wer
      
      2009-04-20 07:11
      
      Bei Array werden auch die nicht besetzten Stellen erzeugt, das bedeutet bei einer dünn besetzten Matrix verschwendest du viel Speicher. Ist die Matrix aber dicht besetzt, überwiegt der Geschwindigkeitsvorteil von Arrays.
      - +9 replies
      - Hagen
        
        2009-04-20 13:26
        
        User since
        2007-09-06
        233 Artikel
        BenutzerIn
        
        Das hatte ich mir schon fast gedacht. Kann ich denn den Speicherverbrauch beeinflussen (oder macht Perl das sogar automatisch); z.B. bräuchte ich ja hier als Speicherwert nur ein Bit.
        Gruß
        Hagen
        
        +8 replies
        
        LanX-
        
        2009-04-20 13:48
        
        User since
        2008-07-15
        1000 Artikel
        BenutzerIn
        
        ob du ein Byte oder ein Bit brauchst ist egal, und würde Array nicht von Hash unterscheiden. Ein Array mit 10000 Speicherstellen braucht immer viel mehr Platz als ein Hash mit 100 Einträgen.
        me and my writeups
        
        +7 replies
        
        Hagen
        
        2009-04-20 14:33
        
        User since
        2007-09-06
        233 Artikel
        BenutzerIn
        
        Danke, aber das war klar ... habe mich wohl ein bisschen falsch Ausgedrückt.
        
        Wenn ich ein Array habe, wie viel Speicherplatz wird denn dann pro Element verbraucht. In diesem Fall würde ja ein Bit ausreichen, d.h. bei einer Matrix von 100 x 100 Felder hätte ich einen Speicherverbrauch von 1.000 Bit für die Nutzdaten.
        Will ich aber z.B. in jedem Element einen Buchstaben speichern können, dann brauche ich schon pro Element 255 Bit, also hätte ich einen Speicherverbrauch von ca. 2,5 MB (100*100*255).
        
        (Ich habe mich mit der Speichernutzung in Perl in beschäftigt, daher sind die Daten mehr geraten).
        
        In anderen Sprachen kann/muss ich ja extra einen Datentyp (z.B. Integer, Real, Char, ...) für so etwas festlegen. Daher bin ich darauf gekommen.
        Gruß
        Hagen
        
        Gast wer
        
        2009-04-20 16:04
        
        Das kommt auf die länge des Strings an, den du speicherst aber minimal ein Byte. Dazu kommen noch etwas Metadaten, bei einem Byte Daten hast verbrauchst du 6Byte, sofern ich mich nicht verlesen habe.
        
        Bei Hashes siht es ähnlich aus, da sind die Schlüssel auch Strings und verbrauchen entsprechend Platz.
        
        Der Datentyp von Perl ist ein Supertyp, der sehr viele verschidenen Daten gelichzeiteig hält. Den Intergerwert, den Stringinhalt, wahr/falsch, und noch ein paar Flags. Das verbraucht ganz ordentlich Platz.
        
        Es gibt aber bei cpan Module, die das Platzsparender machen können. da kann man dann auch typisieren.
        Alternativ kannst du das auch selber von habd Stricken mittels "pack" :)
        
        +5 replies
        
        LanX-
        
        2009-04-20 22:16
        
        User since
        2008-07-15
        1000 Artikel
        BenutzerIn
        
        2009-04-20T12:33:55 Hagen
        Danke, aber das war klar ... habe mich wohl ein bisschen falsch Ausgedrückt.
        
        ich glaube nicht dass es dir klar ist, wenn du einen Graphen mit 100 Knoten und nur 150 Kanten hast brauchts du (falls gerichtet) ein 100x100 Array also
        
        A= 10000 mal a Bytes
        
        statt bei einem Hash
        
        H= 150 mal h Bytes
        
        h kann gar nicht so ungünstig viel größer als a sein, dass sich bei dünnen Matrizen ein Array lohnt, auch wenn du Bytes mit Bits ersetzt.
        
        (tatsächlich sind A und H untere Schranken weil intern mit Zweierpotenzen gerechnet wird, aber egal)
        
        Last edited: 2009-04-20 22:22:50 +0200 (CEST)
        me and my writeups
        
        +3 replies
        
        Crian
        
        2009-04-21 08:44
        
        User since
        2003-08-04
        5873 Artikel
        ModeratorIn
        
        Nein. Hier sollte man die Ebenen nicht durcheinander bringen:
        
        Adjazenzlisten - Matrix
        
        Hash - Array
        
        Es ging darum, Adjazenzlisten zu speichern, diese beinhalten zu jedem Knoten seine Nachbarn.
        
        Die Frage war wohl, ob man es als HoA oder als AoA löst. Dass eine komplette Matrix, die in der Regel zu 90% Nullen enthält, speicherfressender und langsamer ist, sollte klar sein.
        
        Beispiel:
        
        Wir betrachten den Gerichteten Graphen G = (E, K) mit
        E = (V1, V2, V3, V4)
        und
        K = ((V1, V2), (V2,V3), (V2,V4))
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8
        
        V2 V1 *------------>*----------->* V3 | | | v * V4
        
        Matrix:
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8 9
        
        | V1| V2| V3| V4 --+---+---+---+--- V1| 0 | 1 | 0 | 0 --+---+---+---+--- V2| 0 | 0 | 1 | 1 --+---+---+---+--- V3| 0 | 0 | 0 | 0 --+---+---+---+--- V4| 0 | 0 | 0 | 0
        
        Adjazenzlisten:
        
        Code: (dl )
        
        1 2 3 4
        
        a(v1) = (V2) a(v2) = (V3, V4) a(v3) = () a(v4) = ()
        
        mögliche Darstellung als AoA:
        
        Code: (dl )
        
        1 2 3 4 5 6
        
        my @adjazenz = ( [2], [3, 4], [], [], );
        
        mögliche Darstellung als HoA:
        
        Code: (dl )
        
        1 2 3 4 5 6
        
        my %adjazenz = ( V1 => ['V2'], V2 => ['V3', 'V4'], V3 => [], V4 => [], );
        
        Last edited: 2009-04-21 08:46:08 +0200 (CEST)
        s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;
        
        use strict; use warnings; Link zu meiner Perlseite
        
        +2 replies
        
        LanX-
        
        2009-04-21 11:27
        
        User since
        2008-07-15
        1000 Artikel
        BenutzerIn
        
        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)
        me and my writeups
        
        Crian
        
        2009-04-21 13:03
        
        User since
        2003-08-04
        5873 Artikel
        ModeratorIn
        
        Deshalb auch "mögliche", ich wollte nur auf den Unterschied hinaus.
        s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;
        
        use strict; use warnings; Link zu meiner Perlseite
        
        Hagen
        
        2009-04-21 13:53
        
        User since
        2007-09-06
        233 Artikel
        BenutzerIn
        
        Sorry, ich habe nicht so auf den Unterschied zwischen Adjazenzlisten und Matrix geachtet.
        
        2009-04-20T20:16:30 LanX-
        ich glaube nicht dass es dir klar ist, wenn du einen Graphen mit 100 Knoten und nur 150 Kanten hast brauchts du (falls gerichtet) ein 100x100 Array also ...
        
        Das habe ich verstanden, aber danke! Mir ging es "am Schluß" nur noch darum, ob man ein Array platzsparend(er) anlegen kann oder ob das automatisch passiert. Aber meine Frage hat sich geklärt.
        Gruß
        Hagen

View all threads created 2009-04-19 11:57.