scipy/scipy — pull request #3712 by richardtsai (2014-06-05 10:09:26+00:00)
Title: ENH: cluster: reimplement the update-step of K-means in Cython

The current implementation of update-step in `vq.kmeans` and `vq.kmeans2` is inefficient due to unnecessary copying and high cache-miss rate (I guess).

I calculate the sums of obs in each cluster first and then divide them by the numbers of obs. It should be more efficient. And the benchmark shows that the speedup seems to be significant for low dimensional data.

```
old: new:

30000 x 100, k = 10 30000 x 100, k = 10
--float64: 15504.6652ms --float64: 12687.4250ms
--float32: 6647.2686ms --float32: 5272.2000ms

10000 x 1, k = 3 10000 x 1, k = 3
--float64: 96.9102ms --float64: 41.6186ms
--float32: 99.7274ms --float32: 41.9904ms

100000 x 3, k = 4 100000 x 3, k = 4
--float64: 1396.6506ms --float64: 529.0992ms
--float32: 1028.3450ms --float32: 431.0248ms

10000 x 30, k = 10 10000 x 30, k = 10
--float64: 1164.1506ms --float64: 752.1930ms
--float32: 992.7966ms --float32: 658.1064ms

1000 x 3, k = 4 1000 x 3, k = 4
--float64: 30.8582ms --float64: 9.8542ms
--float32: 31.3026ms --float32: 12.4894ms
```