In komplexer Datenstruktur suchen

[Patrick Andrieu]

Hallo alle!

Nehmen wir das Beispiel aus perldoc perldsc (ist auch in »Programmieren mit Perl« vorhanden):

 %TV = (  
     flintstones => {  
         series   => "flintstones",  
         nights   => [ "monday", "thursday", "friday" ],  
         members  => [  
             { name => "fred",    role => "husband", age  => 36, },  
             { name => "wilma",   role => "wife",    age  => 31, },  
             { name => "pebbles", role => "kid",     age  =>  4, },  
         ],  
     },  
  
     jetsons     => {  
         series   => "jetsons",  
         nights   => [ "wednesday", "saturday" ],  
         members  => [  
             { name => "george",  role => "husband", age  => 41, },  
             { name => "jane",    role => "wife",    age  => 39, },  
             { name => "elroy",   role => "kid",     age  =>  9, },  
         ],  
      },  
  
     simpsons    => {  
         series   => "simpsons",  
         nights   => [ "monday" ],  
         members  => [  
             { name => "homer", role => "husband", age => 34, },  
             { name => "marge", role => "wife",    age => 37, },  
             { name => "bart",  role => "kid",     age => [700, 800, 900], },  
         ],  
      },  
  
            others => ['south park', 'sponge bob', 'jimmy newtron'],  
  
            blubb => 'meerjungfraumann',  
   );

^^hier erweitert um zwei weiteren Schlüssel 'others' (Array) und 'blubb' (String)

Und jetzt nehmen wir an, ich habe eine Variable $someone = 'bart';. Habe ich eine Möglichkeit, herauszufinden, ob $someone in der Struktur vorhanden ist, und vor allem wo. Beispiel einer gewünschte Ausgabe wäre: $someone is known as a member of family simpsons and is their son. Also sozusagen der Weg rückwärts. Ich habe einen Wert, und will wissen, welche die enthaltende Struktur ist:

'bart' ist der Wert des Schlüssels 'name' des anonymen Hashs, der den Index 2 im anonymen Array hat, welcher der Wert vom Schlüssel 'members' des anonymen Hashs ist, der wiederum den Wert vom Schlüssel 'simpsons' des Hashs %TV darstellt - uff... ;)

Das folgende führt zwar einigermaßen zum Ziel, gibt es aber etwas Eleganteres?

my $somewhat = '900';  
  
searchfordata(\%TV, $somewhat);  
  
sub searchfordata {  
  my $wheretosearch = shift;  
  my $somewhat = shift;  
  my %wheretosearch = %$wheretosearch;  
  for (keys %wheretosearch) {  
    if (ref $wheretosearch{$_} eq 'ARRAY') {  
      $anarr = $wheretosearch{$_};  
      foreach (@{$wheretosearch{$_}}) {  
        print "$somewhat ist im $anarr\n" if $_ eq $somewhat;                                            # Oder ein Wert in einem Namensarray  
        if (ref $_ eq 'ARRAY') {  
          foreach (@{$wheretosearch{$_}}) {  
            print "$somewhat ist im $anarr\n" if $_ eq $somewhat;  
          }  
        }  
        elsif (ref $_ eq 'HASH') {  
           $anhash = $_;  
           searchfordata($anhash, $somewhat);  
        }  
      }  
    }  
    else {  
       print "$somewhat ist ein Schlüssel von $wheretosearch{$_}\n" if $_ eq $somewhat;                   # Vielleicht ist $somewhat einfach ein Schlüssel  
       print "$somewhat ist ein der Wert von $_ in %wheretosearch\n" if $wheretosearch{$_} eq $somewhat;  # könnte ja auch ein Wert sein  
       searchfordata($wheretosearch{$_}, $somewhat);  
    }  
  }  
}

900 ist im ARRAY(0x1831c04)

Bei $somewhat = 'simpsons' :
simpsons ist ein Schlüssel von HASH(0x1831cb8)
simpsons ist ein der Wert von series in %wheretosearch

Viele Grüße aus Frankfurt/Main,
Patrick

[Siechfred]

Habe ich eine Möglichkeit, herauszufinden, ob $someone in der Struktur vorhanden ist, und vor allem wo.

Hilft Dir evtl. Data::Walk?

Siechfred

[Patrick Andrieu]

Hallo Siechfred!

Schön, dass Du wieder angeschlossen bist ;)

Hilft Dir evtl. Data::Walk?

Hört sich gut an, doch die Beispiele sind spärlich und ich komme damit nicht klar:

<cite>
FUNCTIONS
The module exports two functions by default:

walk
  walk &wanted, @items;
  walk %options, @items;
As the name suggests, the function traverses the items in the order they are given. For every object visited, it calls the &wanted subroutine. See "THE WANTED FUNCTION" for details.

walkdepth
</cite>

use Data::Walk;

my %hash = # selber wie im Vorposting

walk &wanted, %hash;
^Z
Undefined subroutine &main::wanted called at C:/Perl/site/lib/Data/Walk.pm line
144.

?

Viele Grüße aus Frankfurt/Main,
Patrick

[Siechfred]

Schön, dass Du wieder angeschlossen bist ;)

Nur im Büro, zu Hause noch nicht :)

FUNCTIONS
The module exports two functions by default:
[...]

Du hast da wohl was missverstanden: Defaultmäßig werden walk und walkdepth exportiert, wanted ist nur ein Platzhalter für Deine Suchfunktion, also die Funktion, die für jedes Element ausgeführt wird, das gefunden wurde. Diese Funktion musst Du schon irgendwo deklarieren. Vom Ansatz her ist Data::Walk mit File::Find vergleichbar.

use Data::Walk;

my %hash = # selber wie im Vorposting

walk &wanted, %hash;

sub wanted {  
  # tu was mit $_  
  # siehe auch [link:http://search.cpan.org/~guido/Data-Walk-1.00/lib/Data/Walk.pm#THE_WANTED_FUNCTION@title=vordefinierte Variablen]  
}

Siechfred

[Patrick Andrieu]

Hallo Siechfred!

Schön, dass Du wieder angeschlossen bist ;)
Nur im Büro, zu Hause noch nicht :)

Ja, aber das ist schon mal was. Und daheim ist für die Familie ;)

Apropos Familie... Nachdem ich mir letztens einen neuen Laptop gegönnt habe, habe ich meinem Patenkind Jacqueline den aus allen Löchern pfeifenden alten gegeben. Und dadurch, dass sie, noch nicht lesen könnend, nur die Spiele von bspw. kika.de spielt, meistens Flash-Animationen, jagt sie dadurch die CPU hoch, und nach ca. 20-30mn erfolgt was ich den geheimen, automatischen Kinderschutz nennen würde: Die Kiste schaltet sich von selbst aus. So kann ich sicher gehen, dass sie nicht am Computer »kleben» bleibt!

Du hast da wohl was missverstanden: Defaultmäßig werden walk und walkdepth exportiert, wanted ist nur ein Platzhalter für Deine Suchfunktion, also die Funktion, die für jedes Element ausgeführt wird, das gefunden wurde. Diese Funktion musst Du schon irgendwo deklarieren.

Ah, Danke. Ja, ich hatte den Abschnitt »the wanted function« zwar gelesen, aber nicht richtig verstanden.

sub wanted {

# tu was mit $_
  # siehe auch [link:http://search.cpan.org/~guido/Data-Walk-1.00/lib/Data/Walk.pm#THE_WANTED_FUNCTION@title=vordefinierte Variablen]
}

  
Ah ja, jetzt erhalte ich Ergebnisse:  
  
~~~perl
use strict;  
use Data::Walk;  
  
my $hash = # wie im OP  
  
walk \&wanted, %hash;  
  
sub wanted {  
  print $Data::Walk::container if $_ eq 'sponge bob';  
}

Ausgabe:
ARRAY(0x187b0c8)

Nur, das erhielt ich mit meiner häßlichen Funktion vom OP irgendwie auch:

Bei $somewhat = 'sponge bob'; ist die Ausgabe:

sponge bob ist im ARRAY(0x1831d30)

ohne 14KB an Modul einzubinden ;). Interessant aber ist die Rekursionstiefe, da wüßte ich nicht, wie ich sowas realisieren könnte, und das werde ich sehr warhscheinlich gebrauchen können. Werde mal weiter mit dem Modul experimentieren, danke für den Tipp!

BTW: Werden die Speicherplätze bei jedem Skriptaufruf neu zugewiesen? Vergl.: ARRAY(0x187b0c8) und ARRAY(0x1831d30) für das Array, das 'sponge bob' enthält.

Viele Grüße aus Frankfurt/Main,
Patrick

[Siechfred]

Ausgabe:
ARRAY(0x187b0c8)

Btw, wenn Du den Inhalt wissen willst, müsstest Du schon dereferenzieren :)

Nur, das erhielt ich mit meiner häßlichen Funktion vom OP irgendwie auch:

Ich gehe kühn davon aus, dass Data::Walk um einiges schneller ist als Deine selbstgebaute Funktion.

BTW: Werden die Speicherplätze bei jedem Skriptaufruf neu zugewiesen? Vergl.: ARRAY(0x187b0c8) und ARRAY(0x1831d30) für das Array, das 'sponge bob' enthält.

Ja.

Siechfred

[Patrick Andrieu]

Hallo Siechfred!

Btw, wenn Du den Inhalt wissen willst, müsstest Du schon dereferenzieren :)

Ja klar:

my $someone = 'marge';  
walk \&wanted, %hash;  
  
sub wanted {  
  if ($_ eq $someone) {  
    my %mother = %$Data::Walk::container;  
    for (keys %mother) {  
      print "$_: $mother{$_}\n";  
    }  
  }  
}

^Z
name: marge
role: wife
age: 37

Ich gehe kühn davon aus, dass Data::Walk um einiges schneller ist als Deine selbstgebaute Funktion.

Bezweifle ich nicht, nur die Funktion schreiben ging schneller als Data::Walk zu verstehen... Ich kann mir unter diesen Optionen (preprocess, postprocess) nichts vorstellen, und ja, es fehlt an konkreten Beispielen. Deswegen nehmen wir das eben gepostet und kehren zurück zur Ausgangsfrage:

von 'marge' (Mutter von 'bart', Frau von 'homer') ausgehend, wie erhalte ich die ganze Familie? Z.B.:

'marge' (wife, 37) is member of 'simpsons'. Other members are: 'homer' (husband, 34), 'bart' (kid, 11)

Ich habe den Eindruck, dass es ohne komplexere Funktion nicht geht, und eben da fehlt mir der Denkschubs ;)

Bisher bin ich so weit:

my $someone = 'marge';  
walk \&wanted, %hash;  
  
my $foo;  
sub wanted {  
  if ($_ eq $someone) {  
    $foo = $Data::Walk::container;  
    my %person = %$foo;  
    for (keys %person) {  
      print "$_: $person{$_}\n";  
    }  
    walk \&wanted2, %hash;  
  }  
}  
  
sub wanted2 {  
  if ($_ eq $foo) {  
    my $bar = $Data::Walk::container;  
    @members = @$bar;  
    foreach my $member(@members) {  
      my %member = %$member;  
      for (keys %member) {  
        print "$_: $member{$_}\n";  
      }  
    }  
  }  
}

^Z
name: marge
role: wife
age: 37
name: homer
role: husband
age: 34
name: marge
role: wife
age: 37
name: bart
role: kid
age: ARRAY(0x183cbec)

Ich kriege es aber nicht rekursiv...

BTW: Werden die Speicherplätze bei jedem Skriptaufruf neu zugewiesen? Vergl.: ARRAY(0x187b0c8) und ARRAY(0x1831d30) für das Array, das 'sponge bob' enthält.

OK. Hatte mich gewundert, dass die Zahlen manchmal gleich sind, manchmal nicht, danke.

Viele Grüße aus Frankfurt/Main,
Patrick

[Siechfred]

Ich kann mir unter diesen Optionen (preprocess, postprocess) nichts vorstellen, und ja, es fehlt an konkreten Beispielen.

Bei Letzterem stimme ich Dir zu, die Beispiele in der Doku sind dürftig. Allerdings ist das mit preprocess und postprocess m.E. gar nicht so kompliziert. "preprocess => &sub1" wird aufgerufen, bevor die wanted-Funktion ausgeführt wird, "postprocess => &sub2" danach.

Leider habe ich im Moment nicht wirklich Zeit, mich damit zu beschäftigen, aber evtl. helfen Dir folgende Links:

http://www.perlmonks.org/?node_id=390153
http://www.perlmonks.org/?node_id=481746

Siechfred

[Patrick Andrieu]

Hallo Siechfred!

Bei Letzterem stimme ich Dir zu, die Beispiele in der Doku sind dürftig. Allerdings ist das mit preprocess und postprocess m.E. gar nicht so kompliziert.

Mittlerweile konnte ich das am Ende doch auch anwenden, sehe allerdings noch keinen Weg, wie ich das »gebrauchen« könnte.

evtl. helfen Dir folgende Links:
http://www.perlmonks.org/?node_id=390153

Wow, super, danke! Das bringt mich auf jeden Fall weiter!

http://www.perlmonks.org/?node_id=481746

Hier finde ich Dumpvalue ganz gut, außer Data::Dumper waren die anderen Module nicht installiert.

Viele Grüße aus Frankfurt/Main,
Patrick

[Don P]

Hallo Patrick,

von 'marge' (Mutter von 'bart', Frau von 'homer') ausgehend, wie erhalte ich die ganze Familie? Z.B.:

'marge' (wife, 37) is member of 'simpsons'. Other members are: 'homer' (husband, 34), 'bart' (kid, 11)

Ich habe den Eindruck, dass es ohne komplexere Funktion nicht geht, und eben da fehlt mir der Denkschubs ;)

Mal rein logisch betrachtet scheint es mir auch unmöglich, dass eine einfache und allgemeine rekursive Funktion das leisten kann, was du anscheinend vorhast.

Wenn z.B. nach gefundener 'marge' auch die anderen members der simpsons ausgegeben werden sollen, dann müssten konsquenterweise (im vorhergehenden Rekursionsschritt) nach dem inzwischen wegen 'marge' gefundenen key "members" auch die anderen Geschwister dieser members ausgegeben werden, nämlich "series" und "nights", und dann wiederum (auch wieder im vorhergehenden Rekursionsschritt) die anderen Geschwister der gefundenen simpsons, also "flintstones" und "jetsons".

Wenn die Datenstruktur eine beliebig tiefe und beliebig strukturierte Verschachtelung von Arrays und Hashes sein kann – es ist ja immer eine Baumstruktur – dann kannst du von einer einfachen rekrusiven Funktion nicht mehr erwarten als etwa "marge ist der name eines members der simpsons", oder "800 ist ein age eines members der simpsons", oder auch "thursday ist ein nights der flintstones".

Da du anscheinend aber in Abhängigkeit von der Rekursionstiefe und womöglich auch sonstwie in Abhängigkeit von der Art der gefundenen Daten manchmal auch Geschwister und sogar deren Kinder ausgeben willst ("Other members are: 'homer' (husband, 34)..."), muss das zwangsläufig zu einem komplizierteren Algorithums führen, der dann wohl nicht mehr allgemein für jede solche Datenstruktur angewendet werden kann, mal ganz abgesehen von den grammatikalischen Schwierigkeiten, die dann für die Ausgabe entstehen ;-)

Gruß, Don P

[Patrick Andrieu]

Hallo Don P!

Ich habe den Eindruck, dass es ohne komplexere Funktion nicht geht, und eben da fehlt mir der Denkschubs ;)
Mal rein logisch betrachtet scheint es mir auch unmöglich, dass eine einfache und allgemeine rekursive Funktion das leisten kann, was du anscheinend vorhast.

Ja, wenn man sich die Funktionen im ersten von Siechfreds geposteten Link anschaut, sie spielen solange Ping Pong, bis alle Bälle aufgebraucht sind... :)

Mit einer einzigen Funktion ist mir die Rekursion auch nicht gelungen.

Da du anscheinend aber in Abhängigkeit von der Rekursionstiefe und womöglich auch sonstwie in Abhängigkeit von der Art der gefundenen Daten manchmal auch Geschwister und sogar deren Kinder ausgeben willst ("Other members are: 'homer' (husband, 34)..."), muss das zwangsläufig zu einem komplizierteren Algorithums führen, der dann wohl nicht mehr allgemein für jede solche Datenstruktur angewendet werden kann, mal ganz abgesehen von den grammatikalischen Schwierigkeiten, die dann für die Ausgabe entstehen ;-)

my %hash = # wie im OP  
  
my %pathdepths;  
my $somebody = 'marge';  
my $family = '';  
  
#### Funktionen aus dem geposteten Beitrag  
dump_data( 0, '$hash', \%hash );  
  
sub dump_data {  
    my ( $level, $base, $data ) = @_;  
    my $nextlevel = $level + 1;  
    if ( ref($data) eq 'ARRAY' ) {  
        foreach my $k ( 0 .. $#{$data} ) {  
            my $baseval = $base . '[' . $k . ']';  
            dump_it( $nextlevel, $baseval, $data->[$k] );  
        }  
    }  
    elsif ( ref($data) eq 'HASH' ) {  
        foreach my $k ( sort( keys( %{$data} ) ) ) {  
            my $baseval = $base . '{' . $k . '}';  
            dump_it( $nextlevel, $baseval, $data->{$k} );  
        }  
    }  
    elsif ( ref($data) eq 'SCALAR' ) {  
        my $baseval = $base;  
        dump_it( $nextlevel, $baseval, ${$data} );  
    }  
  
}  
  
sub dump_it {  
    my ( $nextlevel, $baseval, $datum ) = @_;  
    my $reftype = ref($datum);  
    if ( $reftype eq 'HASH' ) {  
        dump_data( $nextlevel, $baseval, \%{$datum} );  
    }  
    elsif ( $reftype eq 'ARRAY' ) {  
        dump_data( $nextlevel, $baseval, \@{$datum} );  
    }  
    else {  
        process_data( $nextlevel, $baseval, $datum );  
    }  
}  
  
sub process_data {  
    my ( $nextlevel, $baseval, $datum ) = @_;  
    $pathdepths{$baseval} = $datum;  # Hier wird %pathdepths gefüllt  
}  
# Ende Funktionsklau ;)  
  
for (sort keys %pathdepths) {  
  $family = $_ if $pathdepths{$_} eq $somebody;  
  $family =~ s/^\$hash\{(.+?)\}.*/$1/;  
}  
  
if (defined($hash{$family}{members})) {  
   foreach (@{$hash{$family}{members}}) {  
      print "$_->{name} ($_->{role}, $_->{age}) is member of '$family'. Other members are:", $/ if $_->{name} eq $somebody;  
  }  
   foreach (@{$hash{$family}{members}}) {  
      print "$_->{name} ($_->{role}, $_->{age})", $/ unless $_->{name} eq $somebody;  
  }  
}

^Z
marge (wife, 37) is member of 'simpsons'. Other members are:
homer (husband, 34)
bart (kid, ARRAY(0x1841380))

Das geht sicher sehr viel schöner - habe ich gestern auf die Schnelle gemacht - und setzt voraus, dass die Keys des »Oberhashs« tatsächlich den Familien entsprechen, also, dass man die Struktur schon soweit kennt. Aber mit einer Struktur, die man gar nicht kennt, dürfte es schwer sein zu arbeiten; zumindest den Aufbau sollte einigermaßen bekannt sein.

Viele Grüße aus Frankfurt/Main,
Patrick

[Don P]

Hallo Patrick,

Mit einer einzigen Funktion ist mir die Rekursion auch nicht gelungen.

Da meine Kenntnisse der Perl-Syntax ziemlich eingeschlafen sind, will ich mich hier nicht darauf einlassen und poste lieber eine Beschreibung dessen, was ich meine. Ist hoffentlich auch so verständlich.

Auf die Gefahr, dass ich dir nichts neues erzähle, nochmal grundsätzlich zur Rekursion:
Die Datenstruktur ist immer eine Baumstruktur:

  
TV--flintstones--series--flintstones  
    |            |  
    |            nights--monday  
    |            |       |  
    |            |       thursday  
    |            |       |  
    |            |       friday  
    |            |  
    |            members-----name--fred  
    |                     |  |  
    |                     |  role--husband  
    |                     |  |  
    |                     |  age--36  
    |                     |  
    |                     |--name--wilma  
    |                     |  |  
    |                     |  role--wife  
    |                     |  |  
    |                     |  age--31  
    |                     |  
    |                     |--name--pebbles  
    |                        |  
    |                        role--kid  
    |                        |  
    |                        age--4  
   etc.  

Um darin etwas zu suchen, geht man am besten der Reihe nach alle Knoten durch, angefangen also beim TV:

Wenn der übergebene Parameter eine Liste ist (zuerst also TV), geht es sofort in den nächsten Rekursionsschritt mit dem ersten Listenelement als Parameter (flintstones) usw. bis man am Ende des Zweigs angekommen ist (TV->flintstones->series->flintstones). Damit endet der letzte Rekursionsschritt und es geht weiter im vorherigen mit dem nächsten Element der Liste (nights) und wenn das wieder eine Liste ist, dann sofort wieder zum nächsten Rekursionsschritt bis zum Ende (monday), dann wieder zurück bis zum nächsten Element der vorherigen Liste (thursday) usw. usf.

Das ist m.E. soweit die einfachste rekursive Algorithmus, der alle Elemente der Struktur durchläuft, ähnlich File::Find. Genau wie dort oder bei dem genannten Walk-Modul könnte man nun für jeden erreichten Knoten eine Funktion aufrufen, die mit dem besuchten Knoten etwas unternimmt, z.B. einen Vergleich mit dem gesuchten Datum anstellt. Da diese Funktion aber außerhalb der eigentlichen Rekursionskette liegt, müsste sie das Ergebnis des Vergleichs auch irgendwo außerhalb abspeichern, damit alle Rekursionsschritte (auch die vorherigen) darauf zugreifen und die gefundene Übereinstimmung zur Kenntnis nehmen können, oder aber die externe Funktion müsste das Ergebnis an den aufrufenden Rekursionsschritt direkt zurückgeben, damit dieser wiederum einen entsprechenden Wert an den vorherigen Rekusionsschritt weitergeben kann.

Denn für deine Zwecke ist klar, dass, wenn eine Übereinstimmung irgendwo gefunden wird, der vorherige Rekursionsschritt davon Kenntnis erhalten sollte, weil ja derjenige Rekursionsschritt, in dem die Übereinstimmung gefunden wurde, zunächst selbst nicht "weiß", welche Rekursionsschritte vor ihm statt gefunden haben, d.h. eine Ausgabe wie "wilma ist der name eines members der flinstones im TV" kann eigentlich erst zustande kommen, wenn die Rekursion von der gefundenen "wilma" komplett zurückgekehrt ist zur TV-Liste, wobei bei gefundener Übereinstimmung mit dem Suchbegiff (erkennbar z.B. mittels Flag in jeweiligen Rückgabewerten der rekursiven Funktion) die Namen der Elemente rückwärts eingesammelt werden können (wilma->members->fintstones->TV).

Denkbar wäre jetzt, dass man den tieferen Rekursionsschritten jeweils als zusätzliche Parameter Informationen über die besuchten Ebenen mitteilt, z.B. einen Tiefenzähler mitgibt und eine Liste der in direkter aufsteigender Linie breits besuchten Elternelemente. Damit "wüsste" ein Rekursionsschritt jeweils, wo genau er sich befindet und könnte bei gefundener Übereinstimmung sofort reagieren mit z.B. "Wow, ich habe 'wilma' gefunden in Tiefe 4, und weil es Tiefe 4 ist und ein members-hash, gebe ich gleich mal aus: 'wilma ist ein Eltern[Eltern.length] der Eltern[Eltern.length-1] der Eltern[Eltern.length.2]...' Jetzt bin ich also fertig und gebe zurück: 'gefunden!' ". Der vorhergehende Rekursionsschritt "hört" dieses "gefunden!" und kann darauf regieren mit "Wow, wir haben's gefunden in Tiefe 3+1, und weil ich selber in Tiefe 3 bin, gebe ich die anderen Geschwister auch gleich aus: "Other members are: ....".

Soweit ist das alles möglich mit einer einzigen rekursiven Funktion, meine ich jedenfalls. Aber natürlich muss man dann etwas über die Struktur wissen und an geeigneter Stelle die gewünschten Reaktionen bzw. Bedingungen hardcodieren.

Gruß, Don P

[Patrick Andrieu]

Hallo Don!

Die Datenstruktur ist immer eine Baumstruktur:

Wobei ich eine solche vorziehe:

TV (H)
                                     |
          ---------------------------------------------------------
          |               |             |             |           |
    flintstones (H)   jetsons (H)   simpsons (H)   others (A)  blubb (S)
          |               |             |             |           |
   -----------------------                                    'meerjungfraumann'
   |          |           |
series(S) nights (A) members (A)
   |         |          |
'flintst.'

Aber da braucht man viel horizontalen Platz ;)

Soweit ist das alles möglich mit einer einzigen rekursiven Funktion, meine ich jedenfalls. Aber natürlich muss man dann etwas über die Struktur wissen und an geeigneter Stelle die gewünschten Reaktionen bzw. Bedingungen hardcodieren.

Eben das gelingt mir nicht, ich muss immer zuerst in einer ersten Funktion die Schlüssel der enthaltenden Struktur (hier des Hashs %TV), um dann in einer anderen rekursiv arbeiten zu können. Wie man sich beim Durchlaufen etwas merkt, das kann ich (noch) nicht realisieren, weswegen der Link von Siechfred sinnvoll für mich war. Wenn wir die Aufgabe wie folgt stellen:

$someone = 'marge';

Finde heraus, wer/was das ist (Familie: simpsons, Role: Frau), und suche dann alle weiteren Frauen der weiteren Familien (z.B: weitere Frauen sind: bei Flintstones: Wilma; bei Jetsons: Jane; bei others: N/A, bei blubb: N/A).

dann stehe ich schon auf dem Schlauch ;)

Viele Grüße aus Frankfurt/Main,
Patrick

[Patrick Andrieu]

Re!

Wenn wir die Aufgabe wie folgt stellen:

$someone = 'marge';

Finde heraus, wer/was das ist (Familie: simpsons, Role: Frau), und suche dann alle weiteren Frauen der weiteren Familien (z.B: weitere Frauen sind: bei Flintstones: Wilma; bei Jetsons: Jane; bei others: N/A, bei blubb: N/A).

dann stehe ich schon auf dem Schlauch ;)

Doch nicht:

        my $someone = 'marge';  
        my $family;  
 for $family (keys %TV) {  
     my $rec = $TV{$family};   # temporary pointer  
     for my $person ( @{$rec->{members}} ) {  
         if ($person->{name} eq $someone) {  
                    my $role = $person->{role};  
                    print "$someone is $person->{role} in family: $family", $/;  
                    print "Other ", $role, "s are:", $/;  
                    find_roles($role);  
             #push @kids, $person;  
         }  
     }  
        }  
  
        sub find_roles {  
           my $role = shift;  
          # print $role;  
    for $family (keys %TV) {  
     my $rec = $TV{$family};   # temporary pointer  
         for my $person ( @{$rec->{members}} ) {  
                    if ($person->{role} eq $role) {  
                        print "$person->{name} in family: $family", $/ unless $person->{name} eq $someone;  
                    }  
                }  
           }  
        }

^Z
marge is wife in family: simpsons
Other wifes are:
jane in family: jetsons
wilma in family: flintstones

Ein bisschen in Programmieren mit Perl stöbern hilft, Kopfnüsse zu knacken...

Viele Grüße aus Frankfurt/Main,
Patrick

[Don P]

Hallo Patrick,

Na also, es geht doch ;-)

Allerdings ist das jetzt schon sehr konkret, d.h. du weißt im neuen Beispiel genau

a) dass du eine Person suchst,
b) wo Personen in der Struktur zu finden sind,
c) dass du den Namen der gesuchten Person übergibst,
d) dass Personen bestimmte Rollen in einer Familie haben,
und schließlich,
e) dass du alle anderen Personen- und Familiennamen mit derselben Rolle ausgeben willst

Für e) musstest du sogar eine konkrete Routine schreiben, d.h. wenn du dann z.B. noch alle Personen desselben Alters haben wollest (nur die jüngeren Frauen natürlich ;-) – die Machokasse füllt sich langsam), müsste dafür wieder einen separate Funktion geschrieben werden.

Für solche ganz konkreten Abfragen mit viel Wissen über die Datenstruktur braucht man natürlich keine Rekursion. Wenn aber z.B. das Wissen b) gänzlich fehlt, könnte eine rekursive Lösung trotzdem die gewünschte Ausgabe liefern. Z.B könnte ja für jede Familie noch ein Schlüssel neighbours existieren, der ebenfalls persons und roles kennt. Dann könnte eine rekursive Lösung auch die entsprechenden Nachbarsfrauen ausgeben.

Den OP hatte ich nämlich viel allgemeiner verstanden:

Ich habe einen Wert, und will wissen, welche die enthaltende Struktur ist:

'bart' ist der Wert des Schlüssels 'name' des anonymen Hashs, der den Index 2 im anonymen Array hat, welcher der Wert vom Schlüssel 'members' des anonymen Hashs ist, der wiederum den Wert vom Schlüssel 'simpsons' des Hashs %TV darstellt - uff... ;)

Das verstand ich so: Wenn man z.B. "nights" übergibt, könnte eine allgemeine Funktion ausgeben:
"nights ist ein Schlüssel in flintsones
nights ist ein Schlüssel in jetsons
nights ist ein Schlüssel in simpsons"

Und das, ohne dass man vorher das geringste über die Stuktur weiß. Anschließend weiß man dann, dass die Struktur eine Liste mit (u.A. vielleicht) den Schlüsseln flintsones, jetsons und simpsons ist, und dass diese wiederum jeweils einen Schlüssel namens nights haben.

Habe gerade ein bisschen in perlref(1) gestöbert, weil mein "Programmieren mit Perl" noch verliehen ist. Jetzt verstehe ich endlich deinen code :-).

Das verflixte an Perl ist, dass es viele Wege gibt, dasselbe auszudrücken, und dass sich diese für das Auge Wege nur im Detail unterscheiden. Andere Detail-Unterschiede dagegen könne wieder gravierende Unterschiede in der Bedeutung bzw. Auswirkung haben. Wenn man (wie ich) nicht täglich perlt, vergisst man leicht die genaue Bedeutung der "komischen Zeichen" in bestimmten Zusammenhängen und steht dann plötzlich wie der sprichwörtliche "Ochs vor'm Berg" vor einem an sich einfachen Code.

Gruß, Don P

[Patrick Andrieu]

Hallo Don!

Das verstand ich so: Wenn man z.B. "nights" übergibt, könnte eine allgemeine Funktion ausgeben:
"nights ist ein Schlüssel in flintsones
nights ist ein Schlüssel in jetsons
nights ist ein Schlüssel in simpsons"

Ich komme mit Mischfunktionen aus Data::Walk und dem von Siechfred geposteten Beitrag nicht weiter als:

GEFUNDEN als der Wert des Schluessels 'name' in HASH(0x1884a30)
Uebermittelter Wert: HASH(0x1884a30)
Enthaltender Container: ARRAY(0x1884ae4)
HASH(0x1884a30) ist in ARRAY(0x1884ae4)
Uebermittelter Wert: ARRAY(0x1884ae4)
Enthaltender Container: HASH(0x1884b20)
ARRAY(0x1884ae4) ist in HASH(0x1884b20)

für 'homer' und (mit vielen »Use of unitialized value«-Zeilen dazwischen):

GEFUNDEN als ein Schluessel von HASH(0x1884b20)
Uebermittelter Wert: HASH(0x1884b20)
Use of uninitialized value in concatenation (.) or string at - line 90.
Enthaltender Container:
Use of uninitialized value in concatenation (.) or string at - line 98.
HASH(0x1884b20) ist in

für 'nights'.

Gerade die letzte Ausgabe ist interessant, höher als der anonyme Hash, dessen einer Schlüssel ja 'nights' ist, kommt mein Versuch nicht.

Die im OP gestellte Aufgabe ist doch nicht so einfach (wenn nicht vielleicht gar nicht zu realisieren?), denke ich mal... Wir sind hier leider nicht viele Perler, und das Austüfteln einer solchen Funktion/en nimmt sicherlich etwas Zeit in Anspruch.

Habe gerade ein bisschen in perlref(1) gestöbert, weil mein "Programmieren mit Perl" noch verliehen ist. Jetzt verstehe ich endlich deinen code :-).

Ja, ist eigentlich nur ein mehrfaches Dereferenzieren. Vor einigen Monaten hätte ich noch nicht mal gewußt, was es ist ;)

Viele Grüße aus Frankfurt/Main,
Patrick

[Patrick Andrieu]

Hallo Don!

Hatte heute wieder etwas Zeit, zwischendurch arbeite ich auch an einer ähnlichen, doch tiefer verschachtelten Struktur.

Das verstand ich so: Wenn man z.B. "nights" übergibt, könnte eine allgemeine Funktion ausgeben:
"nights ist ein Schlüssel in flintsones
nights ist ein Schlüssel in jetsons
nights ist ein Schlüssel in simpsons"

So. Das Vorhaben ist mit meinen Bordmitteln unmöglich... Mit dem folgenden Skript kann ich jeden Wert ermitteln (ob Wert von Hash-Schlüssel oder Element im Array) und auch die Hash-Schlüssel selbst:

my $searched = 'nights';  
my $hash = \%TV;  
my $seltsam;  
  
getLocation($searched, $hash);          # wir schnappen uns den/die/das Gesuchte und gehen ins Haus ($hash)  
  
sub getLocation {  
  my $searched = shift;  
  my $wheretosearch = shift;            # beim ersten Aufruf ist $wheretosearch unser Haus... aber beim zweiten oder dritten...  
  if (ref $wheretosearch eq 'HASH') {   # könnte es ein in Kammern unterteiltes Zimmer sein  
    my %wheretosearch = %$wheretosearch;  
    for (keys %wheretosearch) {  
      print $wheretosearch{$_}, $/;  
      if ($_ eq $searched) {  
        print "$searched ist ein Schluessel von ", \%wheretosearch, $/;  
        $seltsam = \%wheretosearch;  
        getLocation($seltsam, $hash);  
      }  
      elsif ($wheretosearch{$_} eq $searched) {  
        print "$searched ist der Wert von $_ in %wheretosearch", $/;  
      }  
      else { getLocation($searched, $wheretosearch{$_});  }  
    }  
  }  
  elsif (ref $wheretosearch eq 'ARRAY') {  # oder eine einfache Besenkammer  
    my $where = $_;  
    my @wheretosearch = @{$wheretosearch};  
    for (my $i = 0; $i < @wheretosearch; $i++) {  
      print "$searched is element $i in \@wheretosearch ($where)", $/ if $wheretosearch[$i] eq $searched;  
      getLocation($searched, $wheretosearch[$i]);  
    }  
  }  
}

Ausgabe:
nights ist ein Schluessel von HASH(0x183f0e0)
nights ist ein Schluessel von HASH(0x183f188)
nights ist ein Schluessel von HASH(0x183f320)

Solele, und da kann ich mir die Haare raufen, denn obwohl ich hier Jeena zeige, warum $a != $b ist, tappe ich in die gleiche Falle, und denke die ganze Zeit mit diesen Zeilen:

print "$searched ist ein Schluessel von ", \%wheretosearch, $/;  
$seltsam = \%wheretosearch;  
getLocation($seltsam, $hash);

»Jetzt merke ich mir, wo das Gesuchte gefunden wurde, und gehe damit noch mal rein ins Haus«. Aber, aber, was habe ich Jeena erzählt? Eben. So geht's nicht... Füge mal dem Skript folgenden Code hinzu:

print "Und jetzt schaunmermal:", $/;  
print '$TV{simpsons}: ', $TV{simpsons}, $/;       # alle sind Hashs mit dem Schluessel: 'nights'  
print '$TV{flintstones}: ', $TV{flintstones}, $/;  
print '$TV{jetsons}: ', $TV{jetsons}, $/;

springt es einem sofort ins Auge:

nights ist ein Schluessel von HASH(0x183f08c)
nights ist ein Schluessel von HASH(0x183f134)
nights ist ein Schluessel von HASH(0x183f2cc)
Und jetzt schaunmermal:
$TV{simpsons}: HASH(0x183215c)
$TV{flintstones}: HASH(0x1831eb0)
$TV{jetsons}: HASH(0x183200c)

Viele Grüße aus Frankfurt/Main,
Patrick

[Don P]

Hallo Patrick,

Hatte heute wieder etwas Zeit,

Ich leider nicht, aber ich sehe, du kommst auch selber ganz gut weiter :-)

Mit dem folgenden Skript kann ich jeden Wert ermitteln (ob Wert von Hash-Schlüssel oder Element im Array) und auch die Hash-Schlüssel selbst

Genau so hatte ich mir die Grundfunktion vorgestellt.

»Jetzt merke ich mir, wo das Gesuchte gefunden wurde, und gehe damit noch mal rein ins Haus«. [...] Füge mal dem Skript folgenden Code hinzu:

print "Und jetzt schaunmermal:", $/;

print '$TV{simpsons}: ', $TV{simpsons}, $/;       # alle sind Hashs mit dem Schluessel: 'nights'
print '$TV{flintstones}: ', $TV{flintstones}, $/;
print '$TV{jetsons}: ', $TV{jetsons}, $/;

>   
> springt es einem sofort ins Auge:  
>   
> nights ist ein Schluessel von HASH(0x183f08c)  
> nights ist ein Schluessel von HASH(0x183f134)  
> nights ist ein Schluessel von HASH(0x183f2cc)  
> Und jetzt schaunmermal:  
> $TV{simpsons}: HASH(0x183215c)  
> $TV{flintstones}: HASH(0x1831eb0)  
> $TV{jetsons}: HASH(0x183200c)  
  
Wahrscheinlich hast du die Zeilen nach "Und jetzt schaunmermal" ganz außerhalb von getLocation notiert. Da das Haus dieser Funktion erst mal übergeben wird, ist die Adresse des übergebenen Hashs dann schon wieder anders, irgendwie so.  
  
Ich dachte ohnehin nicht daran, die Ausgabe in Form von "HASH(0xblabla)" zu machen, sondern jeweils den Schlüssel als String auszugeben, in dem der Wert irgendwo tiefer gefunden wurde. Der erste Schlüssel ist allerdings nicht ohne weiteres bekannt (TV), aber tiefer in der Verschachtelung hat man ihn ja immer im Zugriff.  
  
Was deiner Funktion jetzt noch fehlt, ist ein Rückgabewert, der signalisiert, ob und wo (als Hash-Schlüssel, Hash-Wert oder Array-Wert) das gesuchte  gefunden wurde. Die Ausgabe könnte dann etwa so lauten:  
  
"X ist ein  
Wert des Vektors (2,3,5,7,9) des 5-dimensionalen Arrays im Schlüssel Y im Schlüssel Z im Wert des Vektors (2,4) des 2-dimensionalen Arrays im Schlüssel Bla".  
  
Gruß, Don P  

[Patrick Andrieu]

Hallo Don!

Ich hatte heute morgen bereits eine Antwort geschrieben, die ich zunächst nicht posten konnte, weil das Forum Probleme hatte (Christian hat berichtet). Also hatte ich sie im Editor gespeichert. Als das Forum wieder erreichbar war, hatte ich die Antwort gepostet. Doch leider war sie nur kurze Zeit sichtbar, denn anscheinend stürzte das Forum noch ein Mal ab, danach war die Antwort futsch :(

Und da ich nicht mehr zusammenkriege, was ich gepostet hatte, lasse ich es auch sein ;)

Ich leider nicht, aber ich sehe, du kommst auch selber ganz gut weiter :-)

Mit der anderen, wie gesagt dieser ähnlichen Struktur erhalte ich mittlerweile die Ergebnisse, die ich mir wünsche, muss noch an der Reihenfolge der Ausgabe feilen, kurzum: _was_ ich will habe ich, _wie_ ich will noch nicht.

Der erste Schlüssel ist allerdings nicht ohne weiteres bekannt (TV), aber tiefer in der Verschachtelung hat man ihn ja immer im Zugriff.

Naja, der Hash TV ist das Einzige, von dem man weiß, wie es heißt (wenn man die Struktur sonst nicht kennt), ob man ihn jetzt ausliest und %meinHash nennt, spielt keine Rolle: es ist der Eingang zum Haus. Nur, wieviele Zimmer und Besenkammer es gibt, das weiß man in diesem Fall, aber wenn, und das war eigentlich der Grund des Threads, man ein Skript schreiben soll, das aus einer fremden Datei Daten auslesen und damit die Struktur bauen, ist vielleicht nicht bekannt, wie die Struktur am Ende aussieht: habe ich es nur mit Besenkammmern zu tun, habe ich Besenkammer enthaltende Zimmer, habe ich Zimmer mit weiteren Räumen?

Daher dachte ich mit der Frage weiter zu kommen, bin ich ja auch in Fall meiner eigenen Arbeit ;) Nur beim geposteten Beispiel selbst nicht, bzw. mit der gestellten Aufgabe im OP ;)

Viele Grüße aus Frankfurt/Main,
Patrick