scipy/scipy — pull request #2815 by larsmans (2013-09-01 12:17:09+00:00)
Title: ENH: more scalable sqeuclidean in spatial.distance

Memory complexity down to O(1) additional space instead of O(n), assuming a smart implementation of `np.dot`.

Timings of old version, new version and the obvious alternative, with two random vectors of length 1000:
```
>>> %timeit ((u - v) ** 2).sum()
100000 loops, best of 3: 13.9 us per loop
>>> %timeit np.dot(u, u) + np.dot(v, v) - 2 * np.dot(v, v)
100000 loops, best of 3: 8.97 us per loop
>>> %timeit u_v = u - v; np.dot(u_v, u_v)
100000 loops, best of 3: 7.55 us per loop
```

Length 10000:
```
>>> %timeit ((u - v) ** 2).sum()
10000 loops, best of 3: 70.2 us per loop
>>> %timeit np.dot(u, u) + np.dot(v, v) - 2 * np.dot(v, v)
10000 loops, best of 3: 39.9 us per loop
>>> %timeit u_v = u - v; np.dot(u_v, u_v)
10000 loops, best of 3: 39 us per loop
```

Length 100000:
```
>>> %timeit ((u - v) ** 2).sum()
1000 loops, best of 3: 1.93 ms per loop
>>> %timeit np.dot(u, u) + np.dot(v, v) - 2 * np.dot(v, v)
1000 loops, best of 3: 356 us per loop
>>> %timeit u_v = u - v; np.dot(u_v, u_v)
1000 loops, best of 3: 577 us per loop
```

Vectors generated with `np.random.randn`; NumPy 1.6.2 linked against ATLAS 3.8.4.