Script time improvement
I am trying to improve the efficiency of a part of my script, but I have no more idea. I ran the following script in Matlab and Python, but the Matlab implementation is four times faster than Python. Any idea how to improve?
Python
import time
import numpy as np
def ComputeGradient(X, y, theta, alpha):
m = len(y)
factor = alpha / m
h = np.dot(X, theta)
theta = [theta[i] - factor * sum((h-y) * X[:,i]) for i in [0,1]]
#Also tried this but with worse performances
#diff = np.tile((h-y)[:, np.newaxis],2)
#theta = theta - factor * sum(diff * X)
return theta
if __name__ == '__main__':
data = np.loadtxt("data_LinReg.txt", delimiter=',')
theta = [0, 0]
alpha = 0.01
X = data[:,0]
y = data[:,1]
X = np.column_stack((np.ones(len(y)), X))
start_time = time.time()
for i in range(0, 1500, 1):
theta = ComputeGradient(X, y, theta, alpha)
stop_time = time.time()
print("--- %s seconds ---" % (stop_time - start_time))
-> 0.048 s
Matlab
data = load('data_LinReg.txt');
X = data(:, 1); y = data(:, 2);
m = length(y);
X = [ones(m, 1), data(:,1)]; % Add a column of ones to x
theta = zeros(2, 1);
iterations = 1500;
alpha = 0.01;
tic
for i = 1:1500
theta = gradientDescent(X, y, theta, alpha);
end
toc
function theta = gradientDescent(X, y, theta, alpha)
m = length(y); % number of training examples
h = X * theta;
t1 = theta(1) - alpha * sum(X(:,1).*(h-y)) / m;
t2 = theta(2) - alpha * sum(X(:,2).*(h-y)) / m;
theta = [t1; t2];
end
-> 0.01 s
[EDIT] : avenue's solution
One possible possibility is to use numpy vectorization instead of python root functions. In the proposed code, replacing sum
with np.sum
improves the time efficiency so that it is closer to Matlab (0.019s instead of 0.048s)
Also, I've separately tested the functions on vectors: np.dot, np.sum, * (product), and all of these functions seem to be faster (faster anyway) than the Matlab equivalents. I wonder why it is even slower in Python ....
source to share
This solution is an optimized MATLAB implementation that does -
- Integration in style
gradient-descent
. - Pre-computation of specific values that are reused within the loop.
Code -
data = load('data_LinReg.txt'); iterations = 1500; alpha = 0.01; m = size(data,1); M = alpha/m; %// scaling factor %// Pre-compute certain values that are repeatedly used inside the loop sum_a = M*sum(data(:,1)); sum_p = M*sum(data(:,2)); sum_ap = M*sum(data(:,1).*data(:,2)); sum_sqa = M*sum(data(:,1).^2); one_minus_alpha = 1 - alpha; one_minus_sum_sqa = 1 - sum_sqa; %// Start processing t1n0 = 0; t2n0 = 0; for i = 1:iterations temp = t1n0*one_minus_alpha - t2n0*sum_a + sum_p; t2n0 = t2n0*one_minus_sum_sqa - t1n0*sum_a + sum_ap; t1n0 = temp; end theta = [t1n0;t2n0];
Quick tests show that this greatly improves the MATLAB code posted in the question.
Now I am not very familiar with python, but I would assume that this MATLAB code can be easily ported to python.
source to share