[Perl] funzione ricorsiva

[gianvituzzi]

Salve,

sto cercando di scrivere una routine ricorsiva in perl che scopra tutti gli "amici" di un "amico" e così via...gli amici vengono identificati in modo univoco da un numero id e vorrei sapendo il numero id d un amico espandermi il più possibile nella "ragnatela"...un esempio della struttura:

io (000001) = [ (000002), (000004), (000019), (000222) ...etc... ];

il mio amico (000002) a sua volta ha altri amici [ (000004), (009521), (000023) ...etc... ]; e così all'infinito...

come vedete (000001) e (000002) hanno un amico in comune (000004)

Mi interesserebbe sapere che approccio logico usereste per riunire in un'unica lista tutti gli amici di tutti e così via...Grazie

[scancode]

ok

[menphisx]

Scusa per non usare delle regex ?

#!/usr/bin/perl

my $input = "(000001) = [ (000002), (000004), (000019), (000222)]";
my @friends;

print "$input\n";

while($input =~ m/\[(.+)\]/g){

        print "$1\n";

        $friends_list = $1;

        while($friends_list =~ m/\((\d+)\)/g){

                print "$1\n";

                push(@friend, $1); 

        }

}

for $i(0..$#friends){

        print "$friends[$i]\n";

}

[gianvituzzi]

uhm...cerco di spiegarvi meglio lo scenario...avete presente myspace?? ogni "amico" ha degli "amici" e ognuno di quegli "amici" ha altri "amici" e così via...io in pratica dovrei creare uno robot che partendo dal mio friend ID prenda tutti i miei friends ID e così via e li aggiunga in una lista. Viene usata una sola subroutine chiamata _return_ids_from_id(id) che si spiega da sola...ora io so come partire ma non come continuare dato che questo robot deve espanders all'infinito o quasi mi era all'inizio venuta in mente l'idea di forkare ogni volta che si saliva di livello ma questa diventerebbe una pazzia.

Ecco come inizierei:

my @ids = _return_ids_from_id(000001) # questo è il mio id e in @ids vanno tutti i miei "amici"

ora dovrei scandire tutti gli @ids e per ognuno ritornare tutta la lista di amici e così via...

foreach my $id ( @ids )
{
      my @ids = _return_ids_from_id($id);

      foreach my $id ( @ids )
      {

           my @ids = _return_ids_from_id($id)

           ...etc... e così via all'infinito
       }

}

spero di essere stato più chiaro...Grazie!

[menphisx]

no ho capito, ma il codice che ti ho scritto non va bene, non puoi adattarlo ?
Una cosa del genere:
Passi l'id -> Regex estrae tutti gli altri -> Per ogni id richiama la funzione ricorsivamente.

#Pseudocode

sub getFriends {
   
   my $id = shift;
   
   my @amici = prendi_gli_amici_di_$id;
   
   foreach(@amici){
      
       getFriends($_);
      
   }
   
}

naturalmente salvi il risultato in qualche file.

P.S.: è un qualcosa di abbastanza lento, la ricorsione, soprattuto eni linguaggi come perl, può far schizzare la CPU al 100%

[menphisx]

no ho capito, ma il codice che ti ho scritto non va bene, non puoi adattarlo ?
Una cosa del genere:
Passi l'id -> Regex estrae tutti gli altri -> Per ogni id richiama la funzione ricorsivamente.

#Pseudocode

sub getFriends {
   
   my $id = shift;
   
   my @amici = prendi_gli_amici_di_$id;
   
   foreach(@amici){
      
       getFriends($_);
      
   }
   
}

naturalmente salvi il risultato in qualche file.

P.S.: è un qualcosa di abbastanza lento, la ricorsione, soprattuto nei linguaggi come perl, può far schizzare la CPU al 100%

[gianvituzzi]

#
# start
#

&_getFriends(000001); # my id

sub _getFriends {
   
   my $id = shift;
   
   my @amici = _return_ids_from_id($id);

   &_saveid(@amici); ## or &_saveid($id)
   
   foreach(@amici){
      
       &_getFriends($_);
      
   }
   
}

credo che così possa funzionare...ma come risolvo questo problema della CPU?? dovrei scaricare tutti gli array su file di testo?? e quindi far lavorare più su disco che su ram?

Grazie

[menphisx]

La mia era solo un'osservazione.
Hai provato lo script ? Se non è moolto lento, non c'è problema.
Dicevo di salvare su file perchè è più comodo farlo, ma puoi benissimo salvare dove ti pare

[menphisx]

Aspetta, ho dimenticato la condizione di arresto:

#
# start
#

&_getFriends(000001); # my id

sub _getFriends {
   
   my $id = shift;
   
   my @amici = _return_ids_from_id($id);

   &_saveid(@amici); ## or &_saveid($id)
   
   return if($#amici == 1);
   
   foreach(@amici){
      
       &_getFriends($_);
      
   }
   
}

[gianvituzzi]

è vero...devo prendere in considerazione anche il fatto che io potrei stare nella lista di qualcuno e magari qualche amico mio già scandito potrebbe stare nella lista di qualcuno questo creerebbe un ricorsività all'infinito...