www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Successively prepending to slices.

reply "dnspies" <dspies ualberta.ca> writes:
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?
Apr 09 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
dnspies:


 efficiently, or is it better to avoid this sort of thing?


D arrays are dynamic on the right. So appending on their left is 
not efficient (also here you are not prepending, you are 
concatenating. Array concatenation creates a new array). In some 
cases you can append on the right many items and then use 
std.algorithm.reverse (don't forget the () if you use UFCS) to 
reverse them. In case of doubt write little benchmarks.

Bye,
bearophile
Apr 09 2014
parent reply "dnspies" <dspies ualberta.ca> writes:
On Wednesday, 9 April 2014 at 23:43:27 UTC, bearophile wrote:

 dnspies:


 efficiently, or is it better to avoid this sort of thing?


 D arrays are dynamic on the right. So appending on their left 
 is not efficient (also here you are not prepending, you are 
 concatenating. Array concatenation creates a new array). In 
 some cases you can append on the right many items and then use 
 std.algorithm.reverse (don't forget the () if you use UFCS) to 
 reverse them. In case of doubt write little benchmarks.

 Bye,
 bearophile


Does concatenation always create a new array?  What if the type 
of the original is immutable (or even const)?  In that case, 
wouldn't it be worthwhile to check first if rhs can be copied to 
the right of lhs?
Apr 09 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
dnspies:


 Does concatenation always create a new array?


Concatenation allocated a new array (unless some compiler is able 
to optimize away something in some cases, but I think this is not 
yet happening).

Bye,
bearophile
Apr 09 2014
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 9 April 2014 at 23:53:04 UTC, dnspies wrote:

 Does concatenation always create a new array?  What if the type 
 of the original is immutable (or even const)?  In that case, 
 wouldn't it be worthwhile to check first if rhs can be copied 
 to the right of lhs?


Yes, it *always* creates a new array. First:
The resulting array is guaranteed new. Consider:
1. If "rhs" was copied to the right of "lhs", then "lhs" and 
"result" would be aliasing data:
a = [1];
b = [1];
c = a ~ b;
c[0] = 2;
assert(a[0] == 1); //Could fail! A got clobbered!

2. If "lhs" has some capacity, then it is guaranteed its next 
concatenation will be non allocating.
a = [1];
a.reserve(2);
p = a.ptr;
b =a ~ 2; //Uses a's capacity;
a ~= 2; //relocates.
assert(a.ptr == p); //Fails!

If you *really* wanted to "make concatenation maybe append", you 
can do it this way:
a = [1, 2, 3];
b = [...];
c = a; c ~= b; //c has the same contents as "a ~ b", but may 
actually contain a part of "a".
Apr 09 2014
parent "dnspies" <dspies ualberta.ca> writes:
On Thursday, 10 April 2014 at 05:54:52 UTC, monarch_dodra wrote:

 On Wednesday, 9 April 2014 at 23:53:04 UTC, dnspies wrote:

 Does concatenation always create a new array?  What if the 
 type of the original is immutable (or even const)?  In that 
 case, wouldn't it be worthwhile to check first if rhs can be 
 copied to the right of lhs?


 Yes, it *always* creates a new array. First:
 The resulting array is guaranteed new. Consider:
 1. If "rhs" was copied to the right of "lhs", then "lhs" and 
 "result" would be aliasing data:
 a = [1];
 b = [1];
 c = a ~ b;
 c[0] = 2;
 assert(a[0] == 1); //Could fail! A got clobbered!

 2. If "lhs" has some capacity, then it is guaranteed its next 
 concatenation will be non allocating.
 a = [1];
 a.reserve(2);
 p = a.ptr;
 b =a ~ 2; //Uses a's capacity;
 a ~= 2; //relocates.
 assert(a.ptr == p); //Fails!

 If you *really* wanted to "make concatenation maybe append", 
 you can do it this way:
 a = [1, 2, 3];
 b = [...];
 c = a; c ~= b; //c has the same contents as "a ~ b", but may 
 actually contain a part of "a".


The aliasing thing isn't a problem if the data-type is const or 
immutable, because you can't change it any way. (Your "A got 
clobbered" example doesn't apply)
Apr 10 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Apr 09 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
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?


Definitely better to avoid. What's the use-case? There is almost 
certainly a better way of achieving what you want.
Apr 10 2014
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 09 Apr 2014 19:18:25 -0400, dnspies <dspies ualberta.ca> 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?


I would recommend appending, and then using std.range.retro to access, or  
reversing the array afterwards.

Another possibility, if you know the final array size, is to reserve and  
then fill the array:

int[] x;
x.length = 1000;
for(int i = 0; i < 1000; ++i)
{
    x[$-1-i] = i;
    // or (I think this works)
    retro(x)[i] = i;
}

I don't know the use case (how do you use it after creation?)

Note, I create a deque class in dcollections which maintains 2 arrays, one  
for prepending (and is in reverse order), and one for appending. The class  
handles the indexing so that it looks like a standard array. But  
prepending is also amortized O(1)

Also note, [i] ~ x will first allocate on the heap an array with a single  
element value of i, then allocate ANOTHER array on the heap which can  
contain all the elements in x + 1, and copy i and x to it.

The code is extremely inefficient, and should be avoided.

-Steve
Apr 10 2014
parent reply "JR" <zorael gmail.com> writes:
It depends on your use-case, I think. How often will you be 
prepending? Will you be appending as well?

On Thursday, 10 April 2014 at 16:10:04 UTC, Steven Schveighoffer 
wrote:

 Note, I create a deque class in dcollections which maintains 2 
 arrays, one for prepending (and is in reverse order), and one 
 for appending. The class handles the indexing so that it looks 
 like a standard array. But prepending is also amortized O(1)


I like this one. If you're only ever prepending you would only 
need the reverse one, appending values in .retro to it as you 
wish, and then .retro.dup when you want a copy.

In my NewlineBufferThingy struct, I sometimes need to move a 
slice at an arbitrary point of an array to the very beginning of 
it, like a poor man's circular buffer. I ended up using 
std.algorithm.copy for that, but in your case -- once more, 
depending on your use-case -- that could end up in a *lot* of 
copying.
Apr 10 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 10 April 2014 at 20:03:46 UTC, JR wrote:

 In my NewlineBufferThingy struct, I sometimes need to move a 
 slice at an arbitrary point of an array to the very beginning 
 of it, like a poor man's circular buffer.


Just in case somebody is wondering, phobos has std.range.cycle 
for circular buffers.


 I ended up using std.algorithm.copy for that, but in your case 
 -- once more, depending on your use-case -- that could end up 
 in a *lot* of copying.


You may want to consider looking at std.algorithm.bringToFront. 
I've never used it before, but it claims:

The bringToFront function has considerable flexibility and 
usefulness. It can rotate elements in one buffer left or right, 
swap buffers of equal length, and even move elements across 
disjoint buffers of different types and different lengths.

I don't know how efficient or certifiably correct it actually is.
Apr 10 2014