Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

maintaining a sorted structure

by Anonymous Monk
on Jan 26, 2011 at 16:21 UTC ( [id://884375]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Is there something like a heap or std::map that I can use to maintain elements in sorted order? (I don't have the ability to readily install CPAN, but I saw POSIX::bsearch and Heap.) I guess perl does not have a lower_bound (or bsearch) function as standard part of the language? Is there a technique to do range-like lookup with hashes other than binning? I don't know my data's distribution in advance.

Replies are listed 'Best First'.
Re: maintaining a sorted structure
by Sinistral (Monsignor) on Jan 26, 2011 at 16:38 UTC
    First of all Yes, even you can use CPAN. The basic equivalent of a C++ std::map is the hash. However, as you know, Perl hashes do not maintain order. For an ordered hash, there's Tie::IxHash, which doesn't have specific search functions, but does let you reorder the data structure by key. Even though you mention std::map (hash), you might want to check out the options in List::MoreUtils and List::Util.
      Sinistral,
      For an ordered hash, there's Tie::IxHash, which doesn't have specific search functions, but does let you reorder the data structure by key

      Tie::IxHash maintains insertion order which is very unlikely to be sorted order indicated by the OP. Yes, it does have rudimentary manual sort capability (asciibetical sort by keys or values). It also has the ability to manually reorder the keys arbitrarily but the user must first do the sort. If what you need is a sorted hash and not an insertion order hash, then you should use Tie::Hash::Sorted which is designed for that purpose and also has a number of optimizations.

      Disclaimer: I am the author of Tie::Hash::Sorted

      Cheers - L~R

Re: maintaining a sorted structure
by BrowserUk (Patriarch) on Jan 26, 2011 at 16:38 UTC
    Is there something ... I can use to maintain elements in sorted order?

    Load them, sort them, then don't add or delete. Done.

    I realise that might not work for your application, but of the 50 possible reasons why it might not work, there is no information in your post to tell us which reasons might be applicable. Therefore, there is not enough information for us to offer a solution.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      I need to implement Excel's VLOOKUP with RANGE_SEARCH set to true. E.g., given an array, I can iterate to find the index of the element with the smallest value greater than my key; but if I have a sorted array, I can do much better with a binary search. Further, I would like to be able to update the array (insert elements in the middle) with minimal cost. C++ std::map does this almost automatically. I can implement upper_bound better than most other perl users. I can also make a RB or AVL tree from scratch. But, such standard functionality -- is there a cheap/easy way to get sub O(N) performance, using the out-of-the-box functionality of perl?
        Using DB_File or BerkeleyDB you can easily tie a hash to a BTree, which offers the features that you want.
        is there a cheap/easy way to get sub O(N) performance, using the out-of-the-box functionality of perl?
        No. It is possible to do o(N) queries, but only after ω(N) pre-processing time. That's independent of the language.
        Further, I would like to be able to update the array (insert elements in the middle) with minimal cost.
        If you mean by "updating", "adding more elements", using a traditional Perl array, it takes linear time.

        CPAN is part of the box.

        Its nice to be able to make your own tools from scratch, but there is a bag of steel power tools under the styrofoam peanuts. Just plug them in!

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://884375]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2024-03-28 23:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found