digitalmars.D.learn - Removing elements from dynamic arrays?
- Enjoys Math (40/40) Apr 04 2022 https://forum.dlang.org/post/eih04u$1463$1@digitaldaemon.com
- =?UTF-8?Q?Ali_=c3=87ehreli?= (8/16) Apr 04 2022 I bet 'inout' back then was the equivalent of 'ref' today.
- Salih Dincer (24/57) Apr 04 2022 I'm guessing you're doing this to learn and measure. You might be
- Steven Schveighoffer (23/64) Apr 05 2022 I think this is a bug, it should be `i` you are testing.
- Paul Backus (15/27) Apr 05 2022 I think you can get rid of the ugly pointer arithmetic using
- Steven Schveighoffer (12/41) Apr 05 2022 Yeah, or use enumerate. But it's painful:
- Salih Dincer (24/37) Apr 05 2022 First, you're neglecting the loop. Second, the returned value is
- Steven Schveighoffer (13/56) Apr 06 2022 This is almost equivalent, but it requires a lambda and an allocation.
- Salih Dincer (16/21) Apr 06 2022 I tried to get these results but it didn't work:
- Steven Schveighoffer (19/29) Apr 06 2022 I'm not sure what your code there is trying to do exactly.
- Siarhei Siamashka (25/40) Apr 06 2022 There shouldn't be any significant difference in performance. A
https://forum.dlang.org/post/eih04u$1463$1 digitaldaemon.com A version of the code that takes `T which` as a parameter instead of `int index`. ``` // remove an item from an array template drop(T) { T drop( inout T[] arr, T which ) { int i; T result; for (i=0; i < arr.length; i++) { if (arr[i] == which) { result = arr[i]; break; } } debug if ( which >= arr.length) throw new Exception(str.format("Attempt to drop the %s of value %s from an array, but it was not found.", typeid(T), which)); } for (; i < arr.length; i++) { arr[i] = arr[i + 1]; } arr.length = arr.length - 1; return result; } } ``` It has worse case complexity O(2n) = O(n) whereas the other one can run in half as long minimally and sometimes just as long (but still O(n)), but usually one needs to linear search for the entry first.
Apr 04 2022
=?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> On 4/4/22 16:15, Enjoys Math wrote:https://forum.dlang.org/post/eih04u$1463$1 digitaldaemon.com2006 is a long time ago. :)A version of the code that takes `T which` as a parameter instead of `int index`. ``` // remove an item from an array template drop(T) { T drop( inout T[] arr, T which )I bet 'inout' back then was the equivalent of 'ref' today. Today, I would use remove(): https://dlang.org/library/std/algorithm/mutation/remove.html And where applicable, SwapStrategy.unstable should reduce the number of elements moved. Ali
Apr 04 2022
On Monday, 4 April 2022 at 23:15:30 UTC, Enjoys Math wrote:
```d
// remove an item from an array
template drop(T)
{
T drop( inout T[] arr, T which )
{
int i;
T result;
for (i=0; i < arr.length; i++)
{
if (arr[i] == which)
{
result = arr[i];
break;
}
}
debug if ( which >= arr.length)
throw new Exception(str.format("Attempt to drop the %s
of value %s from an array, but it was not found.", typeid(T),
which));
}
for (; i < arr.length; i++)
{
arr[i] = arr[i + 1];
}
arr.length = arr.length - 1;
return result;
}
}
```
I'm guessing you're doing this to learn and measure. You might be
better off using the slicing method though. It's also possible to
do it with a single loop:
```d
auto dropSlice(T)(T[] array, T which)
{
T[] result;
size_t i; // old index
foreach(index, element; array)
{
if(element == which) {
result ~= array[i..index]; // slice off
i = index + 1;
}
}
return result ~ array[i..$]; // last slice
}
void main()
{
char[] dizi = "abcdefdg".dup;
dizi.dropSlice('d').writeln;
```
SDB 79
Apr 04 2022
On 4/4/22 7:15 PM, Enjoys Math wrote:https://forum.dlang.org/post/eih04u$1463$1 digitaldaemon.com A version of the code that takes `T which` as a parameter instead of `int index`. ``` // remove an item from an array template drop(T) { T drop( inout T[] arr, T which )Note to reader: this is D1 code, so `inout` was equivalent to `ref`.{ int i; T result; for (i=0; i < arr.length; i++) { if (arr[i] == which) { result = arr[i]; break; } } debug if ( which >= arr.length)I think this is a bug, it should be `i` you are testing.throw new Exception(str.format("Attempt to drop the %s of value %s from an array, but it was not found.", typeid(T), which)); }this looks like a stray brace?for (; i < arr.length; i++) { arr[i] = arr[i + 1]; } arr.length = arr.length - 1; > return result; } } ``` It has worse case complexity O(2n) = O(n) whereas the other one can run in half as long minimally and sometimes just as long (but still O(n)), but usually one needs to linear search for the entry first.No, it's O(n) straight up, you are only iterating the entire array once. As others mentioned, std.algorithm.remove can do this now. I'm not entirely sure of the benefit of returning the thing you tried to remove, though I suppose if the parameter defines equality with some extra data that isn't considered, maybe that does help you see what was removed? I'd implement it probably like this (for D2): ```d auto drop(T)(ref T[] arr, T which) { import std.algorithm, std.range; auto f = arr.find(which); debug if(f.empty) throw ...; auto result = arr.front; arr = arr.remove(&f[0] - &arr[0]); // god I hate this return result; } ``` Still O(n). -Steve
Apr 05 2022
On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer
wrote:
I'd implement it probably like this (for D2):
```d
auto drop(T)(ref T[] arr, T which)
{
import std.algorithm, std.range;
auto f = arr.find(which);
debug if(f.empty) throw ...;
auto result = arr.front;
arr = arr.remove(&f[0] - &arr[0]); // god I hate this
return result;
}
```
I think you can get rid of the ugly pointer arithmetic using
`countUntil`:
```d
auto drop(T)(ref T[] arr, T which)
{
import std.algorithm, std.range, std.exception;
auto i = arr.countUntil(which);
debug enforce(i < arr.length, "Not found");
auto result = arr[i];
arr = arr.remove(i);
return result;
}
```
Apr 05 2022
On 4/5/22 11:43 AM, Paul Backus wrote:On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer wrote:Yeah, or use enumerate. But it's painful: ```d auto f = arr.enumerate.find!((v, w) => v[1] == w)(which); auto result = f.front[1]; arr = arr.remove(result[0]); return result; ``` I have a lib somewhere which isn't complete that allows remembering indexes for elements so you can tease out the original index, but it breaks when you use it on strings (of course). -SteveI'd implement it probably like this (for D2): ```d auto drop(T)(ref T[] arr, T which) { import std.algorithm, std.range; auto f = arr.find(which); debug if(f.empty) throw ...; auto result = arr.front; arr = arr.remove(&f[0] - &arr[0]); // god I hate this return result; } ```I think you can get rid of the ugly pointer arithmetic using `countUntil`: ```d auto drop(T)(ref T[] arr, T which) { import std.algorithm, std.range, std.exception; auto i = arr.countUntil(which); debug enforce(i < arr.length, "Not found"); auto result = arr[i]; arr = arr.remove(i); return result; } ```
Apr 05 2022
On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer
wrote:
[...]
I'd implement it probably like this (for D2):
```d
auto drop(T)(ref T[] arr, T which)
{
import std.algorithm, std.range;
auto f = arr.find(which);
debug if(f.empty) throw ...;
auto result = arr.front;
arr = arr.remove(&f[0] - &arr[0]); // god I hate this
return result;
}
```
First, you're neglecting the loop. Second, the returned value is
the first element of the array. It should be as follows:
```d
auto drop2(T)(ref T[] arr, T which)
{
//auto f = arr.find(which);
auto f = arr.find!(a => a == which);
//debug if(f.empty) throw ...;
auto result = f.front; // arr.front;
//arr = arr.remove(&f[0] - &arr[0]);
arr = remove!(a => a == which)(arr);
return result;
}
```
We do not know the wishes of the programmer who made the
development. But it is certain that he scanned until the end of
the array. So it doesn't make sense for the resulting output to
be equal to the ```which```. In summary, one line is enough:
```d
return remove!(a => a == which)(arr);
```
SDB
Apr 05 2022
On 4/5/22 11:47 PM, Salih Dincer wrote:On Tuesday, 5 April 2022 at 14:10:44 UTC, Steven Schveighoffer wrote:oops, yes, that should have been `auto result = f.front`[...] I'd implement it probably like this (for D2): ```d auto drop(T)(ref T[] arr, T which) { import std.algorithm, std.range; auto f = arr.find(which); debug if(f.empty) throw ...; auto result = arr.front; arr = arr.remove(&f[0] - &arr[0]); // god I hate this return result; } ```First, you're neglecting the loop.Second, the returned value is the first element of the array. It should be as follows: ```d auto drop2(T)(ref T[] arr, T which) { //auto f = arr.find(which); auto f = arr.find!(a => a == which);This is almost equivalent, but it requires a lambda and an allocation. So I'm not sure what thing you are trying to do here.//debug if(f.empty) throw ...; auto result = f.front; // arr.front;Yep, that's a bug on my part.//arr = arr.remove(&f[0] - &arr[0]); arr = remove!(a => a == which)(arr);This runs through the array again, instead of just removing the one index that you already know. And also, the original code only removed one element, even if there were multiple matches. Yours removes them all.return result; } ``` We do not know the wishes of the programmer who made the development. But it is certain that he scanned until the end of the array. So it doesn't make sense for the resulting output to be equal to the ```which```. In summary, one line is enough: ```d return remove!(a => a == which)(arr); ```The return is the element that was removed, not the array after removing the element. And even though it might feel equivalent to return the input, we don't know how the elements compare, so the array element might be different than the incoming parameter. -Steve
Apr 06 2022
On Wednesday, 6 April 2022 at 16:54:26 UTC, Steven Schveighoffer wrote:This is almost equivalent, but it requires a lambda and an allocation. So I'm not sure what thing you are trying to do here.I tried to get these results but it didn't work:abcefg h [0, 3] [4, 7] [8, 9] abcefgh I'm a bit old-fashioned and I don't understand these lambda stuff. That's why I coded with classical logic and indexOf... **Source Code:** https://forum.dlang.org/post/pxkhngxmqgiwwymmgoyh forum.dlang.org Actually, I wrote this before, with a few magic touches, I got what I wanted. SDB 79
Apr 06 2022
On 4/6/22 2:32 PM, Salih Dincer wrote:On Wednesday, 6 April 2022 at 16:54:26 UTC, Steven Schveighoffer wrote:This is almost equivalent, but it requires a lambda and an allocation. So I'm not sure what thing you are trying to do here.**Source Code:** https://forum.dlang.org/post/pxkhngxmqgiwwymmgoyh forum.dlang.org Actually, I wrote this before, with a few magic touches, I got what I wanted.I'm not sure what your code there is trying to do exactly. What I meant with my comment above is this: With `arr.find!(someLambda)`, if the lambda is using data from outside the lambda, it needs a closure, which means it may (probably does) allocate your needed data into a GC heap block that will then become garbage after the function is gone. With `arr.find(value)`, it searches the array for something that compares with the value. No allocation happens, and it's equivalent to what you would write in a for loop. Especially for the code in question: ```d arr.find(val); // like a for loop, comparing each element to val arr.find!(v => v == val); // requires a context pointer for val, may allocate. ``` There is no difference functionally -- both perform exactly the same task, but one is just more expensive. -Steve
Apr 06 2022
On Wednesday, 6 April 2022 at 19:28:53 UTC, Steven Schveighoffer wrote:With `arr.find!(someLambda)`, if the lambda is using data from outside the lambda, it needs a closure, which means it may (probably does) allocate your needed data into a GC heap block that will then become garbage after the function is gone. With `arr.find(value)`, it searches the array for something that compares with the value. No allocation happens, and it's equivalent to what you would write in a for loop. Especially for the code in question: ```d arr.find(val); // like a for loop, comparing each element to val arr.find!(v => v == val); // requires a context pointer for val, may allocate. ``` There is no difference functionally -- both perform exactly the same task, but one is just more expensive.There shouldn't be any significant difference in performance. A good optimizing compiler is expected to ensure that templates/lambdas are inlined here and no heap/GC allocation happens. Unfortunately DMD is not an optimizing compiler and this indeed may have some impact on the preferred coding style if people really care about the performance of their code even when it is compiled by DMD. Lambdas and closures aren't even a unique feature of D language. C++ supports them too and sets the bar for performance expectations: https://www.elbeno.com/blog/?p=1068 Currently my own preferred performance test for the optimizing D compiler quality would be this solution of https://atcoder.jp/contests/abc230/tasks/abc230_e based on binary search: * https://atcoder.jp/contests/abc230/submissions/27673369 (D) * https://atcoder.jp/contests/abc230/submissions/27743857 (C++) * https://atcoder.jp/contests/abc230/submissions/27741770 (D with gallopBackwards search policy as a bonus) Using templates from Phobos as building blocks, chaining them together via UFCS and using a lambda is expected to be roughly as efficient as implementing an imperative binary search loop. If this isn't the case, then there's a defect in the compiler to be investigated and fixed.
Apr 06 2022