On Wednesday, 9 April 2014 at 23:18:27 UTC, dnspies wrote:
I know that D slices are set up so you can successively append
to them and it only has to re-allocate infrequently, but what
about with prepending?
ie, does D have a way to handle
int[] x;
for(int i=0; i < 1000; i++) {
x = [i] ~ x;
}
efficiently, or is it better to avoid this sort of thing?
Yeah, that's going to re-allocate every time. At the very least,
use std.array.insertInPlace, which will do what it can to avoid
re-allocating, as well as calling un-needed postblits (when
applicable):
int[] x;
for(int i=0; i < 1000; i++)
insertInPlace(x, 0, i);
But even then, insertInPlace has a complexity of O(N), so while
this is "better", it is still far from optimal.
You should try to avoid prepending in a loop altogether if you
can. Try to prefer a solution where:
- you foreach_reverse and you always append.
- you foreach, but assign to the final location (requires setting
length first).
- you foreach, but append, and then std.algorithm.reverse once
done.
Just some ideas.
