digitalmars.D.learn - std way to remove multiple indices from an array at once

aliak (20/20) Dec 20 2017 Hi, is there a way to remove a number of elements from an array

Steven Schveighoffer (18/42) Dec 20 2017 I'm assuming here indices is sorted? Because it appears you expect that

Nicholas Wilson (19/64) Dec 20 2017 isn't that n log(m), where n is length of array and m is length

aliak (12/27) Dec 21 2017 Ah yes, I guess sorted and unique as well would be the expected
Steven Schveighoffer (12/83) Dec 21 2017 Strictly speaking, yes :) But lg(n) and lg(m) are going to be pretty

aliak (3/8) Dec 22 2017 Noice! :D

Seb (9/29) Dec 20 2017 Try std.algorithm.mutation.remove [1]:

aliak <something something.com> writes:

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!

Dec 20 2017

Steven Schveighoffer <schveiguy yahoo.com> writes:

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

Dec 20 2017

Nicholas Wilson <iamthewilsonator hotmail.com> writes:

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;

Dec 20 2017

aliak <something something.com> writes:

On Thursday, 21 December 2017 at 00:52:29 UTC, Nicholas Wilson 
wrote:
 On Thursday, 21 December 2017 at 00:23:08 UTC, Steven 
 Schveighoffer wrote:
 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.

 auto sortedIdxs = indices.assumeSorted; // also could be =

 It's not going to be as good as hand-written code, complexity 
 wise, but it's definitely shorter to write :)

 -Steve

 If indices is sorted with no duplicates and random access then 
 you can do it in linear time.


Ah yes, I guess sorted and unique as well would be the expected 
input. But nice to see the handling of non-sorted indices.

I tried to search for an assumeUnique function as well (the 
assumeSorted one was nice to see) but it's not what I thought 
it'd be - seems to be more of an assumeUnaliased. And I guess 
there's no assumeUniqueElements.

And the filter approach is nice! :) (just need to account for the 
last ii++ (when filter comes back in I think one case would be ii 
== indices.length and you'd get a range error)

Thanks for the feedback!

Dec 21 2017

Steven Schveighoffer <schveiguy yahoo.com> writes:

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

Dec 21 2017

aliak <something something.com> writes:

On Thursday, 21 December 2017 at 15:59:44 UTC, Steven 
Schveighoffer wrote:
 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

Noice! :D

Dec 22 2017

Seb <seb wilzba.ch> writes:

On Wednesday, 20 December 2017 at 23:01:17 UTC, 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!

Try std.algorithm.mutation.remove [1]:

```
import std.algorithm, std.range, std.stdio, std.typecons;
auto r = 10.iota.array;
r.remove(tuple(2, 4)).writeln;
```

Play with it: https://run.dlang.io/is/RcL3VX

[1] https://dlang.org/phobos/std_algorithm_mutation.html#remove

Dec 20 2017

D Programming

C/C++ Programming

Other

digitalmars.D.learn - std way to remove multiple indices from an array at once