Welcome, guest | Sign In | My Account | Store | Cart

Sometimes it is useful to know what is the smallest value in a sequence greater than (or equal to) some other value. Eg.

max_lt([2, 3, 5, 7, 11], 6) would be 5, because 5 is greatest value in the list which is also less than 6. Following the same lines method call min_gt([3, 5, 6, 10, 12], 6) would return 10, because 10 is the smallest value in the list greater than 6. The following four simple methods implement min_gt, min_le, max_gt and max_ge, but the input must be sorted for them to work.

However, Greg Jorgensen's suggestion is much more clever. No need for sorting, just use list comprehensions with min/max.

Python, 66 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def min_gt(seq, val):
    """
    Return smallest item in seq for which item > val applies.
    None is returned if seq was empty or all items in seq were <= val.

    >>> min_gt([1, 3, 6, 7], 4)
    6
    >>> min_gt([2, 4, 7, 11], 5)
    7
    """

    for v in seq:
        if v > val:
            return v
    return None

def min_ge(seq, val):
    """
    Same as min_gt() except items equal to val are accepted as well.

    >>> min_ge([1, 3, 6, 7], 6)
    6
    >>> min_ge([2, 3, 4, 8], 8)
    8
    """

    for v in seq:
        if v >= val:
            return v
    return None

def max_lt(seq, val):
    """
    Return greatest item in seq for which item < val applies.
    None is returned if seq was empty or all items in seq were >= val.

    >>> max_lt([3, 6, 7, 11], 10)
    7
    >>> max_lt((5, 9, 12, 13), 12)
    9
    """

    idx = len(seq)-1
    while idx >= 0:
        if seq[idx] < val:
            return seq[idx]
        idx -= 1
    return None

def max_le(seq, val):
    """
    Same as max_lt(), but items in seq equal to val apply as well.

    >>> max_le([2, 3, 7, 11], 10)
    7
    >>> max_le((1, 3, 6, 11), 6)
    6
    """

    idx = len(seq)-1
    while idx >= 0:
        if seq[idx] <= val:
            return seq[idx]
        idx -= 1

    return None

An example follows:

<pre> percentages = range(0, 100, 5) # all percentages from 0 to 95 at 5-step intervals

give as large share for each object as possible, using those fixed percentages

items_to_share = 148

for obj in mycontainer: my_share = max_le(percentages, items_to_share/len(mycontainer)) # convert it to percentage my_share /= 100.0

obj.acquire_items(int(my_share*items_to_share)) </pre>

Now each object get as much items as possible so that total percentage is An example follows:

<pre> percentages = range(0, 100, 5) # all percentages from 0 to 95 at 5-step intervals

give as large share for each object as possible, using those fixed percentages

items_to_share = 148

for obj in mycontainer: my_share = max_le(percentages, items_to_share/len(mycontainer)) # convert it to percentage my_share /= 100.0

obj.acquire_items(int(my_share*items_to_share)) </pre>

Now each object get as much items as possible so that total percentage is

8 comments

Greg Jorgensen 16 years, 6 months ago  # | flag

simpler recipes. The requirement that the sequences are sorted, and the use of len() in two of the functions, means that the functions won't work on any iterable; they will only work on simple sequences. Try these more versatile functions that will work on any iterable, sorted or not:

def min_gt(seq, val):
    return min([v for v in seq if v &gt; val])

def min_ge(seq, val):
    return min([v for v in seq if v &gt;= val])

def max_lt(seq, val):
    return max([v for v in seq if v &lt; val])

def max_le(seq, val):
    return max([v for v in seq if v &lt;= val])

If you want all values greater than or less than a specific value in a sequence, a list comprehension is a clear and concise technique:

[v for v in seq if v &gt; val]

Once you have the resulting list, applying the min or max functions will extract the smallest or largest value.

bearophile - 16 years, 6 months ago  # | flag

Alternative. Removing the [] can be positive on the last versions of Python, for example:

def min_gt(seq, val):
    return min(v for v in seq if v > val)

def min_ge(seq, val):
    return min(v for v in seq if v >= val)
Yair Chuchem 16 years, 6 months ago  # | flag

bisect module. The standard module bisect does these stuff, and quickly too.

A useful module, You should get to know it.

Yair Chuchem 16 years, 6 months ago  # | flag

Binary search. The bisect module does the search with the binary search algorithm, which is O(log N). Instead of yours O(N) recipe.

Larry Hastings 16 years, 6 months ago  # | flag

Original recipe is broken. Sadly, this recipe needs to go back to the kitchen.

min_gt and min_ge will return the first value they find that is greater than (or possibly equal to) the value "val". min_gt([1, 3, 8, 7, 6], 6) returns 8, not 7. min_ge([2, 3, 4, 10, 8], 8) returns 10, not 8.

Also, min_ge() has a parameter "sorted=false" which isn't referenced anywhere in the recipe's body... what's up with that?

Greg Jorgensen 16 years, 6 months ago  # | flag

bisect suitable for some applications, not all. bisect only works on lists, not any iterable, and it requires that the list be sorted. If you have a sorted list, or something that can be turned into a sorted list, bisect is a good way to quickly find elements in the list. If you have arbitrary iterables or can't sort your list, bisect won't be much help.

Edvard Majakari (author) 16 years, 6 months ago  # | flag

Input must be sorted in examples. ..but forgot to mention in the docs. The remaining parameter sorted=False was in my first versions, where methods sorted input if it was needed. However, using

max([for i in items where i &lt; val])

is far more clear and makes my recipe useless :)

I think the bisect module will be even better, though the list comprehension should be the easiest to understand.

Qiangning Hong 16 years, 6 months ago  # | flag

Just for completion... Rewrite the recipe using bisect module:

from bisect import bisect_left, bisect_right

def min_gt(seq, val):
    return seq[bisect_right(seq, val)]

def min_ge(seq, val):
    return seq[bisect_left(seq, val)]

def max_lt(seq, val):
    return seq[bisect_left(seq, val) - 1]

def max_le(seq, val):
    return seq[bisect_right(seq, val) - 1]
Created by Edvard Majakari on Thu, 26 May 2005 (PSF)
Python recipes (4591)
Edvard Majakari's recipes (4)

Required Modules

  • (none specified)

Other Information and Tasks