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. | [reply] [Watch: Dir/Any] |
|
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
| [reply] [Watch: Dir/Any] |
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.
| [reply] [Watch: Dir/Any] |
|
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?
| [reply] [Watch: Dir/Any] |
|
Using DB_File or BerkeleyDB you can easily tie a hash to a BTree, which offers the features that you want.
| [reply] [Watch: Dir/Any] |
|
|
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.
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
| [reply] [Watch: Dir/Any] |