www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Slicing upward

reply Brett <Brett gmail.com> writes:
I have an algorithm that is most efficiently implement by taking 
an array and slicing it upward, meaning removing the leading 
elements.

Because the algorithm is complex(deterministic but chaotic) and 
deals with multiple arrays it is difficult to efficiently use 
slicing.

Is there some easy way to take an array and slice it in a way 
that as the array grows any slices will "shift".

Essentially it is sort of reversing how normal slices are 
represented

[2,4,1,64]
slice last 2, [1,64]

append 3 to either one and both become

[2,4,1,64,3]
[1,64,3]


In my case I will never have any slices in the middle.

The easiest way, at the cost of size_t is to have an indexer that 
tells one how much to offset in to a standard array, basically 
skip the head.

In the first it is 0 and the second it is 2.

Since I already have the array though it is wasting space so I'm 
wondering if there is an easier way.


Reversing the direction of the arrays does notwork because this 
then require massive copying of the array to prepend values.

One can make an array type emulating this behavior but I'd rather 
have a simpler solution that is inline with slices, Else I'll 
just use the indexer method for simplicity.
Sep 14 2019
next sibling parent reply rikki cattermole <rikki cattermole.co.nz> writes:
On 14/09/2019 11:34 PM, Brett wrote:

 I have an algorithm that is most efficiently implement by taking an 
 array and slicing it upward, meaning removing the leading elements.
 
 Because the algorithm is complex(deterministic but chaotic) and deals 
 with multiple arrays it is difficult to efficiently use slicing.
 
 Is there some easy way to take an array and slice it in a way that as 
 the array grows any slices will "shift".
 
 Essentially it is sort of reversing how normal slices are represented
 
 [2,4,1,64]
 slice last 2, [1,64]


That part is easy.

```
import std.stdio;

void main() {
	int[] array = [2,4,1,64];
	array[$-2 .. $].writeln;
}
```
Sep 14 2019
parent reply Brett <Brett gmail.com> writes:
On Saturday, 14 September 2019 at 11:39:21 UTC, rikki cattermole 
wrote:

 On 14/09/2019 11:34 PM, Brett wrote:

 I have an algorithm that is most efficiently implement by 
 taking an array and slicing it upward, meaning removing the 
 leading elements.
 
 Because the algorithm is complex(deterministic but chaotic) 
 and deals with multiple arrays it is difficult to efficiently 
 use slicing.
 
 Is there some easy way to take an array and slice it in a way 
 that as the array grows any slices will "shift".
 
 Essentially it is sort of reversing how normal slices are 
 represented
 
 [2,4,1,64]
 slice last 2, [1,64]


 That part is easy.

 ```
 import std.stdio;

 void main() {
 	int[] array = [2,4,1,64];
 	array[$-2 .. $].writeln;
 }
 ```


I hope you are being factious.

What happens when one appends to array?
Sep 14 2019
parent rikki cattermole <rikki cattermole.co.nz> writes:
On 15/09/2019 5:06 AM, Brett wrote:

 On Saturday, 14 September 2019 at 11:39:21 UTC, rikki cattermole wrote:

 On 14/09/2019 11:34 PM, Brett wrote:

 I have an algorithm that is most efficiently implement by taking an 
 array and slicing it upward, meaning removing the leading elements.

 Because the algorithm is complex(deterministic but chaotic) and deals 
 with multiple arrays it is difficult to efficiently use slicing.

 Is there some easy way to take an array and slice it in a way that as 
 the array grows any slices will "shift".

 Essentially it is sort of reversing how normal slices are represented

 [2,4,1,64]
 slice last 2, [1,64]


 That part is easy.

 ```
 import std.stdio;

 void main() {
     int[] array = [2,4,1,64];
     array[$-2 .. $].writeln;
 }
 ```


 
 I hope you are being factious.
 
 What happens when one appends to array?


You will still need to store the length separately.

I only commented what the syntax is for that particular problem.

Paul Backus and Jonathan M Davis both deal in the part that is hard that 
you asked about.
Sep 15 2019
prev sibling next sibling parent Paul Backus <snarwin gmail.com> writes:
On Saturday, 14 September 2019 at 11:34:35 UTC, Brett wrote:

 I have an algorithm that is most efficiently implement by 
 taking an array and slicing it upward, meaning removing the 
 leading elements.

 Because the algorithm is complex(deterministic but chaotic) and 
 deals with multiple arrays it is difficult to efficiently use 
 slicing.

 Is there some easy way to take an array and slice it in a way 
 that as the array grows any slices will "shift".


No, there is no easy way to do this. You will have to implement 
your own "slice" type that keeps a reference to the original 
array it was taken from. For example:

struct UpwardSlice(T)
{
     private T[]* source;
     private size_t offset;

     this(ref T[] source, size_t offset = 0)
     {
         this.source = &source;
         this.offset = offset;
     }

     T opIndex(size_t i)
     {
         return (*source)[offset + i];
     }

     T[] opIndex()
     {
         return (*source)[offset .. $];
     }

      property size_t length()
     {
         return (*source).length - offset;
     }
}
Sep 14 2019
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Saturday, September 14, 2019 5:34:35 AM MDT Brett via Digitalmars-d-learn 
wrote:

 I have an algorithm that is most efficiently implement by taking
 an array and slicing it upward, meaning removing the leading
 elements.

 Because the algorithm is complex(deterministic but chaotic) and
 deals with multiple arrays it is difficult to efficiently use
 slicing.

 Is there some easy way to take an array and slice it in a way
 that as the array grows any slices will "shift".

 Essentially it is sort of reversing how normal slices are
 represented

 [2,4,1,64]
 slice last 2, [1,64]

 append 3 to either one and both become

 [2,4,1,64,3]
 [1,64,3]


 In my case I will never have any slices in the middle.

 The easiest way, at the cost of size_t is to have an indexer that
 tells one how much to offset in to a standard array, basically
 skip the head.

 In the first it is 0 and the second it is 2.

 Since I already have the array though it is wasting space so I'm
 wondering if there is an easier way.


 Reversing the direction of the arrays does notwork because this
 then require massive copying of the array to prepend values.

 One can make an array type emulating this behavior but I'd rather
 have a simpler solution that is inline with slices, Else I'll
 just use the indexer method for simplicity.


No, that fundamentally goes against how D's dynamic arrays work. Their
representation is essentially

struct DynamicArray(T)
{
    size_t length;
    T* ptr;
}

They don't even have a concept of ownership. They merely point to a slice of
memory, and that memory isn't necessarily GC-allocated. In order to append
to a dynamic array, the GC looks at it to see if it's a slice of a block of
memory that the GC has allocated for dynamic arrays. If it is such a block
of memory _and_ the metadata associated with that block of memory indicates
that no other dynamic arrays have ever been expanded into the memory beyond
that dynamic array, then the GC will put the element being appended into the
next spot after the end of the dynamic array, adjust the metadata, and then
increment the length member of the dynamic array that it was passed. If, on
the other hand, that block of memory was not allocated by the GC, was
allocated by the GC for something other than dynamic arrays, or if the
metadata indicates that a dynamic array has already grown into the space
beyond the end of that dynamic array, then it will have to allocate a new
block of memory, copy the elements to that new block of memory, and then
adjust the dynamic array that it was passed so that its ptr and length
members then refer to the new block of memory.

In the case where no allocation occurs, in order for any other dynamic
arrays which happen to refer to that same block of memory and which happen
to have their last element at the same spot as the dynamic array being
appended to then also include that new element, the GC would have to do a
sweep of all of the memory in the program to see if any other dynamic arrays
exist which are slices of that same block of memory and adjust them
(basically, it would have to do what it does when it does a collection when
determining whether a block of memory can be freed). The same would be the
case if the dynamic array had to be reallocated, only then the ptr member
would have to be adjusted as well. Not only would such an approach be
horribly inefficient, but it wouldn't work with all of the use cases where
you want the other dynamic arrays which are slices of that same block of
memory to continue to refer to the exact same piece of that block of memory
that they've been referring to.

The entire design of D's dynamic arrays is built around the idea that they
don't own or manage any memory at all. They are merely slices of it. What
you're looking for implies an ownership relationship which simply does not
exist with D's dynamic arrays.

With D's dynamic arrays, there is no concept of there being a main one which
others are slices of. If two dynamic arrays are slices of the same block of
memory (whether they refer to exactly the same part of it or not), then they
are equal in standing. Neither of them owns the memory. They just point to
it.

To do what you're looking to do with dynamic arrays, you'd need another
layer of indirection - e.g. T[]* - where you then had a separate data type
for your "slices" of that dynamic array. e.g.

struct Slice(T)
{
    T[]* arr;
    size_t startIndex;
    size_t length;
}

would allow you to have a "slice" which always referred to the same elements
of a dynamic array even if the dynamic array were reallocated, or

struct Slice(T)
{
    T[]* arr;
    size_t startIndex;
}

would allow you to have the "slice" to expand when the dynamic array it
refers to expands.

In either case, if you're using a dynamic array to store the data, you'd
have to make sure that it was somewhere where it was going to stay valid as
long as the "slices" were around (e.g. a static variable or on the heap),
since if it's on the stack, and it goes out of scope, then your "slices"
won't refer to valid memory anymore even if the memory that the dynamic
array had referred to was still valid. It's the same problem you'd get if
you had a dynamic array which was a slice of a static array which was on the
stack, and the static array went out of scope.

- Jonathan M Davis
Sep 14 2019