Huffman coding comparison

[Andrei Alexandrescu]

On 05/28/2010 05:01 PM, bearophile wrote:
[snip]
> Some notes (later I can send them to Andrei):

Thanks for your notes. I removed those for which I have no notable answer.

> The "std.typecons" module, that contains Tuple and tuple can be named
> something simpler to remember as "std.tuples".

Phobos' general approach to naming modules is of coarse granularity. I 
wanted to massage in std.typecons everything that constructs new, 
generally useful types.

> I will keep missing array comprehensions in D. In the meantime other
> languages have got some forms of them (but Python ones use the best
> syntax still).

Looks like we're having two proposals.

> In translating the program I have not found significant problems. The
> only bug I have found was caused by the different ordering of the
> Python/Phobos2 heaps, so I have had to use "b<a" in D2. This is not a
> bug, but I have to keep it in mind in future usages of heaps across
> the two languages. I don't know why the two languages have chosen
> different orderings here, if someone of you knows I'd like to know
> it.

a < b is sort of the default comparison operator in D, so it would have 
been surprising if I'd created a max heap.

> Another small problem I have found was caused by BinaryHeap.pop().
> I'd like it to pop and return a single item, instead of an array of
> given length of items, because this is done quite more often than
> popping many items. If the need to pop many items is important, then
> a different method can be defined, as npop().

There exists a pop() function that only pops one element.

> Maybe BinaryHeap can be moved to the collections module.

Agreed.

> array(map(...)) is so common that an amap(...) can be considered.

I don't know.

> A helper function like this one can be useful: auto binaryHeap(alias
> less="a<  b", Range)(Range items) { return BinaryHeap!(Range,
> less)(items); } Note that the 'less' is before the Range, so in that
> program you can write: auto heap = binaryHeap!("b<  a")(s2w); Instead
> of: auto heap = BinaryHeap!(Block[], "b<  a")(s2w); And in many cases
> you just write: auto heap = binaryHeap(items);

Sounds good.

> I have seen that this doesn't work, but something like this can be
> useful (but I am not sure, I don't love strings used this way):
> schwartzSort!("a.code.length")(r);
>
>
> In Python there is both list.sort() and sorted(), the second creates
> a new list. In my dlibs1 I have similar functions. They allow you to
> write: return schwartzSorted!((x){ return x.code.length;
> })(...items); Instead of: auto r = ...items; schwartzSort!((x){
> return x.code.length; })(items); return items; So I'd like sorted and
> schwartzSorted in Phobos2.

I'm not crazy about functions that return large arrays by value. I'd 
have sorted() return a range (a heap!) that lazily spans the input in 
sorted order.

> While debugging this program I have found that array(iota(0, 10)) is
> an uint[] instead of being an int[]. In most cases I prefer that
> syntax to produce an array of true ints. In the uncommon situations
> when I want an array of uints I can ask it with a syntax like
> array(iota(0U, 10U)). If this specification is not possible then I
> prefer iota to always yield signed values, because they are much
> *safer* in D.
>
>
> I'd like iota(100) to be the same as iota(0, 100), as in the Python
> range().

Sounds good.

> To improve a *lot* my debugging in code like this I'd like this line
> of code: writeln(tuple(['x': 1.0, 'y': 2.0], "hello", [[1, 2], [3,
> 4]])); To print (better): tuple(['x': 1.0, 'y': 2.0], "hello", [[1,
> 2], [3, 4]]) Or even: Tuple!(double[char], string, int[][])(['x':
> 1.0, 'y': 2.0], "hello", [[1, 2], [3, 4]]) instead of:
> Tuple!(double[char],string,int[][])([x:1, y:2], hello, 1 2 3 4)

I've never had a clear view on what the target audience for writeln() 
is. You seem to want it to output debug strings; I'm not sure that's the 
best way to purpose it.


Andrei