Variable chunk sizes operations
Paul Backus
snarwin at gmail.com
Sun Aug 30 00:01:16 UTC 2020
On Saturday, 29 August 2020 at 23:33:49 UTC, Mihaela Chirea wrote:
> I started working on this issue and I reached a point where
> some more opinions would be needed:
>
> https://github.com/dlang/phobos/pull/7600
>
> Since the range is split into uneven parts, some operations can
> only be done in O(n).
I think care should be taken to distinguish which `n` we're
talking about when we use terms like O(n) in this context.
For example, let's say N = the length of the source range, and S
= the length of the chunk-sizes range. Your length method is
O(S), but not O(N)--in fact, it runs in constant time w.r.t. the
length of the source range.
I'm not sure what Phobos policy is regarding time complexity for
algorithms that take multiple ranges (does it have to be O(1)
w.r.t. *all* arguments?), but given that S is likely to be
smaller than N, there's a case to be made that the linear-time
algorithm is reasonable here.
(A similar case is binary search of a range that contains strings
runs in logarithmic time w.r.t. the length of the range, but
linear time w.r.t. the length of the target string, because
checking two strings for equality is a linear-time operation.)
More information about the Digitalmars-d
mailing list