scala - 粗略(或部分)排序 Scala 中的列表

Question

考虑一个包含数百万个对象的列表，例如:

case class Point(val name:String, val x:Double, val y:Double)

对于给定的点目标，我需要选择最接近目标的其他 10 个点。

val target = Point("myPoint", 34, 42)
val points = List(...) // list of several million points

def distance(p1: Point, p2: Point) = ??? // return the distance between two points

val closest10 = points.sortWith((a, b) => {
  distance(a, target) < distance(b, target)
}).take(10)

此方法有效但速度很慢。事实上，整个列表针对每个目标请求进行了详尽的排序，而在前 10 个最接近的点之后，我真的不关心任何排序。我什至不需要以正确的顺序返回最接近的前 10 个。

理想情况下，我会寻找一种“首先返回 10 并且不关注其余部分”的方法..

我能想到的朴素解决方案听起来像这样:按 1000 个桶排序，取第一个桶，按 100 个桶排序，取第一个桶，按 10 个桶排序，取第一个桶，完成。

问题是，我想这在 CS 中一定是一个非常普遍的问题，所以在基于这种天真的方法推出我自己的解决方案之前，我想知道任何最先进的方法来做到这一点，或者即使某些标准方法已经存在。

TL;DR 如何获取未排序列表的前 10 项，而无需对整个列表进行排序？

Answer 1

以下是改编自此 SO answer 的准系统方法用于从列表中选取 n 个最小整数(可以对其进行增强以处理更复杂的数据结构):

def nSmallest(n: Int, list: List[Int]): List[Int] = {
  def update(l: List[Int], e: Int): List[Int] =
    if (e < l.head) (e :: l.tail).sortWith(_ > _) else l

  list.drop(n).foldLeft( list.take(n).sortWith(_ > _) )( update(_, _) )
}

nSmallest( 5, List(3, 2, 8, 2, 9, 1, 5, 5, 9, 1, 7, 3, 4) )
// res1: List[Int] = List(3, 2, 2, 1, 1)

请注意输出是倒序的。