Filtering an array with many keys of same length in Perl 6

user_7730888 0
Viewed 181

This question continues the previous one about filtering (the variable names are changed from array & search to source & keys).

Suppose there are even more elements and more keys. The program should print only those element of the @source which begin with any of @keys. So, jjjjk will be printed, but jjjkk won't.

Here's the most straightforward way to solve the problem, but it's too slow to be used:

my @source = "aaaaa" .. "kkkkk";
my @keys = "aaaa" .. "jjjj";

.put for @source .grep: /^ @source /;

# produced 4 elements in 60 seconds
# out of 10 ** 4 * 11 = 110_000
# will take ~19 days to finish

Using .Any and .starts-with() makes it ~100x faster:

my @source = "aaaaa" .. "kkkkk";
my @keys = "aaaa" .. "jjjj";
my $keys_any = @keys.any;

.put for @source .grep: *.starts-with($keys_any);

# produced 700 elements in 110 seconds
# will take ~4.5 hours

If we pre-compile the regex, it works much (~15000x) faster:

my @source = "aaaaa" .. "kkkkk";
my @keys = "aaaa" .. "jjjj";
my $keys = "/@keys.join('|')/".EVAL;

.put for @source .grep: /^ <$keys> /;

# produced all the elements in 100 seconds

Nevertheless, it's still too long, so I've decided to take advantage of the fact that all the keys are of the same length. So, I use a Set of @keys to check substrings of the same length of the @source array:

my @source = "aaaaa" .. "kkkkk";
my @keys = "aaaa" .. "jjjj";
my $keys = @keys.Set;

for @source -> $str {
  my $substring = $str.substr(0, 4);
  if $substring (elem) $keys {
     put $str;
     next;
   }
}

# produced all the elements in 3 seconds

I feel though, that I'm reinventing the wheel and that there should be built-in instruments and methods to do such things?

raku
2 Answers

I feel though, that I'm reinventing the wheel and that there should be built-in instruments and methods to do such things?

There are built-in methods to do such things, as you have demonstrated yourself. They should "just" be optimized to the point where they are fast enough for your use cases.

If compiler optimizations are not your thing, you can contribute to the Perl 6 Core Development Fund to enable smart and dedicated people to work on it.

user_141320

At present, I'll stick to the following solution, which uses the magic of Sets inside a regex, since it's more general than the one with .substr in my Q.

my @source = "aaaaa" .. "kkkkk";
my @keys = "aaaa" .. "jjjj";
my $keys = @keys.Set;

for @source -> $str {
  $str ~~ m/ ^ ( . ** 4 ) <?{ ~$0 (elem) $keys }> /;
  put $str if so $/;
}

# produced all the elements in 11 seconds
user_77308880
Related