Improving excution time for list and sampling in Python

Question

Here is my code for generating edge list based on Price model algorithm. I think there have two points to reduce execution time:

1. use proper data type
2. use faster random sampling

Originally, I used list instead of NumPy array and then changed from extending array till c x n to setting initial fixed array (and change the initial values).

It made execution time faster but still way slower than same implementation written in Matlab.

import pickle
from random import random, sample
import numpy as np


def gen_edge_list(a, c, n):
    """
    Generate edge list based on 14.1.1
    """
    edge_list = np.zeros(c*n)
    p = float(c) / (float(c)+a) # % for preferential attachment edges
    edge_list[0] = 1            # edge from vertex 2 to 1
    idx = 1                     # point to the next index
    for t in range(3, n+1):
        if t <= c+1:
            """
            If network size is smaller than c+1,
            connect among all vertices.
            """
            edge_list[idx:idx+t-1] = [i for i in range(1, t)]
            idx = idx+t-1
        else:
            """
            decide preferential attachment or uniformly random attachment
            by given p
            """
            n_pref = len([True for i in range(c) if random() < p])
            edge_list[idx:idx+n_pref] = sample(edge_list[0:idx-1], n_pref)
            idx += n_pref
            edge_list[idx:idx+c-n_pref] = sample(range(1, t+1), c-n_pref)
            idx = idx + c - n_pref


if __name__ == "__main__":
    a = [1.5]
    c = [3]
    n = 10**6
    edge_lists = []
    for i in range(len(a)):
        edge_lists.append(gen_edge_list(a[i], c[i], n))
    output = open('edge_list.pkl', 'wb')
    pickle.dump(edge_lists, output)
    output.close()

My biggest concern is especially the following:

        """
        decide preferential attachment or uniformly random attachment
        by given p
        """
        n_pref = len([True for i in range(c) if random() < p])
        edge_list[idx:idx+n_pref] = sample(edge_list[0:idx-1], n_pref)
        idx += n_pref
        edge_list[idx:idx+c-n_pref] = sample(range(1, t+1), c-n_pref)
        idx = idx + c - n_pref

Here is my friends code written in Matlab:

a = [1.5];
c = [3];
n = 1^6;
edgelist = cell(numel(c),1);
for i = 1:numel(c)
    p = c(i)./(c(i)+a(i));
    edgelist{i} = zeros(1, c(i).*n);
    edgelist{i}(1) = 1;
    idx = 2;
    for t = 3:n
        if t <= c(i)+1
            edgelist{i}(idx:(idx+t-2)) = 1:(t-1);
            idx = idx+t-1;
        else
            pref_or_rand = rand(1,c(i)) < p;  
            prefn = sum(pref_or_rand);      
            edgelist{i}(idx:(idx+c(i)-1)) = [edgelist{i}(randi(idx-1,1,prefn)) randi(t,1,c(i)-prefn)];
            idx = idx+c(i);
        end
    end
end

I don't know what makes this huge difference on execution time between them. (40 sec in Matlab on mac book pro vs 40 min with Python code in recent i5 machine on Debian)

If you have any idea, please let me know.

Answer 1

I have changed sampling part and it took only 19 sec. I have realized that numpy's random sampling is way faster than python's built-in random sampling.

import pickle
import numpy as np
from numpy.random import randint, rand, choice


def gen_edge_list(a, c, n):
    """
    Generate edge list based on 14.1.1
    """
    edge_list = np.zeros(c*n)
    p = float(c) / (float(c)+a) # % for preferential attachment edges
    edge_list[0] = 1            # edge from vertex 2 to 1
    idx = 1                     # point to the next index
    for t in range(3, n+1):
        print t
        if t <= c+1:
            """
            If network size is smaller than c+1,
            connect among all vertices.
            """
            edge_list[idx:idx+t-1] = [i for i in range(1, t)]
            idx = idx+t-1
        else:
            """
            decide preferential attachment or uniformly random attachment
            by given p
            """
            n_pref = np.sum(rand(c) < p)
            edge_list[idx:idx+n_pref] = choice(edge_list[0:idx-1], n_pref)
            idx += n_pref
            edge_list[idx:idx+c-n_pref] = randint(1, t+1, c-n_pref)
            idx = idx + c - n_pref

Answer 2

Some more suggestions on your latest version:

1. Assigning a numpy array to a numpy array is faster than assigning a list to a numpy array. So edge_list[idx:idx+t-1] = np.arange(1, t) is faster than edge_list[idx:idx+t-1] = [i for i in range(1, t)].
2. It is a little faster, and in my opinion cleaner, to use foo.sum() for numpy arrays instead of np.sum(foo) (or in your case (foo < bar).sum() versus np.sum(foo < bar).
3. You can use in-place operations more. So idx += t-1 instead of idx = idx+t-1.
4. In my opinion it would be cleaner to have two loops, one for t <= c+1, the other for t > c+1. This will save you an indentation level, and a comparison per loop.
5. You add, then immediately remove, n_pref from idx. This seems redundant. I would use another variable there.
6. You re-do some of the math several times. I think it would be better to switch variables around.
7. You can tell what all the idx values will be ahead of time, so you can pre-compute them.
8. You can pre-compute the range and re-use it.