Fastest way to "ignore" elements from array without removal

[H. S. Teoh]

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.