Removing multiple elements from array

H. S. Teoh hsteoh at quickfur.ath.cx
Fri Dec 20 19:13:59 PST 2013


On Fri, Dec 20, 2013 at 07:01:17PM -0800, Ali Çehreli wrote:
> On 12/20/2013 06:17 PM, aldanor wrote:
> >On Saturday, 21 December 2013 at 01:42:04 UTC, Ali Çehreli wrote:
> >
> >>That's probably a bug, right? The indexes would probably become off as
> >>the array gets shorter.
> >
> >Note the .reverse there?
> 
> Yes, I missed that part. :)
> 
> >Which makes sure indices don't get off. Still,
> >that's probably an inefficient way of doing this...
> 
> Yeah, every removal would move the right-hand elements one position
> to the left. But you would be removing only M times (the number of
> indexes). So the complexity is I think O(M logM) + O(NM) for sorting
> the indexing plus removing M elements by shifting at the order of N
> elements.
> 
> The range solution that I've come up with is I think O(M log M) +
> O(M) + O(N), for sorting the indexes, removing the duplicates with
> uniq and iterating the elements. Since O(M log M) dominates O(M), it
> should be O(M log M) + O(N).
[...]

If you know the which elements you're going to remove, you can remove
them all at once in O(N) time:

	int[] arr = [ ... ];
	for (i=0, j=0; i < arr.length; i++)
	{
		if (deleteThisElement(arr[i]))
			continue;
		if (j < i)
			arr[j] = arr[i];
		j++;
	}
	arr.length = j;

Of course, if you know which *indices* you're going to remove, then you
can do even better (by starting your loop at the first index to be
deleted).


T

-- 
BREAKFAST.COM halted...Cereal Port Not Responding. -- YHL


More information about the Digitalmars-d-learn mailing list