Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
December 20, 2017 std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
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! |
December 20, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to aliak | 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 |
December 21, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to aliak | 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 |
December 21, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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;
|
December 21, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nicholas Wilson | 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!
|
December 21, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nicholas Wilson | 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 |
December 22, 2017 Re: std way to remove multiple indices from an array at once | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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
|
Copyright © 1999-2021 by the D Language Foundation