Geek asks and answers

Can simple calculations for variable-length iterations run faster in Python?

I calculate the Euclidean distance between two vectors represented by tuples.

(u[0]-v[0])**2 + (u[1]-v[1])**2 + (u[3]-v[3])**2 ...

A hard-coded way to do this is pretty fast. However, I would not like to make any assumptions about the length of these vectors. This leads to solutions such as:

sum([(a-b)**2 for a, b in izip(u, v)]) # Faster without generator

or

sum = 0
for i in xrange(len(u)):
    sum += (u[i]-v[i])**2

which turn out to be significant (at least twice) slower than the first version. Is there any smart way to optimize , without resorting to NumPy / SciPy? . I know that these packages offer the fastest way to do such things, but at the moment I'm trying more to get the experience of optimizing "bare Python". What I found works fast is to dynamically build a string that defines the function and exec(), but this is really the last resort, I would say ...

Requirements:

  • CPython 2.7
  • Standard library only
  • "Real" (e.g. not exec()), pure Python

Although my question concerns the question of small operations in general, you can assume in your decision that one of the vectors remains the same over several function calls.

+5
2

, , , . , . , u v, return .

def test1(u, v):
    return (u[0]-v[0])**2 + (u[1]-v[1])**2 + (u[3]-v[3])**2

dis.dis(test1)
 0 LOAD_FAST                0 (u)
 3 LOAD_CONST               1 (0)
 6 BINARY_SUBSCR       
 7 LOAD_FAST                1 (v)
10 LOAD_CONST               1 (0)
13 BINARY_SUBSCR       
14 BINARY_SUBTRACT     
15 LOAD_CONST               2 (2)
18 BINARY_POWER        
19 LOAD_FAST                0 (u)
22 LOAD_CONST               3 (1)
25 BINARY_SUBSCR       
26 LOAD_FAST                1 (v)
29 LOAD_CONST               3 (1)
32 BINARY_SUBSCR       
33 BINARY_SUBTRACT     
34 LOAD_CONST               2 (2)
37 BINARY_POWER        
38 BINARY_ADD          
39 LOAD_FAST                0 (u)
42 LOAD_CONST               4 (3)
45 BINARY_SUBSCR       
46 LOAD_FAST                1 (v)
49 LOAD_CONST               4 (3)
52 BINARY_SUBSCR       
53 BINARY_SUBTRACT     
54 LOAD_CONST               2 (2)
57 BINARY_POWER        
58 BINARY_ADD          
59 RETURN_VALUE

3, . , , .

def test2(u, v):
    sum((a-b)**2 for a, b in izip(u, v))

dis.dis(test2)
 0 LOAD_GLOBAL              0 (sum)
 3 LOAD_CONST               1 (<code object <genexpr> at 02C6F458, file "<pyshell#10>", line 2>)
 6 MAKE_FUNCTION            0
 9 LOAD_GLOBAL              1 (izip)
12 LOAD_FAST                0 (u)
15 LOAD_FAST                1 (v)
18 CALL_FUNCTION            2
21 GET_ITER            
22 CALL_FUNCTION            1
25 CALL_FUNCTION            1
28 RETURN_VALUE

, , , , 2 globals (sum izip, , , , , , _izip _sum), 4 - , izip, , , sum ( ).

def test3(u, v):
    sum = 0
    for i in xrange(len(u)):
        sum += (u[i]-v[i])**2

dis.dis(test3)
 0 LOAD_CONST               1 (0)
 3 STORE_FAST               2 (sum)

 6 SETUP_LOOP              52 (to 61)
 9 LOAD_GLOBAL              0 (xrange)
12 LOAD_GLOBAL              1 (len)
15 LOAD_FAST                0 (u)
18 CALL_FUNCTION            1
21 CALL_FUNCTION            1
24 GET_ITER            
25 FOR_ITER                32 (to 60)
28 STORE_FAST               3 (i)

31 LOAD_FAST                2 (sum)
34 LOAD_FAST                0 (u)
37 LOAD_FAST                3 (i)
40 BINARY_SUBSCR       
41 LOAD_FAST                1 (v)
44 LOAD_FAST                3 (i)
47 BINARY_SUBSCR       
48 BINARY_SUBTRACT     
49 LOAD_CONST               2 (2)
52 BINARY_POWER        
53 INPLACE_ADD         
54 STORE_FAST               2 (sum)
57 JUMP_ABSOLUTE           25
60 POP_BLOCK           
61 LOAD_CONST               0 (None)
64 RETURN_VALUE

, , , test2. , , xrange(len(u)) , @Lucas Malor.

def test4(u, v):
    mysum = 0
    for a, b in izip(u, v) :
        mysum += (a-b)**2
    return mysum

dis.dis(test4)
 0 LOAD_CONST               1 (0)
 3 STORE_FAST               2 (mysum)

 6 SETUP_LOOP              47 (to 56)
 9 LOAD_GLOBAL              0 (izip)
12 LOAD_FAST                0 (u)
15 LOAD_FAST                1 (v)
18 CALL_FUNCTION            2
21 GET_ITER            
22 FOR_ITER                30 (to 55)
25 UNPACK_SEQUENCE          2
28 STORE_FAST               3 (a)
31 STORE_FAST               4 (b)

34 LOAD_FAST                2 (mysum)
37 LOAD_FAST                3 (a)
40 LOAD_FAST                4 (b)
43 BINARY_SUBTRACT     
44 LOAD_CONST               2 (2)
47 BINARY_POWER        
48 INPLACE_ADD         
49 STORE_FAST               2 (mysum)
52 JUMP_ABSOLUTE           22
55 POP_BLOCK           

56 LOAD_FAST                2 (mysum)
59 RETURN_VALUE

@Lucas Malor, . , 1. , , , .

, eval , , test1, , . , , u v ( , ), , , , , u v , . ( gc).

, , python, , . "" test2.

+1
mysum = 0
for a, b in izip(u, v) :
    mysum += (a-b)**2

35% , # 3

PS: Cython ( CPython) Shedskin?

+2

More articles:


All Articles