Skip to content

Instantly share code, notes, and snippets.

@rcmlz
Last active November 18, 2022 17:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rcmlz/3e604059949f08c7ea1d6380265459a2 to your computer and use it in GitHub Desktop.
Save rcmlz/3e604059949f08c7ea1d6380265459a2 to your computer and use it in GitHub Desktop.
Raku subsequences of array
#!/usr/bin/env raku
sub subsequences_classic($input where .elems > 0){
my $n = $input.elems();
my @result;
for ^$n -> $start { # start at every element of array
for ^($n-$start) -> $end { # add every subsequence starting here
@result.push($input[$start .. $start+$end]);
}
}
return @result;
}
sub subsequences_gather($input where .elems > 0){
my $n = $input.elems();
gather { # use lazy gather if appropriate
for ^$n -> $start { # start at every element of array
for ^($n-$start) -> $end { # add every subsequence starting here
take $input[$start .. $start+$end];
}
}
}
}
sub subsequences_map($input where .elems > 0){
my $n = $input.elems();
[^$n].map(-> $start { # all elements 0..n-1 are a first element of a subsequences
[^($n-$start)].map(-> $end { $($input[$start .. $start+$end])}) # all possible lengths of subsequence
} ).flat # $(): Note that Scalars around a list will make it immune to flattening.
}
sub test{
say "Testing:";
my @input = 1,2,3;
print "classic:";
say subsequences_classic(@input) == [[1],[2],[3],[1,2],[2,3],[1,2,3]];
print "gather:";
say subsequences_gather(@input) == [[1],[2],[3],[1,2],[2,3],[1,2,3]];
print "map:";
say subsequences_map(@input) == [[1],[2],[3],[1,2],[2,3],[1,2,3]];
}
sub benchmark{
use Bench;
my $b = Bench.new;
my @input = 1 xx 50;
$b.cmpthese(1000, {
gather => sub { subsequences_gather(@input) },
map => sub { subsequences_map(@input) },
classic => sub { subsequences_classic(@input) },
});
}
sub MAIN($benchmark=1){
test();
benchmark() if $benchmark;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment