[phobos] Slicer
David Simcha
dsimcha at gmail.com
Fri Aug 13 16:26:57 PDT 2010
Ok, I've mostly been convinced. I browsed through std.range and
couldn't find any case of ranges that were finite and random access, but
where that slicing would be difficult to implement provided that, in the
case of higher order ranges, the base range supports slicing.
The one somewhat difficult case is when you take a finite number of
elements from an infinite range. I assume we don't want to make
infinite ranges support slicing, as this would be kind of silly. For
example, other than an infinite random access range specialization of
Take that simply maintains a lowerLim variable in addition to an
upperLim variable (which is not unreasonable), I don't see any way to
support slicing like:
take(cycle([1,2,3]), 100)[31..41];
In practice it seems like there are three basic types of random access
ranges (as it's difficult to imagine any other cases where you'd have
O(1) access to every element and dense 0..N indexing):
1. Arrays and array-like objects that are implemented as a contiguous
block of memory.
2. Iota, Sequence, Repeat/Replicate, etc., which are based on
evaluation of mathematical functions.
3. Higher order ranges using (1) or (2) as the base range.
In all of these cases supporting slicing is completely feasible. If
we're sure we agree, I'll fold this into the bug fixing/cleanup I've
resumed in std.range.
On 8/13/2010 5:47 PM, Andrei Alexandrescu wrote:
> I'm just saying it's reasonable to require ranges to define slicing. I
> understand that that may feel some creators of random-access ranges
> aggravated, but it's not like we define five random-access ranges a day.
>
> Let's require slicing (I meant to do that for a long time) and move on
> to more interesting problems. I just don't feel a slicer wrapper
> justifies itself.
>
>
> Andrei
>
> David Simcha wrote:
>> But this would lead to boilerplate and inefficiency in cases where
>> slicing isn't needed. Ranges that don't have a better way of dealing
>> with slicing would have to have lowerLim and upperLim variables and
>> add lowerLim every time the range was indexed. While I think the
>> overhead of this is reasonable if the alternative is an algorithm
>> simply not working, I don't think it's reasonable to pay for it (both
>> in execution efficiency and boilerplate code) when it's not going to
>> be used.
>>
>> On Fri, Aug 13, 2010 at 2:04 PM, Andrei Alexandrescu
>> <andrei at erdani.com <mailto:andrei at erdani.com>> wrote:
>>
>> I'd favor simplicity by just requiring random-access ranges to
>> define slicing.
>>
>> Andrei
>>
>> David Simcha wrote:
>>
>> I would agree if we were talking about big-O efficiency, or even
>> a large constant overhead, but IMHO avoiding Slicer is a
>> micro-optimization, not a macro-optimization. Therefore, by
>> default it should "just work" even if it's slightly inefficient
>> and intervention should be required only if the programmer
>> decides it needs to be optimized.
>>
>> On Fri, Aug 13, 2010 at 1:02 PM, Jonathan M Davis
>> <jmdavisprog at gmail.com <mailto:jmdavisprog at gmail.com>
>> <mailto:jmdavisprog at gmail.com <mailto:jmdavisprog at gmail.com>>>
>> wrote:
>>
>> On Thursday, August 12, 2010 20:24:03 David Simcha wrote:
>> > A whole bunch of stuff in Phobos (including
>> std.range.Radial and
>> the FFT
>> > algorithm I just checked in) requires that ranges provided
>> to it have
>> > slicing. This limitation is a PITA. Should we add a Slicer
>> meta-range
>> > that takes a finite random-access range and bolts slicing
>> on in the
>> > obvious but relatively inefficient way if it's not already
>> supported and
>> > simply returns the range if it already supports slicing? This
>> would be
>> > used under the hood when slicing is required. For example:
>> >
>> > struct Slicer(R) if(isRandomAccessRange!R && !hasSlicing!R) {
>> > R range;
>> > size_t lowerLim, upperLim;
>> >
>> > this(R r) {
>> > this.range = range;
>> > this.upperLim = range.length;
>> > }
>> >
>> > // Range primitives: front, popFront, etc.
>> >
>> > typeof(this) opSlice(size_t lower, size_t upper) {
>> > // Error checking
>> > auto ret = this;
>> > ret.upperLim -= this.length - upper;
>> > ret.lowerLim += lower;
>> > return ret;
>> > }
>> > }
>> >
>> > auto slicer(R)(R range) {
>> > static if(hasSlicing!R) {
>> > return range;
>> > } else {
>> > return Slicer!(R)(range);
>> > }
>> > }
>> > _______________________________________________
>> > phobos mailing list
>> > phobos at puremagic.com <mailto:phobos at puremagic.com>
>> <mailto:phobos at puremagic.com <mailto:phobos at puremagic.com>>
>>
>> > http://lists.puremagic.com/mailman/listinfo/phobos
>>
>> I'm not sure I like the idea that this would be done without
>> programmer
>> intervention. If it's inefficient, it'll lead to programmers
>> using
>> range types
>> with algorithms that really aren't supposed to take those
>> range
>> types and
>> without them realizing the fact that it's inefficient.
>> Having a
>> means to allow the
>> programmer to wrap a range to allow it to be used by an
>> algorithm
>> which it
>> wouldn't normally work with may be a good idea, but each
>> algorithm
>> takes certain
>> types of ranges for a reason, and I'd hate to see much
>> impact to
>> efficiency
>> because of internal range wrangling that the programmer
>> using the
>> function isn't
>> even aware of.
>>
>> - Jonathan M Davis
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com <mailto:phobos at puremagic.com>
>> <mailto:phobos at puremagic.com <mailto:phobos at puremagic.com>>
>>
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com <mailto:phobos at puremagic.com>
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com <mailto:phobos at puremagic.com>
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
More information about the phobos
mailing list