algorithm - Scala 中最快的加权随机算法？

Question

我正在为基于 Scala 的项目编写服务器端模块，我需要找到在某些 Int 权重之间执行加权随机数生成的最快方法。该方法应该尽可能快，因为它会被经常调用。

现在，这就是我想出的:

import scala.util.Random

trait CumulativeDensity {

  /** Returns the index result of a binary search to find @n in the discrete
    * @cdf array.
    */
  def search(n: Int, cdf: Array[Int]): Int = {
    val i: Int = cdf.indexWhere(_ != 0)
    if (i<0 | n<=cdf(i))
      i
    else
      search(n-cdf(i), {cdf.update(i,0); cdf})
  }

  /** Returns the cumulative density function (CDF) of @list (in simple terms,
    * the cumulative sums of the weights).
    */
  def cdf(list: Array[Int]) = list.map{
    var s = 0;
    d => {s += d; s}
  }
}

然后我用这段代码定义了 main 方法:

def rndWeighted(list: Array[Int]): Int =
  search(Random.nextInt(list.sum + 1), cdf(list))

但是，它仍然不够快。是否有任何类型的黑魔法使得从列表开始就无需对其进行迭代(库、内置函数、启发式算法)？

编辑:这是代码的最终版本(现在快多了):

def search(n: Int, cdf: Array[Int]): Int = {
  if (n > cdf.head)
    1 + search(n-cdf.head, cdf.tail)
  else
    0
}

Answer 1

而不是 cdf.update(i,0) 并将整个 cdf 传递回 cdf.indexWhere(_ != 0)在下一个递归调用中，考虑

cdf.splitAt(i)

并且只传递 i 的右边的元素，所以在下面的递归中，indexWhere 扫描一个较小的数组。请注意，数组大小在每次递归调用时单调递减以确保终止。