What would be the overall best manner(in ease of implementation and speed) to arbitrarily remove an item in the middle of an array while iterating through it?
So far i've thought about simply using D's standard [0...x] ~ [x+1..$] with an array of indexes but wouldn't that just cause slow reallocations? According to wikipedia the performance would be suboptimal.[1]
I've also thought about using a pointer array and just assigning a null pointer when the item doesn't need to be iterated on but i'm not sure which method will result in the fastest execution times for the general case where over half of the items will be removed from the index/pointer array.

Big thanks

[1] - https://en.wikipedia.org/wiki/Dynamic_array#Performance

On Tuesday, 16 February 2021 at 04:20:06 UTC, z wrote:
> What would be the overall best manner(in ease of implementation and speed) to arbitrarily remove an item in the middle of an array while iterating through it?

http://phobos.dpldocs.info/std.algorithm.iteration.filter.html

On Tue, Feb 16, 2021 at 04:20:06AM +0000, z via Digitalmars-d-learn wrote:
> What would be the overall best manner(in ease of implementation and
> speed) to arbitrarily remove an item in the middle of an array while
> iterating through it?
> So far i've thought about simply using D's standard [0...x] ~ [x+1..$]
> with an array of indexes but wouldn't that just cause slow
> reallocations?  According to wikipedia the performance would be
> suboptimal.[1]
> I've also thought about using a pointer array and just assigning a
> null pointer when the item doesn't need to be iterated on but i'm not
> sure which method will result in the fastest execution times for the
> general case where over half of the items will be removed from the
> index/pointer array.
[...]

It depends on what your goal is.  Do you want to permanently remove the items from the array?  Or only skip over some items while iterating over it?  For the latter, see std.algorithm.iteration.filter.

For the former, you can use the read-head/write-head algorithm: keep two indices as you iterate over the array, say i and j: i is for reading (incremented every iteration) and j is for writing (not incremented if array[i] is to be deleted).  Each iteration, if j < i, copy array[i] to array[j].  At the end of the loop, assign the value of j to the length of the array.

Example:

	int[] array = ...;
	size_t i=0, j=0;
	while (i < array.length)
	{
		doSomething(array[i]);
		if (!shouldDelete(array[i]))
			j++;
		if (j < i)
			array[j] = array[i];
		i++;
	}
	array.length = j;

Basically, the loop moves elements up from the back of the array on top of elements to be deleted.  This is done in tandem with processing each element, so it requires only traversing array elements once, and copies array elements at most once for the entire loop.  Array elements are also read / copied sequentially, to maximize CPU cache-friendliness.


T

-- 
Without outlines, life would be pointless.

On Tuesday, 16 February 2021 at 04:43:33 UTC, Paul Backus wrote:
> On Tuesday, 16 February 2021 at 04:20:06 UTC, z wrote:
>> What would be the overall best manner(in ease of implementation and speed) to arbitrarily remove an item in the middle of an array while iterating through it?
>
> http://phobos.dpldocs.info/std.algorithm.iteration.filter.html

Does filter support multiple arguments for the predicate?(i.e. using a function that has a "bool function(T1 a, T2 b)" prototype)
If not could still implement the function inside the loop but that would be unwieldy.
And does it create copies every call? this is important because if i end up using .filter it will be called a 6 to 8 digit number of times.

On Tuesday, 16 February 2021 at 06:03:50 UTC, H. S. Teoh wrote:
> It depends on what your goal is.  Do you want to permanently remove the items from the array?  Or only skip over some items while iterating over it?  For the latter, see std.algorithm.iteration.filter.
The array itself is read only, so it'll have to be an array of pointers/indexes.

> For the former, you can use the read-head/write-head algorithm: keep two indices as you iterate over the array, say i and j: i is for reading (incremented every iteration) and j is for writing (not incremented if array[i] is to be deleted).  Each iteration, if j < i, copy array[i] to array[j].  At the end of the loop, assign the value of j to the length of the array.
>
> Example:
>
> 	int[] array = ...;
> 	size_t i=0, j=0;
> 	while (i < array.length)
> 	{
> 		doSomething(array[i]);
> 		if (!shouldDelete(array[i]))
> 			j++;
> 		if (j < i)
> 			array[j] = array[i];
> 		i++;
> 	}
> 	array.length = j;
>
> Basically, the loop moves elements up from the back of the array on top of elements to be deleted.  This is done in tandem with processing each element, so it requires only traversing array elements once, and copies array elements at most once for the entire loop.  Array elements are also read / copied sequentially, to maximize CPU cache-friendliness.
>
>
> T

This is most likely ideal for what i'm trying to do.(resizes/removes will probably have to propagate to other arrays)
The only problem is that it does not work with the first element but i could always just handle the special case on my own.[1]
I'll probably use .filter or an equivalent for an initial first pass and this algorithm for the rest, thank you both!

[1] https://run.dlang.io/is/f9p29A (the first element is still there, and the last element is missing. both occur if the first element didn't pass the check.)

On Tuesday, 16 February 2021 at 09:08:33 UTC, z wrote:
> Does filter support multiple arguments for the predicate?(i.e. using a function that has a "bool function(T1 a, T2 b)" prototype)

I am not sure exactly what you are asking here, but you can probably accomplish what you want by combining filter with std.range.chunks or std.range.slide.

http://phobos.dpldocs.info/std.range.chunks.html
http://phobos.dpldocs.info/std.range.slide.html

> If not could still implement the function inside the loop but that would be unwieldy.
> And does it create copies every call? this is important because if i end up using .filter it will be called a 6 to 8 digit number of times.

filter does not create any copies of the original array. The same is true for pretty much everything in std.range and std.algorithm.

On 2/16/21 1:03 AM, H. S. Teoh wrote:
> For the former, you can use the read-head/write-head algorithm: keep two
> indices as you iterate over the array, say i and j: i is for reading
> (incremented every iteration) and j is for writing (not incremented if
> array[i] is to be deleted).  Each iteration, if j < i, copy array[i] to
> array[j].  At the end of the loop, assign the value of j to the length
> of the array.

std.algorithm.mutation.remove does this for you.

It's just a bit awkward as it doesn't do this based on values, you have to pass a lambda.

auto removed = arr.remove!(v => v == target); // removed is now the truncated array

And if you don't care about preserving the order, it can be done faster:

auto removed = arr.remove!(v => v == target, SwapStrategy.unstable);

-Steve