Re: maintaining a sorted structure

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.

Comment on Re: maintaining a sorted structure

Replies are listed 'Best First'.
Re^2: maintaining a sorted structure by Anonymous Monk on Jan 26, 2011 at 16:48 UTC
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]
Re^3: maintaining a sorted structure by tilly (Archbishop) on Jan 26, 2011 at 18:24 UTC
Using DB_File or BerkeleyDB you can easily tie a hash to a BTree, which offers the features that you want.	[reply]
Re^4: maintaining a sorted structure by Anonymous Monk on Jan 26, 2011 at 21:14 UTC
inspired.	[reply]
Re^3: maintaining a sorted structure by JavaFan (Canon) on Jan 26, 2011 at 18:01 UTC
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] [d/l] [select]
Re^3: maintaining a sorted structure by Anonymous Monk on Jan 26, 2011 at 17:33 UTC
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!	[reply]