in reply to Judy arrays and Perl

Of course. Anything that manages to eliminate several tertiary structures, as you've indicated, and does not bring performance penalties, would be welcomed by me.

Update: I forgot to mention saving me valuable time and effort... any Perl implementation would be welcomed, but since i am already a data structures/algorithms obsessive I will probably end up implementing it anyway (to add to my existing pile of bizarre heap's and sorting methods)...

Update(2): Ok, 'Judy' is basically a trie, since this has been dealt with wonderfully by demerphq, i won't go into details... also try 10 minute description

Replies are listed 'Best First'.
Re: Re: Judy arrays and Perl
by demerphq (Chancellor) on Jun 20, 2002 at 15:41 UTC
    i am already a data structures/algorithms obsessive

    You too eh? My next target (ive got Trie's, Efficient Huffman Encoding, 2-3 trees, Pagoda Heaps under my belt so far) is a Treap. Any idea of a good place to look for documentation? Knuth only provided the most fleeting mention in AoP, and apparently they outperform splay trees and normal heap implementations (while being fully ordered) so I really want to release a CPAN implementation (especially as IMO the Heap:: heirarchy chews)

    BTW thanks for the nod. :-)

    Yves / DeMerphq
    ---
    Writing a good benchmark isnt as easy as it might look.

[reply]
      My own reference for implementing a Treap was section 2 of this paper.

      A google search for Randomized Search Trees provided only a handful of relevant links. The entry in NIST DADS was pathetic, but provided a link to an implementation in Scheme.

[reply]
        Hmm. the paper link seemed to be to only an abstract... (did i miss a link?)

        Anyway I found this Animated Treap Example which looks fairly interesting. I also found these. When I get a chance i'll put together a perl implementation..

        Treap Explanation and Java Treap

        Yves / DeMerphq
        ---
        Writing a good benchmark isnt as easy as it might look.

[reply]

In Section Meditations