help retrieving / storing info in dictionary or gadfly

[Alex Martelli]

"Bryan Webb" <bww00 at amdahl.com> wrote in message
news:93u48n$65t at dispatch.concentric.net...
> Hello,
>     I have a dictionary that has records with keys from 1 to 2^128
> I can build a list and sort the keys in order, then search thru the list
of
> sorted keys.
>     If the list has 1,2,3,4,5,7,8,9 and I need to search for 6. 6 is not
in
> the list , so I need the record that is closest to 6 but not greater than
6.

This is close to what bisect (see 5.5 in the library reference) does
for you, except it gives the index in the sorted list locating the key
closest but not smaller, rather than closest but not greater -- a number
from 0 to len(list), both extremes _included_ -- len(list) if the key
you're looking for is larger than the largest (last) entry in the sorted
list.  You presumably want -1 to len(list)-1 [again extremes included],
with -1 if the key is smaller than the smallest (first) entry.  You
can wrap bisect.bisect for your purposes, e.g.:

def locate(list, key):
    i = bisect.bisect(list,key)
    try:
        if list[i]==key:
            return i
    except IndexError:
        pass
    return i-1

> Is there a way to further index the list of keys to do this ?
>
> Could I use GADFLY to do this.

I don't see how you could do better than O(log N) to locate the
key 'closest but not greater', with any auxiliary data structure
of reasonable size, given your range of possible keys.  And that
is the performance behavior that bisect.bisect gives you.


Alex