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 18 years, 10 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 - 18 years, 10 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 18 years, 10 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 18 years, 10 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 18 years, 10 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 18 years, 10 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) 18 years, 10 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 18 years, 10 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