www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - fast way to insert element at index 0

reply "Assembly" <jckj33 gmail.com> writes:
What's a fast way to insert an element at index 0 of array? now 
that the code is working I want to clean this:

void push(T val)
	{
		T[] t = new T[buffer.length + 1];
		t[0] = val;
		t[1 .. $] = buffer;
		buffer = t;
	}

I did this because I didn't find any suble built-in data 
structure that let me insert an item into a specific index at 
first search. Slist does have insertFron(), exactly what I'm 
looking for it's a linked list.
Jun 22 2015
next sibling parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:

 What's a fast way to insert an element at index 0 of array? now 
 that the code is working I want to clean this:

 void push(T val)
 	{
 		T[] t = new T[buffer.length + 1];
 		t[0] = val;
 		t[1 .. $] = buffer;
 		buffer = t;
 	}

 I did this because I didn't find any suble built-in data 
 structure that let me insert an item into a specific index at 
 first search. Slist does have insertFron(), exactly what I'm 
 looking for it's a linked list.


I think you want to do something like this:

void main() {

     import std.algorithm;

     auto a = [1, 2, 3];

     int val = 5;

     a = val ~ a; // vector.pushFront();

     assert(equal(a[], [5, 1, 2, 3]));
}
Jun 22 2015
prev sibling next sibling parent reply "jkpl" <jkpl nowhere.de> writes:
On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:

 What's a fast way to insert an element at index 0 of array? now 
 that the code is working I want to clean this:

 void push(T val)
 	{
 		T[] t = new T[buffer.length + 1];
 		t[0] = val;
 		t[1 .. $] = buffer;
 		buffer = t;
 	}

 I did this because I didn't find any suble built-in data 
 structure that let me insert an item into a specific index at 
 first search. Slist does have insertFron(), exactly what I'm 
 looking for it's a linked list.


* Option 1/

if most of the time you have to insert at the beginning, then 
start reading from the end and append to the end, so that the 
existing block has not to be moved. You just have to add val at 
the end.

* Option 2/

better way to move the whole block (this can be done with memmove 
too).

---
void push(T val)
{
     buffer.length += 1;
     buffer[1..$] = buffer[0..$-1];
     // or memmove(buffer.ptr + T.sizeof, buffer.ptr, 
(buffer.length - 1) * T.sizeof);
     buffer[0] = val;
}
---

* Option 3/

linked lists are better to insert/move.
Jun 22 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/23/15 1:51 AM, jkpl wrote:

 On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:

 What's a fast way to insert an element at index 0 of array? now that
 the code is working I want to clean this:

 void push(T val)
     {
         T[] t = new T[buffer.length + 1];
         t[0] = val;
         t[1 .. $] = buffer;
         buffer = t;
     }

 I did this because I didn't find any suble built-in data structure
 that let me insert an item into a specific index at first search.
 Slist does have insertFron(), exactly what I'm looking for it's a
 linked list.


 * Option 1/

 if most of the time you have to insert at the beginning, then start
 reading from the end and append to the end, so that the existing block
 has not to be moved. You just have to add val at the end.

 * Option 2/

 better way to move the whole block (this can be done with memmove too).

 ---
 void push(T val)
 {
      buffer.length += 1;
      buffer[1..$] = buffer[0..$-1];


This will fail.

http://dlang.org/arrays.html#overlapping-copying

I will note, dcollections had a deque, which allowed insertion at the 
front in O(1) (amortized) time. It basically worked by having 2 arrays 
front to front.

-Steve
Jun 23 2015
parent reply "Baz" <bb.temp gmx.com> writes:
On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer 
wrote:

 On 6/23/15 1:51 AM, jkpl wrote:

 On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:

 [...]


 * Option 1/

 if most of the time you have to insert at the beginning, then 
 start
 reading from the end and append to the end, so that the 
 existing block
 has not to be moved. You just have to add val at the end.

 * Option 2/

 better way to move the whole block (this can be done with 
 memmove too).

 ---
 void push(T val)
 {
      buffer.length += 1;
      buffer[1..$] = buffer[0..$-1];


 This will fail.

 http://dlang.org/arrays.html#overlapping-copying

 I will note, dcollections had a deque, which allowed insertion 
 at the front in O(1) (amortized) time. It basically worked by 
 having 2 arrays front to front.

 -Steve


according to the C library, memmove handle overlapps, you 
mismatch with memcpy which does not.
Jun 23 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/23/15 8:12 AM, Baz wrote:

 On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer wrote:

 On 6/23/15 1:51 AM, jkpl wrote:

 On Tuesday, 23 June 2015 at 05:16:23 UTC, Assembly wrote:

 [...]


 * Option 1/

 if most of the time you have to insert at the beginning, then start
 reading from the end and append to the end, so that the existing block
 has not to be moved. You just have to add val at the end.

 * Option 2/

 better way to move the whole block (this can be done with memmove too).

 ---
 void push(T val)
 {
      buffer.length += 1;
      buffer[1..$] = buffer[0..$-1];


 This will fail.

 http://dlang.org/arrays.html#overlapping-copying

 I will note, dcollections had a deque, which allowed insertion at the
 front in O(1) (amortized) time. It basically worked by having 2 arrays
 front to front.


 according to the C library, memmove handle overlapps, you mismatch with
 memcpy which does not.


The above is not memmove, it's slice assignment, which is specifically 
illegal for overlaps:

$ cat testsliceassign.d
void buffer[100];

void main()
{
     buffer[1..$] = buffer[0..$-1];
}

$ dmd testsliceassign.d
$ ./testsliceassign
object.Error (0): Overlapping arrays in copy: 98 byte(s) overlap of 99

-Steve
Jun 23 2015
parent reply "Baz" <bb.temp gmx.com> writes:
On Tuesday, 23 June 2015 at 13:29:41 UTC, Steven Schveighoffer 
wrote:

 On 6/23/15 8:12 AM, Baz wrote:

 On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer 
 wrote:

[...]


 according to the C library, memmove handle overlapps, you 
 mismatch with
 memcpy which does not.


 The above is not memmove, it's slice assignment, which is 
 specifically illegal for overlaps:

 $ cat testsliceassign.d
 void buffer[100];

 void main()
 {
     buffer[1..$] = buffer[0..$-1];
 }

 $ dmd testsliceassign.d
 $ ./testsliceassign
 object.Error (0): Overlapping arrays in copy: 98 byte(s) 
 overlap of 99

 -Steve


ok. i was, wrongly, suposing that this operation uses memmove 
under the hood.
btw you forgot to grow the array size, if i dare.
Jun 23 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/23/15 10:20 AM, Baz wrote:

 On Tuesday, 23 June 2015 at 13:29:41 UTC, Steven Schveighoffer wrote:

 On 6/23/15 8:12 AM, Baz wrote:

 On Tuesday, 23 June 2015 at 11:22:31 UTC, Steven Schveighoffer wrote:

 [...]


 according to the C library, memmove handle overlapps, you mismatch with
 memcpy which does not.


 The above is not memmove, it's slice assignment, which is specifically
 illegal for overlaps:

 $ cat testsliceassign.d
 void buffer[100];

 void main()
 {
     buffer[1..$] = buffer[0..$-1];
 }

 $ dmd testsliceassign.d
 $ ./testsliceassign
 object.Error (0): Overlapping arrays in copy: 98 byte(s) overlap of 99


 ok. i was, wrongly, suposing that this operation uses memmove under the
 hood.
 btw you forgot to grow the array size, if i dare.


Heh, it was just to demonstrate the error :) The code does a whole lot 
of nothing, actually.

-Steve
Jun 23 2015
prev sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 06/22/2015 10:16 PM, Assembly wrote:> What's a fast way to insert an 
element at index 0 of array? now that the

 code is working I want to clean this:

 void push(T val)
      {
          T[] t = new T[buffer.length + 1];
          t[0] = val;
          t[1 .. $] = buffer;
          buffer = t;
      }

 I did this because I didn't find any suble built-in data structure that
 let me insert an item into a specific index at first search. Slist does
 have insertFron(), exactly what I'm looking for it's a linked list.


If the array is huge, you may find it to be faster to not move any data 
at all but treat both that single element and the array as one larger 
range. chain() does that:

import std.algorithm;
import std.range;

void main()
{
     auto arr = [ 0, 1, 2 ];
     auto singleElement = 42.only;
     auto both = chain(singleElement, arr);

     assert(both.equal([ 42, 0, 1, 2 ]));

     // Supports random access as well:
     assert(both[0] == 42);
     // ...
     assert(both[$-1] == 2);
}

As you can see, although what chain() returns is not an array, it is a 
RandomAccessRange; so, indexing works just fine. However, do test its 
performance before using it as some of its operations necessarily do 
more work than a real array (or slice).

Ali
Jun 22 2015