Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re^2: Does perl6 have a native linked-list data type? (trees)

by tye (Sage)
on Nov 17, 2010 at 19:27 UTC ( #872036=note: print w/replies, xml ) Need Help??

in reply to Re: Does perl6 have a native linked-list data type?
in thread Does perl6 have a native linked-list data type?

The main fundamental data structure I find missing from Perl 5 is the "sorted associative array". I'd say "sorted hash" because it should act like a Perl hash except the keys are sorted, except that such are not implemented via a hash table; they are usually implemented via balanced trees.

Yes, there are various implementations of sorted hashes that have been bolted on to Perl 5. Many of them don't scale like a real balanced tree implementation would. The ones that scale well usually have a quite significant performance penalty constant applied to them (such as due to using tie or being file-based) and the rest usually have significant complications related to availability, convenience, flexibility, etc.

If there is one "best", efficient and convenient implementation of "sorted associative array" for Perl 5, then I'm not aware of it. This is likely my ignorance. I'd love to be pointed to a really good solution to this problem.

Complaining about this again reminded me of Judy. I even got excited when I saw Judy::HS mentioned as being keyed by arbitrary Perl strings. I have a good deal of appreciation for the Judy data structure and of respect for the author of the Judy module, so I figured there was a good chance that this was what I'd been hoping for. But Judy::HS values are restricted to being integers.

It seems a small step to go from "integer" to SV or even just to "reference" but a step perhaps better done in C (XS). I've put out an inquiry to the author regarding this.

Anyway, the times I have longed for a linked list in Perl 5, a sorted associative array would've been an acceptable solution (often better, in some ways). Perhaps such would scratch the Y (or Ys, if any) behind the original poster's X. :)

- tye        

  • Comment on Re^2: Does perl6 have a native linked-list data type? (trees)

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://872036]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (1)
As of 2022-05-19 03:37 GMT
Find Nodes?
    Voting Booth?
    Do you prefer to work remotely?

    Results (71 votes). Check out past polls.