I have implemented for learning purposes a simple K-Means clustering algorithm in Rust. For those who are not familiar: you are given N points, say in the plane, and you want to group them in n clusters of nearby points.
To do so, you start with n random points, for instance the first n of the given ones. Call these centroids. At each iteration:
- you group the
Npoints based on the nearest centroid - you produce a new set of centroids as the average of the groups of the preceding step
You can stop after a fixed number of iterations, or after some convergence.
Here is my implementation, with the help of SO. For some reasons, the code runs slower than an equivalent algorithm written in Scala. I think I might be introducing some unnecessary copying or other hidden overhead, but I am not familiar enough with Rust to tell.
Just to be clear: I am not interested in changing algorithm (I want to compare apples to apples), and I would rather have idiomatic Rust than hyper-optimized code.
use std::collections::TreeMap;
use point::Point;
fn dist(v: Point, w: Point) -> f64 { (v - w).norm() }
fn avg(points: & Vec<Point>) -> Point {
let Point(x, y) = points.iter().fold(Point(0.0, 0.0), |p, &q| p + q);
let k = points.len() as f64;
Point(x / k, y / k)
}
fn closest(x: Point, ys: & Vec<Point>) -> Point {
let y0 = ys[0];
let d0 = dist(y0, x);
let (_, y) = ys.iter().fold((d0, y0),
|(m, p), &q| {
let d = dist(q, x);
if d < m { (d, q) } else { (m, p) }
}
);
y
}
fn clusters(xs: & Vec<Point>, centroids: & Vec<Point>) -> Vec<Vec<Point>> {
let mut groups: TreeMap<Point, Vec<Point>> = TreeMap::new();
for x in xs.iter() {
let y = closest(*x, centroids);
let should_insert = match groups.find_mut(&y) {
Some(val) => {
val.push(*x);
false
},
None => true
};
if should_insert {
groups.insert(y, vec![*x]);
}
}
groups.into_iter().map(|(_, v)| v).collect::<Vec<Vec<Point>>>()
}
pub fn run(points: & Vec<Point>, n: uint, iters: uint) -> Vec<Vec<Point>> {
let mut centroids: Vec<Point> = Vec::from_fn(n, |i| points[i]);
for _ in range(0, iters) {
centroids = clusters(points, & centroids).iter().map(|g| avg(g)).collect();
}
clusters(points, & centroids)
}
Definition of Point:
use serialize::{Decoder, Decodable};
#[deriving(Show, PartialEq, PartialOrd, Clone)]
pub struct Point(pub f64, pub f64);
fn sq(x: f64) -> f64 { x * x }
impl Point {
pub fn norm(self: &Point) -> f64 {
let Point(x, y) = *self;
(sq(x) + sq(y)).sqrt()
}
}
impl<E, D: Decoder<E>> Decodable<D, E> for Point {
fn decode(d: &mut D) -> Result<Point, E> {
d.read_tuple(|d, n| {
if n != 2 { Err(d.error("invalid number of elements, need 2")) }
else {
d.read_tuple_arg(0, |d| d.read_f64()).and_then(|e1|
d.read_tuple_arg(1, |d| d.read_f64()).map(|e2|
Point(e1, e2)
)
)
}
})
}
}
impl Add<Point, Point> for Point {
fn add(&self, other: &Point) -> Point {
let &Point(a, b) = self;
let &Point(c, d) = other;
Point(a + c, b + d)
}
}
impl Sub<Point, Point> for Point {
fn sub(&self, other: &Point) -> Point {
let &Point(a, b) = self;
let &Point(c, d) = other;
Point(a - c, b - d)
}
}
impl Eq for Point {}
impl Ord for Point {
fn cmp(&self, other: &Point) -> Ordering {
self.partial_cmp(other).unwrap_or(Equal)
}
}
Is there anything that I am doing that justifies the unexpected slowness?
rustc -O,cargo --release)? \$\endgroup\$