perl6 What is a quick way to de-select array or list elements?

Question

To select multiple elements from an array in perl6, it is easy: just use a list of indices:

> my @a = < a b c d e f g >;
> @a[ 1,3,5 ]
(b d f)

But to de-select those elements, I had to use Set:

> say @a[ (@a.keys.Set (-) (1,3,5)).keys.sort ]
(a c e g)

I am wondering if there is an easier way because the arrays I use are often quite large?

Answer 1

@raiphs solution combined with @Jonathan Worthington 's:

The operator should be very efficient for huge numbers and large @not-ats lists as it returns a list of ranges, and it even creates that list of ranges lazily. For the @not-ats it supports integers and ranges with included and excluded bounds and infinity. But it has to be ascending.

The $elems can be a Range or an Int. It is interpreted as .Int as in Jonathan Worthington's solution to support (but needs a .flat applying it to array slicing - the price of performance for the lazy operator - this could be changed by using flat gather instead of lazy gather in the 2nd line)

@a[ (* not-at (1, 3, 5)).flat ];

or newly support

@a[ (* not-at (1, 3^ .. 5, 8 .. 8, 10, 14 .. ^18, 19 .. *)).flat ];

The performance improvements can be seen, when not slicing the array at once, but operating on parts of the array, optimally with multithreading.

sub infix:<not-at> ($elems, @not-ats) {
    lazy gather {
        my $at = 0;
        for @not-ats {                                               # iterate over @not-ats ranges
            my ($stop, $continue) = do given $_ {
                when Int            { succeed $_,       $_         } # 5
                when !.infinite     { succeed .int-bounds          } # 3..8 | 2^..8 | 3..^9 | 2^..^9
                when !.excludes-min { succeed .min,     $elems.Int } # 4..*
                default             { succeed .min + 1, $elems.Int } # 3^..*
            }
            take $at .. $stop - 1 if $at < $stop;                    # output Range before current $not-at range
            $at = $continue + 1;                                     # continue after current $not-at range
        }
        take $at .. $elems.Int - 1 if $at < $elems;                  # output Range with remaining elements
    }
}

Answer 2

sub infix:<not-at> ($elems, @not-ats) {
  my $at = 0;
  flat gather for @not-ats -> $not-at {
    when $at < $not-at { take $at++ xx $not-at - $at } 
    NEXT { $at++ }
    LAST { take $at++ xx $elems - $not-at - 1 }
  }
}

my @a = < a b c d e f g >;
say @a[ * not-at (1, 3, 5) ]; # (a c e g)

I think the operator code is self-explanatory if you know each of the P6 constructs it uses. If anyone would appreciate an explanation of it beyond the following, let me know in the comments.

I'll start with the two aspects that generate the call to not-at.

* aka Whatever

From the Whatever doc page:

When * is used in term position, that is, as an operand, in combination with most operators, the compiler will transform the expression into a closure of type WhateverCode

* is indeed used in the above as an operand. In this case it's the left argument (corresponding to the $elems parameter) of the infix not-at operator that I've just created.

The next question is, will the compiler do the transform? The compiler decides based on whether the operator has an explicit * as the parameter corresponding to the * argument. If I'd written * instead of $elems then that would have made not-at one of the few operators that wants to directly handle the * and do whatever it chooses to do and the compiler would directly call it. But I didn't. I wrote $elems. So the compiler does the transform I'll describe next.

The transform builds a new WhateverCode around the enclosing expression and rewrites the Whatever as "it" aka the topic aka $_ instead. So in this case it turns this:

* not-at (1,3,5)

into this:

{ $_ not-at (1,3,5) }

What [...] as a subscript does

The [...] in @a[...] is a Positional (array/list) subscript. This imposes several evaluation aspects, of which two matter here:

• "it" aka the topic aka $_ is set to the length of the list/array.

• If the content of the subscript is a Callable it gets called. The WhateverCode generated as explained above is indeed a Callable so it gets called.

So this:

@a[ * not-at (1,3,5) ]

becomes this:

@a[ { $_ not-at [1,3,5] } ]

which turns into this:

 @a[ { infix:not-at(7, [1,3,5]) } ]

Answer 3

Given the indexer wants the elements to extract, we could solve this by turning the list of elements to exclude into a list of ranges of elements to extract. That is, given:

1, 3, 5

We'd produce something equivalent to:

0..0, 2..2, 4..4, 6..Inf

Given:

my @exclude = 1, 3, 5;

We can do:

-1, |@exclude Z^..^ |@exclude, Inf

To break it down, zip (-1, 1, 3, 5) with (1, 3, 5, Inf), but using the range operator with exclusive endpoints. This results in, for the given example:

(-1^..^1 1^..^3 3^..^5 5^..^Inf)

Which is equivalent to the ranges I mentioned above. Then we stick this into the indexer:

my @a = <a b c d e f g>
my @exclude = 1, 3, 5;
say @a[-1, |@exclude Z^..^ |@exclude, Inf].flat

Which gives the desired result:

(a c e g)

This approach is O(n + m). It will probably work out quite well if there array is long, but the number of things to exclude is comparatively small, since it only produces the Range objects needed for the indexing, and then indexing by range is relatively well optimized.

Finally, should the flat on the outside be considered troublesome, it's also possible to move it inside:

@a[{ flat -1, |@exclude Z^..^ |@exclude, $_ }]

Which works because the block is passed the number of elements in @a.

Answer 4

Here's another option:

my @a = < a b c d e f g >;
say @a[@a.keys.grep(none(1, 3, 5))];

But all in all, arrays aren't optimized for this use case. They are optimized for working with a single element, or all elements, and slices provide a shortcut for (positively) selecting several elements by key.

If you tell us about the underlying use case, maybe we can recommend a more suitable data structure.