Ranges usages

[monarch_dodra]

On Thursday, 22 November 2012 at 01:14:23 UTC, bearophile wrote:
>
> [SNIP]
>
> Thank you,
> bye,
> bearophile

I'd argue that your first "compress1" isn't range correct either 
anyways, because "w ~ ch;" (which will allocate) is not part of 
the range interface.

Neither is "w = [ch];" (which will also allocate)

Given the allocations in the first example, I'd hardly consider 
the performance comparison fair.

How about this?

int[] compress3(immutable T[] original) {
     int[Ta] dictionary;
     foreach (i; 0 .. 256)
         dictionary[cast(Ta)[i]] = i;

     int[] result;
     size_t start, end;
     Ta w;
     foreach (i, ch; original) {
         auto wc = original[start .. end + 1];
         if (wc in dictionary) {
             w = wc;
             ++end;
         } else {
             w = original[start .. end];
             result ~= dictionary[w];
             dictionary[wc] = dictionary.length - 1;
             start = i;
             end = i + 1;
         }
     }

     return w.empty ? result : (result ~ dictionary[w]);
}

This is "range correct". Being range correct, it doesn't allocate 
either.

I would have preferred writing "wc = wc.ptr[0 .. wc.length + 
1]"... but that's not range correct...

I'd be thrilled if you (quickly) benched my compress3.

----
Also: I'd suggest you avoid code such as:
int[] result;
for (...)
     result ~= xxx ;

Unless you take the time to manually call assumeUnique, this will 
reallocate on *each*and*every* append. You are better off using 
an actual appender:
auto result = appender!int();
for (...)
     result.put(x);
return result.data;

My benching experiences have shown performance gains with 
appender as early as the 2nd insertion.
--------

Back to topic though:
My limited range experience has shown me that:
1. They are *incredibly* easy to chain and adapt.
2. RA ranges are (mostly) just as powerful as iterators or raw 
arrays.
3. If all you want to do is iterate forward, than any flavor of 
range will rock.

The "HUGE" flaw I see with ranges though, is in regards to 
bidirectional ranges, and their ability to "only shrink, never 
grow". In particular, it is not possible to "slice" an Bidir 
right through the middle. "iterate until you find x, and then 
return the slice *up-to* x". Iterators can do it just fine.

The (IMO) tell-tale symptom are all the algorithms that return a 
"take" for bidirectional ranges. "take" is nice and all, but in 
that case, I think it is subverting your range's type.

In particular, own of the "great power" of a bidirectional range, 
is to define a sequence by "all elements between a start and end 
point". What's cool about this definition is that it means that 
if you insert new element between the bounds, they will be taken 
into account by the range.

"Take" subverts that in that the sequence becomes a "start + 
index", so inserting new items in the underlying _container_ will 
just bump the last items out of your rake range.

--------
Well, that's my rant anyways: Range are an incredibly powerful 
abstract notion, but when you want to get down and dirty with 
them, they tend to create a bit of friction compared to some 
lower level abstractions...

But overall: Worth it.