Here is my code for generating edge list based on Price model algorithm. I think there have two points to reduce execution time:use proper data typeuse faster random samplingOriginally, 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 picklefrom random import random, sampleimport numpy as npdef 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_prefif __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_prefHere 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    endendI 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.
Improving excution time for list and sampling in Python
python;performance;numpy;matlab
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 pickleimport numpy as npfrom numpy.random import randint, rand, choicedef 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