Tomek Sowin'ski wrote:
Andrei Alexandrescu wrote:
I'm trying to find justifications for keeping assumeSorted and friends
within Phobos. Background: assumeSorted(r) where r is some range returns
a value that wraps r and clarifies to the caller that it can assume r
has been sorted.
The obvious use case in Phobos is that find(haystack, needle) can
proceed faster if haystack == assumeSorted(something).
The nicest way to go about this is to make the type returned by
assumeSorted a kind of "range with benefits". That is, it would
implement all range primitives, plus a few more primitives that are
advantageous for sorted ranges. Question is: what are those? What kind
of cool primitives could a sorted range define?
Here are a few I can think of:
find -> uses binary search if random-access, or at least early stopping
otherwise.
minElement -> r.front
maxElement -> r.back
topN -> essentially does nothing
median -> r[r.length / 2]
Such functions could have free counterparts in std.algorithm. The free
functions check whether the range already implements the fast functions
and uses them transparently if present. So then we have e.g. find()
which works in linear time for most ranges, but logarithmic time on
random-access sorted ranges.
Sort of trivial, but I'd like to see the predicate with which it's sorted.
Thanks for your feedback. Yah, that's a given.
Also, I can't stop thinking that it's stand-alone find()'s job utilize
whatever features the range has (be it random access, sortedness, or
anything else) to execute fast, not the passed in range's.
Good point, though that reintroduces the question of comparing find's
predicate with SortedRange's predicate.
Checking for a member find() sounds good but doesn't have anything specific
to do with the range being sorted. Any range could define its find() to
special-case on its structure.
And that's not bad I think. If the range feels it has defined enough
structure to implement fast find, maybe find should defer to it. I'm
unclear about the best strategy here.
BTW, would it be a big deal if sort() returned assumeSorted!Range? Many uses
are a re-sort + binary search combo.
Yah, that would be great.
Andrei
