1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#!/usr/bin/perl
use warnings;
use strict;
use experimental qw( signatures );
use List::Util qw{ product };
sub unequal_triplets(@ints) {
my $count = 0;
for my $i (0 .. $#ints - 2) {
for my $j ($i + 1 .. $#ints - 1) {
for my $k ($j + 1 .. $#ints) {
++$count if $ints[$i] != $ints[$j]
&& $ints[$j] != $ints[$k]
&& $ints[$k] != $ints[$i]
}
}
}
return $count
}
sub unequal_triplets_optimized(@ints) {
my %seen;
++$seen{$_} for @ints;
my @unique = keys %seen;
my $count = 0;
for my $i (0 .. $#unique - 2) {
for my $j ($i + 1 .. $#unique - 1) {
for my $k ($j + 1 .. $#unique) {
$count += product(@seen{ @unique[$i, $j, $k] });
}
}
}
return $count
}
use Test::More tests => 3 + 3 + 2;
is unequal_triplets(4, 4, 2, 4, 3), 3, 'Example 1 naive';
is unequal_triplets(1, 1, 1, 1, 1), 0, 'Example 2 naive';
is unequal_triplets(4, 7, 1, 10, 7, 4, 1, 1), 28, 'Example 3 naive';
is unequal_triplets_optimized(4, 4, 2, 4, 3), 3, 'Example 1 optimized';
is unequal_triplets_optimized(1, 1, 1, 1, 1), 0, 'Example 2 optimized';
is unequal_triplets_optimized(4, 7, 1, 10, 7, 4, 1, 1), 28,
'Example 3 optimized';
my @long = ((1) x 100, (2) x 30, (3) x 20, (4) x 10, 5);
is unequal_triplets(@long), 123100, 'Long naive';
is unequal_triplets_optimized(@long), 123100, 'Long optimized';
use Benchmark qw{ cmpthese };
cmpthese(-3, {
naive => sub { unequal_triplets(@long) },
optimized => sub { unequal_triplets_optimized(@long) },
});
__END__
Rate naive optimized
naive 13.1/s -- -100%
optimized 28171/s 215647% --
|
