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