Removing elements from dynamic arrays?
ibisbasenji at gmail.com
Tue Oct 31 12:34:29 PST 2006
Bill Baxter wrote:
> David Medlock wrote:
>> Bill Baxter wrote:
>>> How do I remove an element from a dynamic array?
>>> int a = [1,2,3,4,5];
>>> I tried every syntax I could think of:
>>> a = void;
>>> a[3..4] = void;
>>> a[3..4] = a[3..3];
>>> a = ;
>>> a[3..4] = ;
>>> delete a;
>>> delete a[3..4];
>>> The last one compiles, but fills a with garbage.
>>> I hope the answer isn't:
>>> a = a[0..3] ~ a[4..length];
>> From my personal tools library...
>> // remove an item from an array
>> template drop(T)
>> T drop( inout T arr, int which )
>> debug if ( which>=arr.length)
>> throw new Exception(str.format("Attempt to drop position %s
>> from size %s",which,arr.length));
>> T result = arr[which];
>> int max = arr.length-1;
>> for (; which < max; which++ ) arr[which]=arr[which+1];
>> arr.length= max;
>> return result;
Something you might find interesting/indicative -- I wrote a little test program to time
your function versus that found in Cashew, and with the slicing expression above. Output:
# Array length: 10000
# Iterations removing middle element: 5000
# ---------- Slice syntax: a[0 .. mid] ~ [mid + 1 .. a.length]
# <Benchmark array removals> Baseline 3.460000
# ---------- CashewUtils: a.removeIndex(mid)
# <Benchmark array removals> Time 2.970000 & 1.164983 versus baseline
# ---------- Drop: version 1
# <Benchmark array removals> Time 0.270000 & 12.814815 versus baseline
# ---------- Drop: version 2
# <Benchmark array removals> Time 0.390000 & 8.871795 versus baseline
Drop v2 was an attempt of mine at rewriting your .drop() that, obviously, falls a little
short of the original in performance. I also find it odd that Cashew's .removeIndex() is
actually timing a little master than the slice expression, because that's actually it is:
a wrapper around that very same expression. *confused* Anyhow, clearly your .drop() is
running very fast! I actually expected the opposite, and am surprised/impressed.
Maybe you should release it into Cashew? ;) And maybe I should put more into
benchmarking the entire Cashew array module. There might be a few more placed it could be
>> Even though it returns the array, it modifies it in place.
> Thanks David, this seems like the best answer in terms of efficiency,
> although I suppose the
> a = a[0..3] ~ a[4..length];
> could theoretically be pretty similar depending how the compiler
> implements it.
> There really should be syntax in the language or at least functions like
> the above in the standard library for this (and for removing slices).
# import cashew.utils.array;
# int foo = ... ;
# foo.removeRange(2U, 7U);
# foo.removeSub(foo[1 .. 5]);
That's why I maintain those. Hopefully, eventually, it does spawn a standard library
module. (I'm always looking for ways to further optimize them, but I do want to keep them
-- Chris Nicholson-Sauls
More information about the Digitalmars-d-learn