On 04/06/13 00:57, Steven Schveighoffer wrote:
On Fri, 31 May 2013 21:04:47 -0400, Peter Williams
<pwil3...@bigpond.net.au> wrote:
I do like the idea that "~=" is generally cheap as it potentially
makes building lists easy (is there any need for the singly linked
list in D?) and I may modify some of my code. I've been allocating
arrays using "new array[size]" where I know that "size" will be the
max needed but that it may be too much (i.e. throwing away duplicates)
inserting into the array and then adjusting "length" to whatever I
used. In the case, where it's highly likely that the whole array will
fit in a page I might as well allocate an empty array and use "+=".
NB there's only one copy of the array.
You can .reserve the space that you need ahead of time. Then appending
will always deterministically go into the reserved block, and won't
reallocate. This should be relatively quick. It's not as quick as
pre-allocating the entire array and then writing the data directly --
you still need calls into the runtime for appending.
That's great news. When I tried to implement what I described above it
didn't go as well as planned (because I'd misunderstood how much gets
allocated) and I was thinking that what's needed is a way to tell the
compiler how much to allocate at the start. And now you tell me there
is a way.
This is one of the things I like about learning D. Almost every time I
say to myself "I wish there was an easier way to do this" it turns out
that there is :-). Some of them are easier to discover than others, though.
The appending feature of D arrays/slices is intended to be "good enough"
for most usages, not horrendously slow, but also not super-optimized for
specific purposes.
And yes, we still need linked lists, arrays are good for appending, but
not inserting :)
I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as I'm
willing to pay the cost of allocation for the convenience of array
notation. One advantage is that finding i is O(log(a.length)) instead
of O(a.length()). I also reasoned that the compiler can use memcopy()
(or whatever its name is) to do the reallocation and therefore it should
be fairly quick.
I also do a = a[0..i] ~ a[i + 1..$] to remove an item but am starting to
suspect this isn't as good an idea as for the insert. Maybe something like:
auto tmp = a[i + 1..$];
a.length = i;
a ~= tmp;
would be more efficient?
Peter
