Search a sequence for its minimum and stop as soon as the lowest possible value is found
Peter Otten
__peter__ at web.de
Mon Jan 9 12:30:30 EST 2017
Antonio Caminero Garcia wrote:
> On Friday, January 6, 2017 at 6:04:33 AM UTC-8, Peter Otten wrote:
>> Example: you are looking for the minimum absolute value in a series of
>> integers. As soon as you encounter the first 0 it's unnecessary extra
>> work to check the remaining values, but the builtin min() will continue.
>>
>> The solution is a minimum function that allows the user to specify a stop
>> value:
>>
>> >>> from itertools import count, chain
>> >>> stopmin(chain(reversed(range(10)), count()), key=abs, stop=0)
>> 0
>>
>> How would you implement stopmin()?
>>
>> Currently I raise an exception in the key function:
>>
>> class Stop(Exception):
>> pass
>>
>> def stopmin(items, key, stop):
>> """
>> >>> def g():
>> ... for i in reversed(range(10)):
>> ... print(10*i)
>> ... yield str(i)
>> >>> stopmin(g(), key=int, stop=5)
>> 90
>> 80
>> 70
>> 60
>> 50
>> '5'
>> """
>> def key2(value):
>> result = key(value)
>> if result <= stop:
>> raise Stop(value)
>> return result
>> try:
>> return min(items, key=key2)
>> except Stop as stop:
>> return stop.args[0]
>
> This is the simplest version I could come up with. I also like the classic
> 100% imperative, but it seems that is not trendy between the solutions
> given :D.
>
> you can test it here https://repl.it/FD5A/0
> source code:
>
> from itertools import accumulate
>
> # stopmin calculates the greatest lower bound (infimum).
> #
https://upload.wikimedia.org/wikipedia/commons/0/0a/Infimum_illustration.svg
>
> def takeuntil(pred, seq):
> for item in seq:
> yield item
> if not pred(item):
The "not": one of those decisions that can drive programmers into madness ;)
> break
>
> def stopmin(seq, stop=0):
> drop_ltstop = (item for item in seq if item >= stop)
> min_gen = (min_ for min_ in accumulate(drop_ltstop, func=min))
You don't need the genexp here; just accumulate() will do.
Using accumulate() is a nice suggestion, by the way.
> return list(takeuntil(lambda x: x!= stop, min_gen))[-1]
> seq = [1, 4, 7, -8, 0, 7, -8, 9] # 0 just until zero is generated
> seq = [1, 4, 7, -8, 7, -8, 9] # 1 the entire sequence is generated
>
> print(stopmin(seq, stop=0))
Once it passes my doctests your code isn't quite as simple, but still
readable:
from itertools import accumulate
from operator import itemgetter
from collections import deque
firstitem = itemgetter(0)
def takeuntil(pred, items):
for item in items:
yield item
if pred(item):
break
def last(items):
tail = deque(items, maxlen=1)
if tail:
return tail.pop()
else:
raise ValueError
def minkey(a, b):
return min(a, b, key=firstitem)
def stopmin(items, *, key, stop):
"""
>>> def g():
... for i in reversed(range(10)):
... print(10*i)
... yield str(i)
>>> stopmin(g(), key=int, stop=5)
90
80
70
60
50
'5'
>>> stopmin(g(), key=int, stop=8.5)
90
80
'8'
>>> stopmin(g(), key=int, stop=9)
90
'9'
>>> stopmin([10, 9, -11, 7, -12], key=abs, stop=0)
7
>>> try: stopmin([], key=abs, stop=0)
... except ValueError: print('OK')
OK
>>> stopmin("a", key=lambda x: print(x) or "c", stop="b")
a
'a'
>>> class A:
... def __init__(self, key):
... self.key = key
>>> stopmin([A(2), A(2), A(1), A(0)], key=lambda a: a.key, stop=1.1).key
1
"""
pairs = ((key(item), item) for item in items)
descending_pairs = accumulate(pairs, func=minkey)
return last(takeuntil(lambda p: p[0] <= stop, descending_pairs))[1]
More information about the Python-list
mailing list