std way to remove multiple indices from an array at once
Steven Schveighoffer
schveiguy at yahoo.com
Thu Dec 21 15:59:44 UTC 2017
On 12/20/17 7:52 PM, Nicholas Wilson wrote:
> On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:
>> On 12/20/17 6:01 PM, aliak wrote:
>>> Hi, is there a way to remove a number of elements from an array by a
>>> range of indices in the standard library somewhere?
>>>
>>> I wrote one (code below), but I'm wondering if there's a better way?
>>>
>>> Also, can the below be made more efficient?
>>>
>>> auto without(T, R)(T[] array, R indices) if (isForwardRange!R &&
>>> isIntegral!(ElementType!R) && !isInfinite!R) {
>>> T[] newArray;
>>> ElementType!R start = 0;
>>> foreach (i; indices) {
>>> newArray ~= array[start .. i];
>>> start = i + 1;
>>> }
>>> newArray ~= array[start .. $];
>>> return newArray;
>>> }
>>>
>>> // Usage
>>> long[] aa = [1, 2, 3, 4]
>>> aa = aa.without([1, 3])
>>>
>>> Thanks!
>>
>> I'm assuming here indices is sorted? Because it appears you expect
>> that in your code. However, I'm going to assume it isn't sorted at first.
>>
>> Now:
>>
>> import std.range;
>> import std.algorithm;
>>
>> auto indices = [1,2,3,4];
>> aa = aa.enumerate.filter!(a => !indicies.canFind(a[0])).map(a =>
>> a[1]).array;
>>
>> Now, this is going to be O(n^2), but if indices is sorted, you could
>> use binary search:
>>
>> auto sortedIdxs = indices.assumeSorted; // also could be = indices.sort()
>>
>> arr = arr.enumerate.filter!(a => !sortedIdxs.contains(a[0])).map(a =>
>> a[1]).array;
>>
>> Complexity would be O(n lg(n))
>>
>> It's not going to be as good as hand-written code, complexity wise,
>> but it's definitely shorter to write :)
>>
>
> isn't that n log(m), where n is length of array and m is length of indices?
Strictly speaking, yes :) But lg(n) and lg(m) are going to be pretty
insignificantly different.
> If indices is sorted with no duplicates and random access then you can
> do it in linear time.
>
> int i;
> int ii;
> int[] indicies = ...;
> arr = arr.filter!((T t)
> {
> scope(exit) i++;
> if (i == indicies[ii])
> {
> ii++;
> return false;
> }
> return true;
> }).array;
>
Very nice! as aliak mentioned, however, you have a bug, as ii might
extend beyond the size of indicies. So should be if(ii < indices.length
&& indicies[ii] == i).
We are always focused on using a chained one-liner, but your lambda
stretches that ;)
Here's a similar solution with an actual range:
https://run.dlang.io/is/gR3CjF
Note, all done lazily. However, the indices must be sorted/unique.
-Steve
More information about the Digitalmars-d-learn
mailing list