Search a sequence for its minimum and stop as soon as the lowest possible value is found

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]