View mode: basic / threaded / horizontal-split · Log in · Help
November 13, 2012
Regarding ranges
The type system knows the length of a fixed size array at 
compile-time, but to call a function that accepts ranges you have 
to slice it. So you are throwing away some compile-time 
information. This is rather bad, because such information is 
useful for the compiler to produce more optimized code 
(especially when the array is small) or to detect some out of 
array bound errors at compile time instead of at run time. Who 
knows what Alexander Stepanov thinks about this :-)

The usual work around to avoid this problem in D is to add 
overloads that accept fixed sized arrays as inputs.

Regarding ranges, as Andrei says the main restriction of a range 
is that it can always shrink, never grow.

In the following program there are two versions of the compress 
function, that implement the same bare-bones version of the LZW 
(http://en.wikipedia.org/wiki/Lempel-Ziv-Welch ) compression 
algorithm.

compress1 is the simpler version, while compress2 avoids useless 
heap-allocations managing a Slice that is able to grow (In some 
of my benchmarks compress2 is about twice faster than compress1). 
Do you know if it's possible to write similar code nicely & 
efficiently with ranges?


import std.stdio, std.array;

alias T = ubyte;
alias Ta = immutable(T)[];

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

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

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

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

    struct Slice {
        size_t start, end;
        @property opSlice() {
            return original[start .. end];
        }
        alias this = opSlice;
    }

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

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

void main() {
    auto txt = cast(Ta)"TOBEORNOTTOBEORTOBEORNOT";
    writeln(compress1(txt));
    writeln(compress2(txt));
}


Thank you,
bye,
bearophile
November 13, 2012
Re: Regarding ranges
On Tuesday, 13 November 2012 at 04:50:54 UTC, bearophile wrote:
> Do you know if it's possible to write similar code nicely & 
> efficiently with ranges?

Bearophile, do you know of a good reference to learn about ranges 
in D?  Due to the language name, Googling for specific topics in 
D is a bit difficult and though I've heard the topic come up, I 
never found a way to really understand it.

 - Vijay
November 13, 2012
Re: Regarding ranges
On Tuesday, 13 November 2012 at 16:18:43 UTC, Vijay Nayar wrote:
> On Tuesday, 13 November 2012 at 04:50:54 UTC, bearophile wrote:
>> Do you know if it's possible to write similar code nicely & 
>> efficiently with ranges?
>
> Bearophile, do you know of a good reference to learn about 
> ranges in D?  Due to the language name, Googling for specific 
> topics in D is a bit difficult and though I've heard the topic 
> come up, I never found a way to really understand it.
>
>  - Vijay

http://ddili.org/ders/d.en/ranges.html
November 13, 2012
Re: Regarding ranges
This is very well written.  Thanks for the link!

 - Vijay

On Tuesday, 13 November 2012 at 16:29:41 UTC, Namespace wrote:
> On Tuesday, 13 November 2012 at 16:18:43 UTC, Vijay Nayar wrote:
>> On Tuesday, 13 November 2012 at 04:50:54 UTC, bearophile wrote:
>>> Do you know if it's possible to write similar code nicely & 
>>> efficiently with ranges?
>>
>> Bearophile, do you know of a good reference to learn about 
>> ranges in D?  Due to the language name, Googling for specific 
>> topics in D is a bit difficult and though I've heard the topic 
>> come up, I never found a way to really understand it.
>>
>> - Vijay
>
> http://ddili.org/ders/d.en/ranges.html
Top | Discussion index | About this forum | D home