[Python-Dev] Fwd: summing a bunch of numbers (or "whatevers")

[Tim Peters]

[Alex Martelli]
> Hmmm, I think I must be missing something here.  Surely in many
> application cases a loop exploiting short-circuiting behavior will have
> better expected performance than anything that's going all the way
> through the sequence no matter what?

No, you're only missing that I seem rarely to have apps where it actually
matters.

> Far greater variance, sure, and if the probability of true items gets
> extreme enough then the gain from short-circuiting will evaporate,

Or, more likely, become a pessimization (liability).

> but...:
>
> [alex@lancelot src]$ ./python Lib/timeit.py -s'seq=[i%2 for i in
> range(9999)]'
> -s'''
> > def any(x):
> >   for xx in x:
> >     if xx: return True
> >   return False
> > ''' 'any(seq)'
> 1000000 loops, best of 3: 1.42 usec per loop
>
> [alex@lancelot src]$ ./python Lib/timeit.py -s'seq=[i%2 for i in
> range(9999)]'
> -s'''
> def any(x):
>   return bool(filter(None,x))
> ''' 'any(seq)'
> 1000 loops, best of 3: 679 usec per loop
>
> ...i.e., despite filter's amazing performance, looping over 10k
> items still takes a bit more than shortcircuiting out at once;-).

It's only because Guido sped up loops for 2.3 <wink>.

> If Python ever gains such C-coded functions as any, all, etc (hopefully
> in some library module, not in builtins!) I do hope and imagine they'd
> short-circuit, of course.  BTW, I think any should return the first
> true item (or the last one if all false, or False for an empty sequence)
> and all should return the first false item (or the last one if all true,
> or True for an empty seq) by analogy with the behavior of operators
> and/or.

I agree that getting the first witness (for "any") or counterexample (for
"all") can be useful.  I'm not sure I care what it returns if all are false
for "any", or all true for "all".  If I don't care, they're easy to write
with itertools now:

"""
import itertools

def all(seq):
    for x in itertools.ifilterfalse(None, seq):
        return x # return first false value
    return True

def any(seq):
    for x in itertools.ifilter(None, seq):
        return x # return first true value
    return False

print all([1, 2, 3]) # True
print all([1, 2, 3, 0, 4, 5]) # 0, the first counterexample

print any([0, 0, 0, 0]) # False
print any([0, 42, 0, 0]) # 42, the first witness
"""

I liked ABC's quantified boolean expressions:

    SOME x IN collection HAS bool_expression_presumably_referencing_x
    EACH x IN collection HAS bool_expression_presumably_referencing_x
    NO x IN collection HAS bool_expression_presumably_referencing_x

The first left x bound to the first witness when true.  ABC didn't have
boolean data values -- these expressions could only be used in control-flow
statements (like IF).  x was then a block-local binding in the block
controlled by the truth of the expression, so there was no question about
what to do with x when the expression was false (you didn't enter the block
then, so couldn't reference the block-local x).

The second and third left x bound to the first counterexample when the
expression was false, and in those cases x was local to the ELSE clause.

I viewed that as finessing around a question that shouldn't be asked, via
the simple expedient of making the question unaskable <wink>.  The exact
rules were pretty complicated, though.