Summing over pair of indices (or more) in Python
For the MD example you give, it can be exploited by sorting, You can achieve O(N*Log(N)) instead of O(N^2)
y = [2,3,2,34]def slow(y): tot = 0 for i in range(len(y)): for j in range(len(y)): if i != j: tot += abs(y[i] - y[j]) return float(tot)/len(y)**2print slow(y)def fast(y): sorted_y = sorted(y) tot = 0 for i, yi in enumerate(sorted_y): smaller = i bigger = len(y) - i - 1 tot += smaller * yi - bigger * yi return float(2*tot)/len(y)**2print fast(y)Often you will have to use dynamic programming or other techniques to make these faster, I'm not sure if there is a "one method fits all" solution.