Speaking of which...
I am looking at my code in Re^6: Travelling problem (Anyone better 86850?) and I am wondering whether it is simple to make it multi-threaded. In the definition of sub path_recursive there is a call to path_recursive. Would it be possible to kick a new thread of for each of these, if the maximal number of threads is not yet encountered and execute it directly if we are at the maximum already?
All the threads need to share the global variable $glength which stores the length of the best path so far.
I have no experience with threads in Perl yet, so if there is a simple modification of my script, I would be grateful for hints...
Update: this is what I am trying and it seems faster:
use strict;
use warnings;
use threads;
use threads::shared;
use List::Util qw( sum min );
my $glength :shared;
my @dist = <DATA>;
$_ = [ split /\s+/ ] and shift @$_ for @dist;
$glength = 0.5 * sum map { sum @$_ } @dist;
sub path_recursive {
my( $bound, $len, $path, $end, $tbv, $dist, $in_a_thread ) = @_;
if( !@$tbv ) {
$len += $dist->[ $path->[-1] ]->[$end];
if( $len < $glength ) {
$glength = $len;
print "$len: @$path $end ",scalar(localtime),"\n";
}
threads->exit() if $in_a_thread;
return;
}
my $last = $dist->[ $path->[-1] ];
my @sorted = sort { $last->[$a] <=> $last->[$b] } @$tbv;
for (1..min($bound,@sorted)){
my $next = shift @sorted;
if( scalar( threads->list(threads::running) ) < 15 ) {
threads->create( \&path_recursive, $bound, $len + $last->[$next]
+, [ @$path, $next ], $end, [ @sorted ], $dist, 1 );
} else {
path_recursive( $bound, $len + $last->[$next], [ @$path, $next ]
+, $end, [ @sorted ], $dist, 0 );
}
push @sorted, $next;
}
}
path_recursive shift(), 0, [ 1 ], 24, [ 2..23 ], \@dist, 0;
sleep 10 while threads->list(threads::running);
__DATA__
|