Huffman coding comparison

[Philippe Sigaud]

On Sun, May 30, 2010 at 19:01, Simen kjaeraas <simen.kjaras at gmail.com>wrote:

> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>> This reminded me that Phobos lacks a combinatorial range, taking two or
>>> more (forward) ranges and giving all combinations thereof:
>>>
>>> combine([0,1],[2,3])
>>> =>
>>> (0,2), (0,3), (1,2), (1,3)
>>>
>>> Work has commenced on implementing just that.
>>>
>>
>> Yah, that would be useful. If Philippe agrees to adapt his work, maybe
>> that would be the fastest route. And don't forget - the gates of Phobos are
>> open.
>>
>
> Too late for that, as I've already written this. :p
>

Hey, cool, lots of static foreach. Man, it's like I'm reading my own code.
I'm happy to see convergent evolution: this must be the D way to do this.



> Current problems: back and popBack not implemented. I'm not sure they
> even should be. Doing so would be a tremendous pain the region below the
> spine.
>
>
Ow.
I *guess* it's doable, but I for sure don't want to do it.


> May very well be there are other problems, I don't know. If anyone finds
> any, please let me know.


Well, I like the way you dealt with popFront.  You length is more costly
than mine, but I cheated: I count the numbers of popFronts and substract
them from the original length.

Your empty use .length in the foreach loop. You should use .empty instead, I
think. And with an infinite range in the mix, the resulting product is
infinte also, so you can define your combine to be infinite.

Then I can give you something to munch over :-)

When one range is infinite, the resulting combination is infinite. What's
sad is that you'll never 'traverse' the infinite range:
auto c = combine([0,1,2], cycle([2,3,4]));
->
(0,2),(0,3),(0,4),(0,2),(0,3), ...

You never reach the (1,x) (2,x) parts, as it should be seeing how we both
defined combinations: iterating on the ranges as if they were digits in a
number.

But there is another way to iterate: diagonally, by cutting successive
diagonal slices:

c is:
(0,2),(0,3),(0,4),(0,2),...
(1,2),(1,3),(1,4),(1,2),...
(2,2),(2,3),(2,4),(2,2),...
->

(0,2),(0,3)(1,2),(0,4),(1,3),(2,2) ...

It's even better if all ranges are infinite.
I never coded this, but it seems doable for two ranges. Lot thougher for any
number of ranges... Pretty obscure, maybe?

btw, I think we should divert this discussion in another thread if you wish
to continue: this is bearophile's Huffman thread, after all.

  Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100530/070ac575/attachment.html>