Golang中使用缓存加速K-Means聚类算法过程的实践。

package main

import (
    "fmt"
    "math"
    "math/rand"
    "sync"
    "time"
)

// Point represents a data point in K-Means algorithm
type Point struct {
    X, Y float64
    Group int
}

// Distance calculates the Euclidean distance between two points
func Distance(a, b Point) float64 {
    return math.Sqrt((a.X-b.X)*(a.X-b.X) + (a.Y-b.Y)*(a.Y-b.Y))
}

// KMeans performs K-Means clustering on a given dataset
func KMeans(points []Point, k int) []Point {
    clusters := make([]Point, k)
    copy(clusters, points[:k])

    cache := make(map[int]map[int]float64)
    var mutex sync.Mutex

    for {
        for i := range clusters {
            clusters[i].Group = i
        }

        for i := range points {
            minDist := math.MaxFloat64
            var group int

            // check cache
            if cachedDist, ok := cache[i]; ok {
                for j, dist := range cachedDist {
                    if dist < minDist {
                        minDist = dist
                        group = j
                    }
                }
            } else {
                cachedDist = make(map[int]float64)
                mutex.Lock()
                for j, c := range clusters {
                    dist := Distance(points[i], c)
                    cachedDist[j] = dist
                    if dist < minDist {
                        minDist = dist
                        group = j
                    }
                }
                cache[i] = cachedDist
                mutex.Unlock()
            }

            points[i].Group = group
        }

        changed := false
        for i := range clusters {
            sumX := 0.0
            sumY := 0.0
            count := 0

            for j := range points {
                if points[j].Group == i {
                    sumX += points[j].X
                    sumY += points[j].Y
                    count++
                }
            }

            if count > 0 {
                newX := sumX / float64(count)
                newY := sumY / float64(count)
                if clusters[i].X != newX || clusters[i].Y != newY {
                    changed = true
                    clusters[i].X = newX
                    clusters[i].Y = newY
                }
            }
        }

        if !changed {
            break
        }
    }

    return clusters
}

func main() {
    rand.Seed(time.Now().UnixNano())

    numPoints := 10000
    k := 4

    points := make([]Point, numPoints)
    for i := range points {
        points[i].X = rand.Float64() * 100
        points[i].Y = rand.Float64() * 100
    }

    start := time.Now()
    clusters := KMeans(points, k)
    elapsed := time.Since(start)

    fmt.Printf("%d data points clustered into %d groups in %s
", numPoints, k, elapsed)
}