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

[Peter Otten]

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:

Thanks everyone who contributed to this thread!

For those interested here's my collection of stopmin() implementations so 
far. Remember, there should be one ... *obvious* way to do it (emphasis 
mine).

$ cat stopmin_simple.py               
import functools
import operator
import re

from itertools import groupby
from functools import lru_cache


def steal_doc(f):
    def set_doc(g):
        sub = re.compile(r"\b{}\b".format(f.__name__)).sub
        g.__doc__ = sub(g.__name__, f.__doc__)
        return g
    return set_doc


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'
    >>> 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'
    """
    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]


def takeuntil(data, pred):
    '''Take values from data until and including the first that
    satisfies pred (until data is exhausted if none does).'''
    for kind, group in groupby(data, pred):
        if kind:
            yield next(group)
            break
        else:
            yield from group


@steal_doc(stopmin)
def stopmin_jussi(data, *, key, stop):
    key = lru_cache(maxsize=1)(key)
    return min(
        takeuntil(data, lambda o: key(o) <= stop),
        key=key
    )


@steal_doc(stopmin)
def stopmin_wolfgang(iterable, *, key, stop):
    key = lru_cache(maxsize=1)(key)

    def take_until():
        for e in iterable:
            yield e
            if key(e) <= stop:
                break
    return min(take_until(), key=key)


firstitem = operator.itemgetter(0)


@steal_doc(stopmin)
def stopmin_du(items, *, key, stop):
    # decorate, process, undecorate
    pairs = ((key(item), item) for item in items)
    pairs = takeuntil(pairs, lambda pair: pair[0] <= stop)
    return min(pairs, key=firstitem)[1]


@functools.total_ordering
class Pair:
    __slots__ = ["key", "value"]

    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __lt__(self, other):
        return self.key < other.key


@steal_doc(stopmin)
def stopmin_du2(items, *, key, stop):
    pairs = (Pair(key(item), item) for item in items)
    pairs = takeuntil(pairs, lambda p: p.key <= stop)
    return min(pairs).value


@steal_doc(stopmin)
def stopmin_steve(iterable, *, key, stop):
    it = iter(iterable)
    try:
        smallest = next(it)
    except StopIteration:
        raise ValueError('empty iterable has no minimum')
    keyed_smallest = key(smallest)
    if keyed_smallest <= stop:
        return smallest
    for x in it:
        y = key(x)
        if y < keyed_smallest:
            keyed_smallest = y
            smallest = x
        if y <= stop:
            break
    return smallest


@steal_doc(stopmin)
def stopmin2(items, key, stop):
    pairs = ((key(item), item) for item in items)
    try:
        minkey, minval = next(pairs)
    except StopIteration:
        raise ValueError("stopmin2() arg is an empty sequence")
    if minkey <= stop:
        return minval
    for k, v in pairs:
        if k < minkey:
            if k <= stop:
                return v
            minkey = k
            minval = v
    return minval
$ pep8 stopmin_simple.py
$ python3 -m doctest stopmin_simple.py