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

[Peter Otten]

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]