Scala: какая структура данных наиболее подходит для отсортированных подмножеств?

Question

Учитывая большую коллекцию (назовем это 'a') элементов типа T (скажем, Vector или List) и функцию оценки 'f' (скажем, (T) => Double), которую я хотел бы вывестииз 'a' коллекция результатов 'b', которая содержит N элементов из 'a', что приводит к наибольшему значению в f.Коллекция «а» может содержать дубликаты.Он не отсортирован.

Может быть, на время оставить вопрос параллелизации (отобразить / уменьшить и т. Д.), Какой будет подходящая структура данных Scala для компиляции набора результатов «b»?Спасибо за любые указатели / идеи.

Примечания:

(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 такая реализация?Или отсортированный в двоичном виде вектор или массив, если результирующий набор достаточно мал?

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 в этой реализации, но адаптировать его для использования функции оценки было бы довольно тривиально.