I am looking for a way to optimize the following code. It computes all the possible pairwise sums of the elements in an array:
import numpy as np
from itertools import combinations
N = 5000
a = np.random.rand(N)
c = ([a[i]+a[j] for i,j in combinations(range(N),2)])
This is relatively slow. I could get much better performances using the following:
b = a+a[:,None]
c = b[np.triu_indices(N,1)]
yet it still seems largely non-optimized: computing the full matrix b is inefficient because half of it ends up useless, and extracting its upper part (omitting the diagonal) is actually even slower than computing b.
Is there a way to do this faster? This makes me think of a similar problem, computing pairwise distances between points (Fastest pairwise distance metric in python) but I don't know if there is a way to do something similar here using scipy.
edit: I would like to keep the order of the sums, so that the result contains the sum of the indices in this order:
[(0,1), (0,2), ... (0,N-1), (1,2), .... (1,N-1), (2,3), ...],
i.e. the order you would get doing a double for loop for 0=<i<N, for j<i<N