does python multiplicative expression evaluates faster if finds a zero?

Question

suppose i a have a multiplicative expression with lots of multiplicands (small expressions)

expression = a*b*c*d*....*w   

where for example c is (x-1), d is (y**2-16), k is (xy-60)..... x,y are numbers
and i know that c,d,k,j maybe zero
Does the order i write the expression matters for faster evaluation?
Is it better to write cdkj....*w or python will evaluate all expression no matter the order i write?

Answer 1

Python v2.6.5 does not check for zero values.

def foo():
    a = 1
    b = 2
    c = 0
    return a * b * c

>>> import dis
>>> dis.dis(foo)
  2           0 LOAD_CONST               1 (1)
              3 STORE_FAST               0 (a)

  3           6 LOAD_CONST               2 (2)
              9 STORE_FAST               1 (b)

  4          12 LOAD_CONST               3 (3)
             15 STORE_FAST               2 (c)

  5          18 LOAD_FAST                0 (a)
             21 LOAD_FAST                1 (b)
             24 BINARY_MULTIPLY     
             25 LOAD_FAST                2 (c)
             28 BINARY_MULTIPLY     
             29 RETURN_VALUE        

Update: I tested Baldur's expressions, and Python can and will optimize code that involve constant expressions. The weird is that test6 isn't optimized.

def test1():
    return 0 * 1

def test2():
    a = 1
    return 0 * a * 1

def test3():
    return 243*(5539**35)*0

def test4():
    return 0*243*(5539**35)

def test5():
    return (256**256)*0

def test6():
    return 0*(256**256)

>>> dis.dis(test1) # 0 * 1
  2           0 LOAD_CONST               3 (0)
              3 RETURN_VALUE       

>>> dis.dis(test2) # 0 * a * 1
  5           0 LOAD_CONST               1 (1)
              3 STORE_FAST               0 (a)

  6           6 LOAD_CONST               2 (0)
              9 LOAD_FAST                0 (a)
             12 BINARY_MULTIPLY     
             13 LOAD_CONST               1 (1)
             16 BINARY_MULTIPLY     
             17 RETURN_VALUE        

>>> dis.dis(test3) # 243*(5539**35)*0
  9           0 LOAD_CONST               1 (243)
              3 LOAD_CONST               5 (104736434394484...681759461305771899L)
              6 BINARY_MULTIPLY     
              7 LOAD_CONST               4 (0)
             10 BINARY_MULTIPLY     
             11 RETURN_VALUE        

>>> dis.dis(test4) # 0*243*(5539**35)
 12           0 LOAD_CONST               5 (0)
              3 LOAD_CONST               6 (104736433252667...001759461305771899L)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

>>> dis.dis(test5) # (256**256)*0
 15           0 LOAD_CONST               4 (0L)
              3 RETURN_VALUE        

>>> dis.dis(test6) # 0*(256**256)
 18           0 LOAD_CONST               1 (0)
              3 LOAD_CONST               3 (323170060713110...853611059596230656L)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

In brief, if the expression includes variables, the order doesn't matter. Everything will be evaluated.

Answer 2

Don't try to optimize before you benchmark.

With that in mind, it is true that all expressions will be evaluated even if an intermediate term is zero.

Order may still matter. Expressions are evaluated from left to right. If a,b,c,... are very large numbers, they could force Python to allocate a lot of memory, slowing down the calculation before it comes to j=0. (If j=0 came earlier in the expression, then the product would never get as large and no additional memory allocation would be needed).

If, after timing your code with timeit or cProfile, you feel this may be your situation, then you could try pre-evaluating c,d,k,j, and testing

if not all (c,d,k,j):
    expression = 0
else:
    expression = a*b*c*d*....*w

Then time this with timeit or cProfile as well. The only way to really tell if this is useful in your situation is to benchmark.

In [333]: import timeit

In [334]: timeit.timeit('10**100*10**100*0')
Out[334]: 1.2021231651306152

In [335]: timeit.timeit('0*10**100*10**100')
Out[335]: 0.13552498817443848

Although PyPy is much faster, it does not appear to optimize this either:

% pypy-c
Python 2.7.3 (d994777be5ab, Oct 12 2013, 14:13:59)
[PyPy 2.2.0-alpha0 with GCC 4.6.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``http://twitpic.com/52ae8f''
>>>> import timeit
>>>> timeit.timeit('10**100*10**100*0')
0.020643949508666992
>>>> timeit.timeit('0*10**100*10**100')
0.003732919692993164

Answer 3

This is just a quick check in Python 3.1:

>>> import timeit
>>> timeit.timeit('243*325*(5539**35)*0')
0.5147271156311035
>>> timeit.timeit('0*243*325*(5539**35)')
0.153839111328125

and this in Python 2.6:

>>> timeit.timeit('243*325*(5539**35)*0')
0.72972488403320312
>>> timeit.timeit('0*243*325*(5539**35)')
0.26213502883911133

So the order does enter into it.

Also I got this result in Python 3.1:

>>> timeit.timeit('(256**256)*0')
0.048995018005371094
>>> timeit.timeit('0*(256**256)')
0.1501758098602295

Why on Earth?

Answer 4

>>> import timeit
>>> timeit.timeit('1*2*3*4*5*6*7*8*9*9'*6)
0.13404703140258789
>>> timeit.timeit('1*2*3*4*5*6*7*8*9*0'*6)
0.13294696807861328
>>> 

Answer 5

Probably not. Multiplication is one of the cheapest operations of all. If a 0 should be faster then it would be necessary to check for zeros before and that's probably slower than just doing the multiplication.

The fastest solution should be multiply.reduce()