On Thursday, 15 May 2014 at 09:00:13 UTC, bearophile wrote:
This task asks for an basic implementation of the the
Lempel-Ziv-Welch (LZW) compression/decompression algorithm. I
am keeping two D versions, the first one is minimal, and the
second is a little more optimized:
http://rosettacode.org/wiki/LZW_compression#More_Refined_Version
There are of course ways to implement a really efficient ZLW
compressor in D, and such implementation could be added as
third D entry if it manages to be not too much long, but for
the first two versions keeping the code very short is more
important.
Despite the compressor in the second D entry is still not
efficient at all, I have tried to make it not terrible
regarding its efficiency, so I have defined a new kind of slice
that can be extended, unlike the D slices, to avoid the string
appends visible in the first D entry:
struct Slice {
size_t start, end;
@property opSlice() const pure nothrow @safe @nogc {
return original[start .. end];
}
alias opSlice this;
}
Slice w;
Tcomp[] result;
foreach (immutable i; 0 .. original.length) {
auto wc = Slice(w.start, w.end + 1); // Extend slice.
if (wc in dict) {
w = wc;
} else {
result ~= dict[w];
assert(dict.length < Tcomp.max); // Overflow guard.
dict[wc] = cast(Tcomp)dict.length;
w = Slice(i, i + 1);
}
}
Is this showing a limit (problem) of D slices, or is this
design better written in other ways?
Bye,
bearophile
I don't think it shows a limit of "slices" in and out of itself,
but rather the whole "range" concept, that conveniently
encapsulates a start/end iteration scheme.
The problem though is that, unlike iterators, these can only
shrink, and never grow. Furthermore, it is usally hard to "split"
a range into two parts, given a center iterator (especially for
bidirectional-only ranges: EG: linked list).
I think ranges/slices still provide more functionality and are
worth it, but they do sacrifice *some* power: Growth and
splitting.
To be honest, what you are doing is essentially working with
iterator pairs, disguised as indexes inside a "Slice" struct. Not
that there's anything wrong with that, but that's my impression
when looking at the code.
Related:
http://forum.dlang.org/thread/[email protected]#post-umxlhsfqmfjwydemfdeb:40forum.dlang.org
http://forum.dlang.org/thread/[email protected]#post-mailman.2149.1353648522.5162.digitalmars-d:40puremagic.com
