让这个坐标类与欧几里得距离，
case class coord(x: Double, y: Double) {
def dist(c: coord) = Math.sqrt( Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2) )
}
并让坐标网格，例如
val grid = (1 to 25).map {_ => coord(Math.random*5, Math.random*5) }
然后对于任何给定的坐标
val x = coord(Math.random*5, Math.random*5)
最近的点x是
val nearest = grid.sortWith( (p,q) => p.dist(x) < q.dist(x) )
所以前三个最接近的是nearest.take(3)。
有没有办法让这些计算更省时，特别是对于有一百万点的网格的情况？
我不确定这是否有帮助（甚至是愚蠢的），但我想到了这一点：
您使用排序功能对网格中的所有元素进行排序，然后选择第一个k元素。如果您考虑像递归合并排序这样的排序算法，您会得到这样的结果：
也许您可以根据需要优化这样的功能。合并部分通常会合并两半的所有元素，但您只对k合并产生的第一个元素感兴趣。所以你只能合并直到你有k元素并忽略其余部分。
所以在最坏的情况下，其中k >= n（n是网格的大小）你仍然只有合并排序的复杂性。O(n log n)老实说，我无法确定此解决方案相对于k. （此刻太累了）
这是该解决方案的示例实现（绝对不是最佳的，也不是通用的）：
def minK(seq: IndexedSeq[coord], x: coord, k: Int) = {
val dist = (c: coord) => c.dist(x)
def sort(seq: IndexedSeq[coord]): IndexedSeq[coord] = seq.size match {
case 0 | 1 => seq
case size => {
val (left, right) = seq.splitAt(size / 2)
merge(sort(left), sort(right))
}
}
def merge(left: IndexedSeq[coord], right: IndexedSeq[coord]) = {
val leftF = left.lift
val rightF = right.lift
val builder = IndexedSeq.newBuilder[coord]
@tailrec
def loop(leftIndex: Int = 0, rightIndex: Int = 0): Unit = {
if (leftIndex + rightIndex < k) {
(leftF(leftIndex), rightF(rightIndex)) match {
case (Some(leftCoord), Some(rightCoord)) => {
if (dist(leftCoord) < dist(rightCoord)) {
builder += leftCoord
loop(leftIndex + 1, rightIndex)
} else {
builder += rightCoord
loop(leftIndex, rightIndex + 1)
}
}
case (Some(leftCoord), None) => {
builder += leftCoord
loop(leftIndex + 1, rightIndex)
}
case (None, Some(rightCoord)) => {
builder += rightCoord
loop(leftIndex, rightIndex + 1)
}
case _ =>
}
}
}
loop()
builder.result
}
sort(seq)
}
分析您的代码，看看什么是昂贵的。
您的排序方式已经非常低效。
不要一直重新计算距离。这不是免费的——你的程序很可能 99% 的时间都花在计算距离上（使用分析器来找出答案！）
最后，您可以使用索引结构。对于欧几里得距离，您可能拥有最大的索引选择来加速找到最近的邻居。有 kd-tree，但我发现 R-tree 通常更快。如果你想玩这些，我推荐ELKI。它是一个用于数据挖掘的 Java 库（因此它也应该很容易从 Scala 中使用），并且它有大量的索引结构可供选择。
这个做起来很有趣。
case class Coord(x: Double, y: Double) {
def dist(c: Coord) = Math.sqrt(Math.pow(x - c.x, 2) + Math.pow(y - c.y, 2))
}
class CoordOrdering(x: Coord) extends Ordering[Coord] {
def compare(a: Coord, b: Coord) = a.dist(x) compare b.dist(x)
}
def top[T](xs: Seq[T], n: Int)(implicit ord: Ordering[T]): Seq[T] = {
// xs is an ordered sequence of n elements. insert returns xs with e inserted
// if it is less than anything currently in the sequence (and in that case,
// the last element is dropped) otherwise returns an unmodifed sequence
def insert[T](xs: Seq[T], e: T)(implicit ord: Ordering[T]): Seq[T] = {
val (l, r) = xs.span(x => ord.lt(x, e))
(l ++ (e +: r)).take(n)
}
xs.drop(n).foldLeft(xs.take(n).sorted)(insert)
}
最低限度的测试。像这样称呼它：
val grid = (1 to 250000).map { _ => Coord(Math.random * 5, Math.random * 5) }
val x = Coord(Math.random * 5, Math.random * 5)
top(grid, 3)(new CoordOrdering(x))
编辑：很容易将其扩展到（预）计算距离一次
val zippedGrid = grid map {_.dist(x)} zip grid
object ZippedCoordOrdering extends Ordering[(Double, Coord)] {
def compare(a:(Double, Coord), b:(Double, Coord)) = a._1 compare b._1
}
top(zippedGrid,3)(ZippedCoordOrdering).unzip._2
这是一个利用 R-tree 数据结构的算法。对于所描述的小数据集没有用，但它可以很好地扩展到大量对象。
使用一个有序列表，其节点代表对象或 R-tree 边界框。使用您想要的任何距离函数，顺序最接近。保持插入顺序。
通过在 R 树的根节点中插入边界框来初始化列表。
要获取下一个最近的对象：
(1) 从列表中删除第一个元素。
(2) 如果它是一个对象，它是最近的一个。
(3) 如果是R-tree的非叶子节点的边界框，则将代表该节点子节点的所有边界框按照距离插入到列表中合适的位置。
(4) 如果是 R-tree 叶节点的边界框，则根据距离插入作为该节点子节点的对象（对象，而不是其边界框）。
(5) 回到步骤(1)。
该列表将仍然很短。前面是我们感兴趣的附近对象，列表中后面的节点将是表示更远对象集合的框。
这取决于是否exact或approximation。
正如http://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup等几个基准测试表明，在efficient.
我写ann4s的是Annoy的 Scala 实现
Annoy (Approximate Nearest Neighbors Oh Yeah) 是一个带有 Python 绑定的 C++ 库，用于搜索空间中靠近给定查询点的点。它还创建了基于文件的大型只读数据结构，这些数据结构映射到内存中，以便许多进程可以共享相同的数据。
看看这个回购。