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]:
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
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
On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:On 12/20/17 6:01 PM, aliak wrote: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;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
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: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!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 :) -SteveIf indices is sorted with no duplicates and random access then you can do it in linear time.
Dec 21 2017
On 12/20/17 7:52 PM, Nicholas Wilson wrote:On Thursday, 21 December 2017 at 00:23:08 UTC, Steven Schveighoffer wrote:Strictly speaking, yes :) But lg(n) and lg(m) are going to be pretty insignificantly different.On 12/20/17 6:01 PM, aliak wrote:isn't that n log(m), where n is length of array and m is length of indices?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 :)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
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. -SteveNoice! :D
Dec 22 2017
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