Since the question was about efficiency, I've done some benchmarks with both the supplied data set, and a larger ( 10_000 x 2) random data set.
Here are the results on my lil' old AMD K6-2 400 w/448M RAM:
$ ./pm_temp
Benchmark: timing 50000 iterations of aighearach, aighearach_longrand,
+ ewijaya, ewijaya_longrand, pg, pg_longrand, scooterm, scooterm_longr
+and...
aighearach: 1 wallclock secs ( 0.88 usr + 0.00 sys = 0.88 CPU) @ 56
+818.18/s (n=50000)
aighearach_longrand: 1 wallclock secs ( 0.83 usr + 0.00 sys = 0.83
+CPU) @ 60240.96/s (n=50000)
ewijaya: 4 wallclock secs ( 3.70 usr + 0.00 sys = 3.70 CPU) @ 13
+513.51/s (n=50000)
ewijaya_longrand: 2 wallclock secs ( 3.22 usr + 0.00 sys = 3.22 CPU
+) @ 15527.95/s (n=50000)
pg: 1 wallclock secs ( 0.86 usr + 0.00 sys = 0.86 CPU) @ 58
+139.53/s (n=50000)
pg_longrand: 1 wallclock secs ( 0.99 usr + 0.00 sys = 0.99 CPU) @ 5
+0505.05/s (n=50000)
scooterm: 2 wallclock secs ( 0.95 usr + 0.01 sys = 0.96 CPU) @ 52
+083.33/s (n=50000)
scooterm_longrand: 2 wallclock secs ( 0.86 usr + 0.00 sys = 0.86 CP
+U) @ 58139.53/s (n=50000)
Rate ewijaya ewijaya_longrand pg_longrand scoot
+erm aighearach scooterm_longrand pg aighearach_longrand
ewijaya 13514/s -- -13% -73% -
+74% -76% -77% -77% -78%
ewijaya_longrand 15528/s 15% -- -69% -
+70% -73% -73% -73% -74%
pg_longrand 50505/s 274% 225% --
+-3% -11% -13% -13% -16%
scooterm 52083/s 285% 235% 3%
+ -- -8% -10% -10% -14%
aighearach 56818/s 320% 266% 12%
+ 9% -- -2% -2% -6%
scooterm_longrand 58140/s 330% 274% 15%
+12% 2% -- -0% -3%
pg 58140/s 330% 274% 15%
+12% 2% 0% -- -3%
aighearach_longrand 60241/s 346% 288% 19%
+16% 6% 4% 4% --
Here is the code:
#!/usr/bin/perl -- # -*-PERL-*-
use Data::Dumper;
use Benchmark 'cmpthese';
my @data = ([1,2], [1,3], [2,3], [2,4], [3,4]);
my @data_longrand = map { [ int( rand( 25 ) ), int( rand( 25 ) ) ] } 1
+ .. 10_000;
cmpthese( 50_000,
{ ( map { $_ => qq[$_( \@data )] } qw/ pg scooterm ewijaya aigh
+earach / ),
( map { $_.'_longrand' => qq[$_( \@data_longrand )] } qw/ pg
+scooterm ewijaya aighearach / ),
},
);
sub pg {
my %vertices;
for my $i ( 0 .. $#_ ) {
$vertices{$_[$i][$_]} = 1 for (0 .. $#{$_[$i]});
}
return sort keys %vertices;
}
sub scooterm {
my %hTemp;
my @aTemp = map{@{$_}} @_;
@hTemp{@aTemp} = ();
return sort keys %hTemp;
}
sub aighearach {
my ( %unique );
for ( my $i = 0; $i < @_; $i++ ) {
@unique{@{$_[$i]}} = undef;
}
return sort keys %unique;
}
sub ewijaya {
my @edges = @_;
my @vertices;
my @uniqv;
for my $i ( 0 .. $#edges ) {
for my $j ( 0 .. $#{$edges[$i]} ) {
push @vertices, $edges[$i][$j];
}
}
@uniqv = sort keys %{{map {$_,1} @vertices}};
return @uniqv;
}
__END__