Scala:排序子集最合适的数据结构是什么_编程设计

给定一个 T 类型元素的大集合(我们称之为“a”)(比如一个向量或列表)和一个评估函数“f”(比如，(T)=> Double)我想从 'a ' 结果集合 'b' 包含导致 f 下最高值的 'a' 的 N 个元素。集合“a”可能包含重复项。它没有排序。

也许将并行性(映射/减少等)问题暂时搁置一旁，用于编译结果集合“b”的合适 Scala 数据结构是什么？感谢您的任何指示/想法。

笔记:

(1) 我想我的用例可以最简洁地表示为

val a = Vector( 9,2,6,1,7,5,2,6,9 ) // just an example 
val f : (Int)=>Double = (n)=>n      // evaluation function 
val b = a.sortBy( f ).take( N )     // sort, then clip

除了我不想对整个集合进行排序。

(2) 一个选项可能是对“a”的迭代，它用“手动”大小边界填充 TreeSet(拒绝比集合中最差项目更糟糕的任何东西，不要让集合增长超过 N)。但是，我想在结果集中保留原始集中存在的重复项，因此这可能不起作用。

(3) 如果排序的多集是正确的数据结构，是否有 Scala 实现？或者二进制排序的向量或数组，如果结果集相当小？

请您参考如下方法:

您可以使用优先队列:

def firstK[A](xs: Seq[A], k: Int)(implicit ord: Ordering[A]) = { 
  val q = new scala.collection.mutable.PriorityQueue[A]()(ord.reverse) 
  val (before, after) = xs.splitAt(k) 
  q ++= before 
  after.foreach(x => q += ord.max(x, q.dequeue)) 
  q.dequeueAll 
}

我们用第一个 k 填充队列元素，然后将每个附加元素与队列的头部进行比较，并根据需要进行交换。这按预期工作并保留重复项:

scala> firstK(Vector(9, 2, 6, 1, 7, 5, 2, 6, 9), 4) 
res14: scala.collection.mutable.Buffer[Int] = ArrayBuffer(6, 7, 9, 9)

它不会对完整列表进行排序。我有一个 Ordering在此实现中，但将其调整为使用评估函数将非常简单。