|
in reply to Re: maintaining a sorted structure
in thread 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?
|
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] |
|
|
| [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] |
|
