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