www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Removing multiple elements from array

reply "aldanor" <i.s.smirnov gmail.com> writes:
Is there an efficient method to remove elements with multiple 
(compile-time-unknown) indices from an array? I currently do 
something like

		if (!index.empty)
			foreach (i; index.sort.reverse)
				a = a.remove(i);

... which looks a bit awkward.
Dec 20 2013
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 12/20/2013 04:47 PM, aldanor wrote:

 Is there an efficient method to remove elements with multiple
 (compile-time-unknown) indices from an array? I currently do 
something like
          if (!index.empty)
              foreach (i; index.sort.reverse)
                  a = a.remove(i);
That's probably a bug, right? The indexes would probably become off as the array gets shorter.
 ... which looks a bit awkward.
I am sure others can come up with solutions but I can't think of a way of doing this Phobos right now. :) Here is a range that does what you want (not very well tested ;) ): import std.stdio; import std.array; import std.range; import std.algorithm; struct SkipIndexes(R, I) { alias SortedIndexRange = typeof((I.init).sort.uniq); R range; SortedIndexRange indexes; size_t currentIndex; this(R range, I indexes, size_t currentIndex = 0) { this.range = range; this.indexes = indexes.sort.uniq; this.currentIndex = currentIndex; prime(); } bool empty() const property { return range.empty; } ElementType!R front() const property { return range.front; } void prime() { while (!empty && !indexes.empty && (indexes.front == currentIndex)) { range.popFront(); indexes.popFront(); ++currentIndex; } } void popFront() { range.popFront(); ++currentIndex; prime(); } auto save() property { return this; } void report() const { writeln(indexes); writeln(currentIndex); } } auto skipIndexes(R, I)(R range, I skipIndexes, size_t currentIndex = 0) { return SkipIndexes!(R, I)(range, skipIndexes, currentIndex); } void main() { auto arr = [ 0, 1, 2, 3, 4, 5 ]; size_t[] badIndexes = [ 0, 1, 5 ]; auto skipped = arr.skipIndexes(badIndexes); // skipped is a lazy range: assert(skipped.equal([ 2, 3, 4 ])); // arr is untouched at this point: assert(arr == [ 0, 1, 2, 3, 4, 5 ]); // To affect it, assign from .array of the lazy range: arr = skipped.array; assert(arr == [ 2, 3, 4 ]); } Ali
Dec 20 2013
parent reply "aldanor" <i.s.smirnov gmail.com> writes:
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? Which makes sure indices don't get off. Still, that's probably an inefficient way of doing this...
Dec 20 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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). Ali P.S. Hm. I think I've reading an algorithms book lately. :p
Dec 20 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
Dec 20 2013
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Dec 20, 2013 at 07:13:59PM -0800, H. S. Teoh wrote:
 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;
There's also a Phobos solution: the above code is equivalent to: import std.algorithm : remove; int[] arr = [ ... ]; arr = arr.remove!deleteThisElement();
 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).
[...] Unfortunately, while std.algorithm.remove does provide a way to do this if the number of indices to remove are known beforehand, it doesn't seem to be able to remove a dynamic list of indices. Probably an enhancement request should be filed: http://d.puremagic.com/issues If the number of indices to remove are fixed, though, you can do this: import std.algorithm : remove; int[] arr = [ ... ]; int i1, i2, i3; // indices to remove arr = arr.remove(i1, i2, i3); T -- It's bad luck to be superstitious. -- YHL
Dec 20 2013
parent "aldanor" <i.s.smirnov gmail.com> writes:
On Saturday, 21 December 2013 at 03:22:22 UTC, H. S. Teoh wrote:
 Unfortunately, while std.algorithm.remove does provide a way to 
 do this
 if the number of indices to remove are known beforehand, it 
 doesn't seem
 to be able to remove a dynamic list of indices. Probably an 
 enhancement
 request should be filed:

 	http://d.puremagic.com/issues

 If the number of indices to remove are fixed, though, you can 
 do this:

 	import std.algorithm : remove;
  	int[] arr = [ ... ];
 	int i1, i2, i3;  // indices to remove
 	arr = arr.remove(i1, i2, i3);
Yes, this is exactly why I opened this thread initially, I noticed this functionality in .remove() and was native enough to assume there's a shortcut for batch removal with indices unknown in advance :)
Dec 21 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
aldanor:

 Is there an efficient method to remove elements with multiple 
 (compile-time-unknown) indices from an array? I currently do 
 something like

 		if (!index.empty)
 			foreach (i; index.sort.reverse)
 				a = a.remove(i);

 ... which looks a bit awkward.
Do not forget to add the () after the sort, otherwise you call the deprecated, buggy and slow built-in sort. reverse is another deprecated built-in, so use "retro". The first "if" is not much useful, trying to sort an empty array will not wast much time. foreach (i; index.sort().retro) a = a.remove(i); In alternative you can also invert the sorting cmp (untested): foreach (i; index.sort!q{a > b}) a = a.remove(i); If you have to remove just few items in-place, that's the way to do it. In future I hope we'll have a better remove function in Phobos (but it's not hard to write). Another solution is to filter the array a. If you have the indexes, you can zip a with the indexes, and then filter, map to extract just the items and use copy() to work in place, but it's not nice-looking code. Bye, bearophile
Dec 20 2013
parent "aldanor" <i.s.smirnov gmail.com> writes:
On Saturday, 21 December 2013 at 02:52:00 UTC, bearophile wrote:
 Do not forget to add the () after the sort, otherwise you call 
 the deprecated, buggy and slow built-in sort.

 reverse is another deprecated built-in, so use "retro".

 The first "if" is not much useful, trying to sort an empty 
 array will not wast much time.

 foreach (i; index.sort().retro)
     a = a.remove(i);

 In alternative you can also invert the sorting cmp (untested):

 foreach (i; index.sort!q{a > b})
     a = a.remove(i);
Thanks, that looks like the cleanest solution so far! So (I guess) it will not cause index.length reallocations by just moving the elements in-place and then returning a slice? P.S. I wonder where would one learn about the deprecated sort and reverse if not from this forum? I followed the official docs and there's nothing about these properties being deprecated... yet another spot where a compiler warning would be appropriate?
Dec 21 2013
prev sibling parent reply "MrSmith" <mrsmith33 yandex.ru> writes:
On Saturday, 21 December 2013 at 00:47:04 UTC, aldanor wrote:
 Is there an efficient method to remove elements with multiple 
 (compile-time-unknown) indices from an array? I currently do 
 something like

 		if (!index.empty)
 			foreach (i; index.sort.reverse)
 				a = a.remove(i);

 ... which looks a bit awkward.
just use foreach_reverse
Dec 21 2013
parent reply "aldanor" <i.s.smirnov gmail.com> writes:
On Saturday, 21 December 2013 at 21:49:01 UTC, MrSmith wrote:
 On Saturday, 21 December 2013 at 00:47:04 UTC, aldanor wrote:
 Is there an efficient method to remove elements with multiple 
 (compile-time-unknown) indices from an array? I currently do 
 something like

 		if (!index.empty)
 			foreach (i; index.sort.reverse)
 				a = a.remove(i);

 ... which looks a bit awkward.
just use foreach_reverse
Wow, I never knew it is a keyword, thank you!
Dec 21 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 12/21/2013 05:39 PM, aldanor wrote:

 On Saturday, 21 December 2013 at 21:49:01 UTC, MrSmith wrote:
 just use foreach_reverse
Wow, I never knew it is a keyword, thank you!
I feel guilty for omitting in knowingly but we've been hearing that it would be deprecated. I don't think it will ever happen. :-/ Besides, I think retro(), its alternative, is not suitable for recursive algorithms because retro() works only with ranges. I had once tried to do recursive iteration with ranges (probably on a tree) but it had turned out that iteration with opApplyReverse was more natural for recursion. (I may be wrong on my conclusion but that is what I remember now.) Ali
Dec 21 2013