# Improving excution time for list and sampling in Python

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.

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


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.
• You are right. np.arange(1, t) must be faster and make it consistent. – sangheestyle May 6 '16 at 20:12