help with silly algorhythm

Jason Orendorff jason at jorendorff.com
Fri Feb 15 18:34:02 CET 2002


Kevin Parks writes:
> I realize that this is very odd and convoluted. If anyone can make
> heads or tails of this explanation and would like to help me I
> would be grateful.

This might be more readable than the previous poster's answers.
It should be faster, too, especially for large 'partners' lists.
You could do even better if you could guarantee that 'values'
is sorted too.

## Jason Orendorff    http://www.jorendorff.com/



# sillyalg.py - Silly algorithm

import bisect

values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
partners = [1, 3, 7, 10]


# Mode 1
def upper(list, item):
    """ Return the least element greater than item in list.
    The list must be sorted!

    If item is greater than all items in 'list', then wrap around and
    return the least item.
    """
    index = bisect.bisect_right(list, item)
    if index == len(list):
        index = 0
    return list[index]

print "Mode 1"
print [[i, upper(partners, i)] for i in values]
print [upper(partners, i) for i in values]


# Mode 2
def lower(list, item):
    """ Analogous to upper(). """
    index = bisect.bisect_left(list, item)
    if index == 0:
        index = len(list)
    return list[index - 1]

print "Mode 2"
print [[i, lower(partners, i)] for i in values]
print [lower(partners, i) for i in values]


# Mode 3
def even_upper(list, item, n):
    functions = (upper, lower)
    fn = functions[n%2]  # choose which function
    return fn(list, item)

print "Mode 3"
print [[values[n], even_upper(partners, values[n], n)]
       for n in range(len(values))]
print [even_upper(partners, values[n], n) for n in range(len(values))]






More information about the Python-list mailing list