Scala PriorityQueue on Array[Int] 具有复杂比较函数的性能问题（需要缓存）

Question

该问题涉及 Scala PriorityQueue[Array[Int]] 在大数据集上的性能。需要进行以下操作：入队、出队和过滤。目前，我的实现如下：

对于 Array[Int] 类型的每个元素，都有一个复杂的求值函数：（我不知道如何以更有效的方式编写它，因为它排除了位置 0

def eval_fun(a : Array[Int]) =
  if(a.size < 2) 3
  else {
    var ret = 0
    var i = 1
    while(i < a.size) {
      if((a(i) & 0x3) == 1) ret += 1
      else if((a(i) & 0x3) == 3) ret += 3
      i += 1
    }
    ret / a.size
  }

）带有比较函数的是基于评估函数：（反向，降序）

val arr_ord = new Ordering[Array[Int]] {
  def compare(a : Array[Int], b : Array[Int]) = eval_fun(b) compare eval_fun(a) }

PriorityQueue 定义为：

val pq: scala.collection.mutable.PriorityQueue[Array[Int]] = PriorityQueue()

问题：

1. 是否有更优雅、更高效的方式来编写这样的评估函数？我正在考虑使用fold，但是fold不能排除位置0。
2. 是否有数据结构可以生成具有唯一元素的优先级队列？在每个入队操作之后应用过滤操作效率不高。
3. 有没有缓存方法来减少评估计算？因为当向队列中添加新元素时，每个元素可能需要再次使用 eval_fun 进行评估，如果每个元素的评估值都可以缓存，则不需要这样做。另外，我应该提到两个不同的元素可能具有相同的评估值。
4. 是否有更有效的数据结构而不使用泛型类型？因为如果elements的大小达到10000，size的大小达到1000，性能就慢得要命。

感谢您。

Answer 1

(1) 如果你想在这里获得最大的性能，我会坚持使用 while 循环，即使它不是非常优雅。否则，如果您在数组上使用view，则可以轻松地在进入fold之前删除第一个元素：

a.view.drop(1).foldLeft(0)( (sum, a) => sum + ((a & 0x03) match {
   case 0x01 => 1
   case 0x03 => 3
   case _    => 0
})) / a.size

(2) 您可以维护两个结构，优先级队列，和一套。两者结合起来会给你一个排序集......所以你可以使用collection.immutable.SortedSet，但标准库中没有可变变体。是否想要基于优先级函数或实际数组内容进行相等？因为在后一种情况下，您将无法为每次插入逐个元素地比较数组，从而取消缓存优先级函数值的效果。

(3) 只需将计算出的优先级与数组一起放入队列即可。 IE

implicit val ord = Ordering.by[(Int, Array[Int]), Int](_._1)
val pq = new collection.mutable.PriorityQueue[(Int, Array[Int])]
pq += eval_fun(a) -> a

Answer 2

好吧，您可以使用尾递归循环（通常这些更“惯用”：

def eval(a: Array[Int]): Int =
  if (a.size < 2) 3
  else {
    @annotation.tailrec
    def loop(ret: Int = 0, i: Int = 1): Int =
      if (i >= a.size) ret / a.size
      else {
        val mod3 = (a(i) & 0x3)
        if (mod3 == 1) loop(ret + 1, i + 1)
        else if (mod3 == 3) loop(ret + 3, i + 1)
        else loop(ret, i + 1)
      }
    loop()
  }

然后您可以使用它来初始化缓存的优先级值：

case class PriorityArray(a: Array[Int]) {
  lazy val priority = if (a.size < 2) 3 else {
    @annotation.tailrec
    def loop(ret: Int = 0, i: Int = 1): Int =
      if (i >= a.size) ret / a.size
      else {
        val mod3 = (a(i) & 0x3)
        if (mod3 == 2) loop(ret, i + 1)
        else loop(ret + mod3, i + 1)
      }
    loop()
  }
}

您可能还注意到我删除了冗余的 & 操作并且只有单个条件（对于当它等于 2 时，而不是对 1 && 3) 进行两次检查 – 这些应该会产生一些最小的影响，

但这与 0__ 刚刚提出的提案没有太大区别。

Answer 3

我的回答：

1. 如果评估很重要，就保持原样。您可能会通过递归获得更好的性能（不知道为什么，但它确实发生了），但是使用几乎任何其他方法肯定会获得更差的性能。

2. 不，没有，但是您只需修改出队操作就可以非常接近它：

   defdistinctDequeue[T](q: PriorityQueue[T]): T = {
   val 结果 = q.dequeue
   while (q.head == 结果) q.dequeue
   结果
   }

，您必须保留第二个数据结构来跟踪是否已添加元素。无论哪种方式，等号都相当重，但我建议在下一个项目中使其更快。

但请注意，这需要以其他方式解决成本函数上的关系。

1. 像 0__ 建议的那样，将成本放入优先级队列中。但是如果有帮助的话，您也可以在函数上保留缓存。我会尝试这样的事情：

   val evalMap = scala.collection.mutable.HashMapWrappedArray[Int], Int
   def eval_fun(a : 数组[Int]) =
   if(a.size < 2) 3
   否则 evalMap.getOrElseUpdate(a, {
   变量 ret = 0
   变量我 = 1
   while(i < a.size) {
   if((a(i) & 0x3) == 1) ret += 1
   否则 if((a(i) & 0x3) == 3) ret += 3
   我 += 1
   }
   ret / a.尺寸
   })

   导入scala.math.Ordering.Implicits._
   val pq = new collection.mutable.PriorityQueue[(Int, WrappedArray[Int])]
   pq += eval_fun(a) ->; (a : WrappedArray[Int])

请注意，我没有创建特殊的 Ordering ——我使用的是标准 Ordering，以便 WrappedArray > 将打破联系。包装 Array 的成本很低，并且您可以使用 .array 将其返回，但是，另一方面，您将得到以下结果：

1. Ties will通过比较数组本身来打破。如果成本方面没有太多关系，这应该足够了。如果有，请向元组中添加其他内容，以帮助打破平局，而无需比较数组。

2. 这意味着所有相等的元素将被保留在一起，这将使您能够同时将所有它们出列，给人一种只保留一个元素的印象。

3. 并且 equals 实际上会起作用，因为 WrappedArray 会像 Scala 序列一样进行比较。

我不明白你说的第四点是什么意思。