Does Python's reduce() short circuit?

If I do:

result = reduce(operator.and_, [False] * 1000)

Will it stop after the first result? (since False & anything == False)

Similarly:开发者_如何学Python

result = reduce(operator.or_, [True] * 1000)

It doesn't. Your alternative in this case is any and all.

result = reduce(operator.and_, [False] * 1000)
result = reduce(operator.or_, [True] * 1000)

can be replaced by

result = all([False] * 1000)
result = any([True] * 1000)

which do short circuit.

The timing results show the difference:

In [1]: import operator

In [2]: timeit result = reduce(operator.and_, [False] * 1000)
10000 loops, best of 3: 113 us per loop

In [3]: timeit result = all([False] * 1000)
100000 loops, best of 3: 5.59 us per loop

In [4]: timeit result = reduce(operator.or_, [True] * 1000)
10000 loops, best of 3: 113 us per loop

In [5]: timeit result = any([True] * 1000)
100000 loops, best of 3: 5.49 us per loop

Not only does reduce() not short-circuit, it cannot possibly short-circuit over all the items being reduced, because it only considers the items two at a time. Additionally, it has no idea of the conditions under which the function being used short-circuits. (It would be sorta nifty if functions could have a property that indicates the value at which they begin to short-circuit, which reduce() could then recognize and use, but they don't.)

It may well be possible (see fate of reduce) that an alternative reduce implementation will do a good job.

This idea has perfectly worked for me to make things more transparent in the design.

def ipairs(seq):
    prev = None
    for item in seq:
        if prev is not None:
            yield (prev, item)
        prev = item

def iapply(seq, func):
    for a, b in ipairs(seq):
        yield func(a, b)

def satisfy(seq, cond):
    return all(iapply(seq, cond))

def is_uniform(seq):
    return satisfy(seq, lambda a, b: a == b)

As you see reduce is broken into iapply <- ipairs.

Please note it is not equivalent to

def ireduce(seq, func):
    prev = None
    for item in seq:
        if prev is None:
            prev = item
        else:
            prev = func(prev, item)
    return prev

Bear in mind that short circuit evaluation is not always what you want. "Fixing" reduce to short circuit would be a mistake for that reason. For example, I recently had to change my use of all() to reduce() while processing a list of forms in django: I want to report any is_valid() problems, not just the first one.

I had a related use case where I wanted a behavior different from any and all but equivalent to a loop over or and and. The solution is to use filter rather than reduce.

any returns booleans while or returns the last object evaluated as True.

>>> any(['', 'a'])
True
>>> any(['', ''])
False
>>> any([0, 1])
True
>>> any([0, 0])
False

or returns the last object evaluated as True.

>>> '' or 'a'
'a'
>>> '' or ''
''
>>> 0 or 1
1
>>> 0 or 0
0

reduce(operator.or_, xs) will not short circuit but next(filter(bool, xs)) in python3 or next(itertools.ifilter(bool, xs)) in python2 will short circuit. It is not because filter short circuits, but because iterator returned is lazy and will only evaluate when needed. By using next we are only asking for first element that satisfies the filter criteria.

>>> def maybenext(iter, onstopiter=False):
...     try: return  next(iter)
...     except StopIteration: return onstopiter
...     
>>> 
>>> maybenext(filter(bool, ['', 'a']))
'a'
>>> maybenext(filter(bool, ['', '']))
False
>>> maybenext(filter(bool, [0, 1]))
1
>>> maybenext(filter(bool, [0, 0]))
False

The result is not as fast as any but close enough

>>> %timeit maybenext(filter(bool, [1] * 1000))
2.48 µs ± 91.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit any([1] * 1000)
2.26 µs ± 90.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit reduce(operator.or_, [1] * 1000)
47.3 µs ± 1.75 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Here's a possible lazy reduce implementation:

from itertools import accumulate

def lazy_reduce(pred, reducer, it, initial=None):
    accum = accumulate(it, reducer, initial=initial)
    last = None
    for item in accum:
        last = item
        if pred(item):
            return item
    return last

This should work like reduce but will short on pred.

from operator import add
from itertools import count
res = short_reduce(lambda x: x > 20, add, count(1,8)) # 27