help retrieving / storing info in dictionary or gadfly

[Sune Kirkeby]

[ "Bryan Webb" <bww00 at amdahl.com> ]

>     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.  Is there a way to further index the list of keys to
> do this ?

Since the list is sorted (in ascending order, presumably), you could
just do a binary search through it.  Something along the lines of,

def find(list, number):
    """Given a list of numbers, sorted in ascending order, find the
    largest element that is less-than-or-equal some given number.  If a
    fitting element is found return this (the value, that is);
    otherwise it return None."""
    
    # Sanity check
    if len(list) == 0:
        return None
    
    # Simple binary search through the list.
    pivot = len(list) / 2
    while list[pivot] != number:
        # If the pivot is less-than the sought-for number we include
        # the pivot in the further search (so we can find the nearest
        # number that is less-than, if no exact match is found).
        if list[pivot] < number:
            list = list[pivot : ]
        else:
            list = list[0 : pivot]
        pivot = len(list) / 2
        
        if len(list) == 1:
            break
    
    # Done, if list[pivot] > number we searched all the way down to the
    # bottom of the list, but found no match, so we return None since
    # all elements in the list are greater-than the number.
    if list[pivot] <= number:
        return list[pivot]
    else:
        return None

> Could I use GADFLY to do this.

Dunno.

-- 
Sune Kirkeby                    | "Imagine, if you will, that there were no
http://mel.interspace.dk/~sune/ | such thing as a hypothetical situation..."