• bearophile (75/75) Nov 12 2012 The type system knows the length of a fixed size array at
• Vijay Nayar (6/8) Nov 13 2012 Bearophile, do you know of a good reference to learn about ranges
• Namespace (2/10) Nov 13 2012 http://ddili.org/ders/d.en/ranges.html
• Vijay Nayar (3/15) Nov 13 2012 This is very well written. Thanks for the link!

"bearophile" <bearophileHUGS lycos.com> writes:

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

"Vijay Nayar" <madric gmail.com> writes:

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

"Namespace" <rswhite4 googlemail.com> writes:

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

"Vijay Nayar" <madric gmail.com> writes:

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