opIndex, opSlice, length for joiner?

Maverick Chardet via Digitalmars-d digitalmars-d at puremagic.com
Wed Jan 20 14:13:28 PST 2016


Thank you all for your comments! I'm not making a PR for now 
because however I implement this, there will be complexity issues 
that need to be discussed...

On Wednesday, 20 January 2016 at 20:23:08 UTC, Jonathan M Davis 
wrote:
> On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
> wrote:
>> 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?
>
> The various range primitives all need to be O(1). We need to be 
> able to rely on the big-o complexity of the primitives used by 
> ranges, or the performance of various algorithms will tank when 
> used with ranges that don't stick to the expected big-o 
> complexities. So, if a range type cannot provide a primitive as 
> O(1), it should not provide that primitive. If that weren't the 
> case, then we'd have stuff like length, opIndex, and opSlice 
> for narrow strings, but we don't.
>
> std.container lists the algorithmic complexity for its various 
> operations for the same reason, and as I understand it, its 
> replacement that Andrei is working on is going to do the same.
>
> - Jonathan M Davis

That makes sense, so it won't happen unless we can make all of 
them run in O(1) time right? And this seems hopeless to me, even 
if all ranges are random access and implement opIndex, opSlice 
and length... Maybe with some precomputing in O(k) or O(n) (with 
k the number of ranges and n the total number of elements) with 
some fancy data structure?

But the whole thing would lose a lot of interest with a 
precomputing in O(n) time, appart from the syntaxic point of 
view...

Maverick Chardet


More information about the Digitalmars-d mailing list