opIndex, opSlice, length for joiner?

Ilya via Digitalmars-d digitalmars-d at puremagic.com
Wed Jan 20 11:15:59 PST 2016


On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
wrote:
> Hi everyone,
>
> After reading the thread "Distributed Memory implementation": 
> http://forum.dlang.org/post/oqcfifzolmolcvyupsef@forum.dlang.org
>
> And more precisely the suggestion of Dragos Carp on page 2: 
> http://forum.dlang.org/post/txgabyyoutitketlpvgm@forum.dlang.org
>
> I looked at the joiner source code 
> (std.algorithm.iteration.joiner) and I have several ideas to 
> make it have the opIndex, opSlice and length methods under 
> certain conditions.
>
> First question: what do you think of making this possible if 
> all the considered ranges have opIndex, opSlice and length? I 
> think that all the ranges types don't have to all implement the 
> three methods in all cases (for instance length would actually 
> only require ElementType!RoR and Separator to implement length) 
> but we can discuss all that later...
>
> The most important issue that comes to my mind is that the 
> operations would not take constant time... A trivial 
> implementation would be in O(k) where k is the number of joined 
> ranges, and with some precomputation in O(k) time and space we 
> can make length O(1) and opIndex and opSlice O(log k)... Would 
> that be a problem?
>
> Thank you in advance for your remarks!

O(K) looks OK for joiner. However this will cause additional 
performance problem because a couple of Phobos algorithm assumes 
that opIndex is fast as front+popFront. Perhaps a special UDA can 
be introduced, something like @optimized("forward range").

See also `byElement` for multidimensional random access slices. 
It has opIndex and slicing.
https://github.com/D-Programming-Language/phobos/blob/v2.070.0-b2/std/experimental/ndslice/selection.d#L893

Ilya


More information about the Digitalmars-d mailing list