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?
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.
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
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?
>>> 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
>>>
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()
