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 06:42:58 EST 2017


Jussi Piitulainen wrote:

> Peter Otten writes:
> 
>> 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()?
> 
> Only let min see the data up to, but including, the stop value:

I should have mentioned that my actual use case has a costly key() function.

> from itertools import groupby
> 
> 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

A clever takeuntil() implementation ;) I may steal it for my current 
favourite

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]


> def stopmin(data, key, stop):
>     return min(takeuntil(data, lambda o : key(o) == stop),
>                key = key)
> 
> data = '31415926'
> for stop in range(5):
>     print(stop,
>           '=>', repr(''.join(takeuntil(data, lambda o : int(o) == stop))),
>           '=>', repr(stopmin(data, int, stop)))
> 
> # 0 => '31415926' => '1'
> # 1 => '31' => '1'
> # 2 => '3141592' => '1'
> # 3 => '3' => '3'
> # 4 => '314' => '1'
> 
> from itertools import count, chain
> print(stopmin(chain(reversed(range(10)), count()), key=abs, stop=0))
> print(stopmin(chain(reversed(range(10)), count()), key=abs, stop=3))
> 
> # 0
> # 3




More information about the Python-list mailing list