Search a sequence for its minimum and stop as soon as the lowest possible value is found
Peter Otten
__peter__ at web.de
Sat Jan 7 07:15:22 EST 2017
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
More information about the Python-list
mailing list