If K-Means really does the job and just seems slow, why not try to do it faster? The method I use is random-pause .
It usually happens that there are many opportunities for speeding up, in code that you would not consider a problem, without changing the underlying algorithm.
Here is an example.
source
share