Scala中的有效近邻搜索

Question

让这个坐标类和欧几里德距离，

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)。

是否有办法使这些计算更有时间效率，特别是在网格有一百万点的情况下？

Answer 1

我不确定这是否有用(甚至是愚蠢的)，但我想到了这一点：

使用排序函数对网格中的所有元素进行排序，然后选择第一个k元素。如果考虑像递归合并排序这样的排序算法，则有如下所示：

1. 分拆收集
2. 在两半上恢复
3. 合并两个排序的半部

也许您可以根据您的需要优化这样的功能。合并部分通常合并来自两部分的所有元素，但您只对合并产生的第一个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)
}

Answer 2

Profile您的代码，看看什么是昂贵的。

你的排序方式已经非常低效了。

不会一直重新计算距离。这不是免费的--很可能你的程序在计算距离上花费了99%的时间(使用分析器来找出答案！)

最后，您可以使用使用索引结构。对于欧几里德距离，你可能有最大的选择指数，以加快寻找最近的邻居。有k-d树，但我发现R-树更快。如果您想玩这些游戏，我推荐埃尔基。它是一个用于数据挖掘的Java库(因此它也应该易于从Scala中使用)，而且它有大量的索引结构可供选择。

Answer 3

做这件事很有趣。

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