Scala：最适合排序子集的数据结构是什么？

Question

给定大量类型为T的元素（例如，向量或列表）和评估函数“ f”（例如，（T）=> Double）的集合（我们称其为“ a”），我想从“ a”中派生'结果集合'b'包含'a'的N个元素，这些元素导致f下的最大值。集合“ 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'的迭代，该迭代用'manual'的大小范围填充TreeSet（拒绝任何比集合中最差的项目还差的东西，不要让集合增长到N以上​​）。但是，我想保留结果集中原始集中存在的重复项，因此这可能行不通。

（3）如果排序的多集是正确的数据结构，是否有此的Scala实现？还是二进制排序的Vector或Array（如果结果集相当小）？

Answer 1

您可以使用优先级队列：

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在此实现中有一个，但是将其修改为使用评估函数将非常简单。