algorithm – Scala中的高效最近邻搜索

您使用排序函数对网格中的所有元素进行排序,然后选择前k个元素.如果你考虑像递归合并排序这样的排序算法,你有这样的事情：

>拆分一半
>两个部分递归
>合并两个分类的一半

也许你可以根据自己的需要优化这样的功能.合并部分通常合并来自两半的所有元素,但您只对合并产生的第一个k感兴趣.所以你只能合并,直到你有k个元素并忽略其余元素.

所以在最坏的情况下,k> = n(n是网格的大小),你仍然只有merge-sort的复杂性. 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)
}