CODEWITHSUNDEEP
pythonmatlab
GuillaumeA
GuillaumeA

Reputation: 3545

Script time improvement

I'm trying to improve time efficiency of part of my script but I don't have any more idea. I ran following script in either Matlab and Python but Matlab implementation is four times quicker than Python 's one. 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.048s

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.01s

[EDIT] : solution avenue

One possible avenue is to use numpy vectorization instead of python root functions. In the proposed code, replacing sum by np.sum improves the time efficiency so that it is closer to Matlab (0.019s instead of 0.048s)

Furthermore, I tested separately the functions on vectors : np.dot, np.sum, * (product) and all these functions seems to be faster (really faster in some case) than the equivalent Matlab. I wonder then why it is still slower in Python....

Upvotes: 3

Views: 121

Answers (2)

Divakar
Divakar

Reputation: 221504

This solution presents an optimized MATLAB implementation that does -

  • Funtion-inlining of the gradient-descent implementation.
  • Pre-computation of certain values that are repeatedly used inside 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 presents an appreciable speedup over the MATLAB code posted in the question.

Now, I am not too familiar with python, but I would assume that this MATLAB code could be easily ported to python.

Upvotes: 1

AnonSubmitter85
AnonSubmitter85

Reputation: 933

I don't know how much of a difference it will make, but you can simplify your function with something like:

s = alpha / size(X,1);
gradientDescent = @(theta)( theta - s * X' * (X*theta - y) );

Since you need theta_{i} in order to find theta_{i+1}, I don't see any way to avoid the loop.

Upvotes: 0

Related Questions