Re^2: maintaining a sorted structure

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?

Comment on Re^2: maintaining a sorted structure

Replies are listed 'Best First'.
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]