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.
Download
Copy to clipboard1 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
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:
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:
Once you have the resulting list, applying the min or max functions will extract the smallest or largest value.
Alternative. Removing the [] can be positive on the last versions of Python, for example:
bisect module. The standard module bisect does these stuff, and quickly too.
A useful module, You should get to know it.
Binary search. The bisect module does the search with the binary search algorithm, which is O(log N). Instead of yours O(N) recipe.
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?
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.
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
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.
Just for completion... Rewrite the recipe using bisect module: