# Looking for efficient python program for this following python script

I am looking for a memory efficient python script for the following script. The following script works well for smaller dimension but the dimension of the matrix is 5000X5000 in my actual calculation. Therefore, it takes very long time to finish it. Can anyone help me how can I do that?

def check(v1,v2):
if len(v1)!=len(v2):
raise ValueError,"the lenght of both arrays must be the same"
pass
def d0(v1, v2):
check(v1, v2)
return dot(v1, v2)
import numpy as np
from pylab import *
vector=[[0.1, .32, .2, 0.4, 0.8], [.23, .18, .56, .61, .12], [.9, .3, .6, .5, .3], [.34, .75, .91, .19, .21]]
rav= np.mean(vector,axis=0)
#print rav
#print vector
m= vector-rav
corr_matrix=[]
for i in range(0,len(vector)):
tmp=[]
x=sqrt(d0(m[i],m[i]))
for j in range(0,len(vector)):
y=sqrt(d0(m[j],m[j]))
z=d0(m[i],m[j])
w=z/(x*y)
tmp.append(w)
corr_matrix.append(tmp)
print corr_matrix

-
"... memory efficient ... very long time ..." Do you want to optimize memory usage or runtime? –  mnhg Feb 6 '13 at 12:27
I am looking for both. –  user21858 Feb 6 '13 at 18:24

I noticed one of your issues is that you are calculating the same thing over and over again when it is possible to pre-calculate the values before looping. First of all:

x = sqrt(d0(m[i], m[i]))


and:

y = sqrt(d0(m[j], m[j]))


are doing the exact same thing. You are calculating the sqrt() of dot product of the entire length of the vector length^2 times! For your 5000 element vector list, that's 25,000,000 times.

When it comes to iterating over giant mounds of data, try to pre-calculate as much as possible. Try this:

pre_sqrt = [sqrt(d0(elem, elem)) for elem in m]
pre_d0 = [d0(i, j) for i in m for j in m]


Then, to reduce the amount of repetitive calls to len() and range():

vectorLength = len(vector)
iterRange = range(vectorLength)


Finally, this is how your for loops should look:

for i in iterRange:

tmp = []
x = pre_sqrt[i]

for j in iterRange:

y = pre_sqrt[j]
z = pre_d0[i*vectorLength + j]

w = z / (x * y)

tmp.append(w)

corr_matrix.append(tmp)


When I timed your implementation vs mine these were the average speeds over 10000 repetitions:

Old: .150 ms

Mine: .021 ms

That's about a 7 fold increase over your small sample vector. I imagine the speed increase will be even better when you enter the 5000 element vector.

You should also be aware that there could be some Python specific improvements to be made. For example, using lists vs numpy arrays to store large amounts of data. Perhaps someone else can elaborate further on those types of speed increases.

-

Use a profiler to know your hot spots: http://docs.python.org/2/library/profile.html

Describe your algorithm. It is not directly clear what should happen in this loop. If you abstract the algorithm inside a specification, you can perhaps simplify the abstract specification to get a better algorithm.

Correlates to the previous one: Use meaningful names.
For example:

vector=[[0.1, .32, .2, 0.4, 0.8], [.23, .18, .56, .61, .12], [.9, .3, .6, .5, .3], [.34, .75, .91, .19, .21]]


Sure, this is a vector for a vector space over a R^5 field, but you could call it a matrix and everyone can follow it.

def check(v1,v2):
if len(v1)!=len(v2):
raise ValueError,"the lenght of both arrays must be the same"


What does it check? (And i think, you do not need it. Because dot from numpy will already raise an error for illegal arguments)

def d0(v1, v2):
check(v1, v2)
return dot(v1, v2)


What is d0? Call it get_inner_product or something like this (I even do not like the numpy name, but well)

and some more

from pylab import *

Try to avoid import everything. This will lead to problems, sometimes hard to read code and namespace problems.

-