Re: numfmt enhancements to emulate df -g

[Pádraig Brady]

On 20/06/15 03:57, Dylan Cali wrote:
> On Fri, Jun 19, 2015 at 3:08 PM, Pádraig Brady <address@hidden> wrote:
>> Dylan I used/adjusted your patch for multiple fields support.
> 
> Thanks Pádraig, excited to see this making its way into the mainline.
> 
>> Note I moved from an avltree to a linked list so that memory
>> consumption was proportional to the number of field specifications,
>> rather than the number of fields specified.
> 
> Can't you store field specifications as the elements in an avl tree as
> well, without having to resort to something fancy like an interval
> tree?  And if it's the same number of elements, shouldn't memory
> consumption be the same as with a linked list since they're both node
> based structures?

With most and all standard range specs this would work,
though for certain overlapping range specs, the short circuiting
involved in the tree search could skip matching pairs.

> I went with the avl tree just because theoretically if someone were to
> list duplicate, out of order fields (or field specs) inserting them is
> going to be O(n) with a sorted linked list vs O(logn) with a binary
> search tree.  Obviously for such a small cli tool it doesn't really
> matter though.

Right, the vast majority of cases is very few specified pairs.
Again focusing on performance would take advantage of the
linear scan being done, like cut does.

cheers,
Pádraig.