PDA

Visualizza la versione completa : [Perl] funzione ricorsiva


gianvituzzi
14-05-2008, 01:06
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
14-05-2008, 01:36
ok

menphisx
14-05-2008, 01:56
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
14-05-2008, 10:42
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
14-05-2008, 10:51
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
14-05-2008, 10:52
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
14-05-2008, 11:22
#
# 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
14-05-2008, 11:53
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
14-05-2008, 13:01
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
14-05-2008, 13:27
è 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...

Loading