Search code examples
d

Efficient drop every N-th element in array in D

Drop every N-th element from the array in D can be implemented with filter and map. For example:

dchar[] dropN(size_t n, dchar[] arr) {
    return darr.enumerate(1).filter!(tup => tup.index % n != 0).map!(a => a.value).array;
}

void main() {
    dchar[] darr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'];
    dropN(3, darr); // ['a', 'b', 'd', 'e', 'g', 'h', 'j', 'k']
}

However, dropN performs two passes filter and map. I tried to make use of skipOver from std.algorithm.searching but how does it actually work. I tried to reproduce after doc examples but only got true as return value.

How can it be done in a single pass without falling back to for loop?

Solution

  • dropN performs two passes filter and map

    D ranges are lazy. In your example, filter and map do not "iterate" over their input ranges, only array does. So, it is already single-pass.

    An alternative implementation of dropN would be:

    return arr.chunks(n).map!(r => r.take(n-1)).joiner.array;

    One point where performance looks suboptimal is that array does not know the length of the range (due to filter or map+joiner), which causes it to use an appender when building the resultant array.