让这个坐标类与欧几里得距离配合使用，
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%的时间都在计算距离（使用分析工具找到原因！）
最后，你可以使用索引结构。对于欧几里德距离，你可能有最大的选择来加速查找最近邻居。有k-d树，但我发现R树通常更快。如果你想试一试这些，我建议使用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
这取决于是使用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）是一个C++库，具有Python绑定，用于搜索与给定查询点接近的空间点。它还创建了大型的只读文件数据结构，这些数据会被映射到内存中，以便许多进程可以共享相同的数据。
看一下this repo。
def distSquare(c: coord) = Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2)作为度量方式。这基本上可以避免每次计算.sqrt。 - artur grzesiaktop方法可以实现您想要的功能。也许您可以重新利用该源代码？https://spark.apache.org/docs/0.8.1/api/core/org/apache/spark/rdd/RDD.html - The Archetypal Paul