at_most: search "dictionary" for less than or equal

[slais-www]

Before I set out to reinvent the wheel.

I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary "; in which case I want a key/value
returned which is the closest key that is less than the search term.


The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.


--
djc

[bearophileHUGS@lycos.com]

Re: at_most: search "dictionar y" for less than or equal

slais-www, a BK-tree maybe isn't right what you need but it may be
enough:

http://code.activestate.com/recipes/572156/

Bye,
bearophile

[Paul McGuire]

Re: at_most: search "dictionar y" for less than or equal

On Aug 11, 9:18 am, slais-www <slais-...@ucl.ac.ukwr ote:

Before I set out to reinvent the wheel.
>
I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary "; in which case I want a key/value
returned which is the closest key that is less than the search term.
>
The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.
>
--
djc

Sounds like you have very long lists to work with. Maybe a solution
using bisect would combine simplest structure with best performance.

-- Paul