std way to remove multiple indices from an array at once
Nicholas Wilson
iamthewilsonator at hotmail.com
Thu Dec 21 00:52:29 UTC 2017
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 :)
>
> -Steve
isn't that n log(m), where n is length of array and m is length
of indices?
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;
More information about the Digitalmars-d-learn
mailing list