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.

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;
}
```

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?

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;
    }
}

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

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.