有没有办法让下面的算法更加高效？

Question

给定以下算法，如果随机输入值u小于（累积）prob向量中的某个预定义概率，则该算法返回预定义枚举中的值

val <- 1:5
prob <- c(1/3,1/30,2/15,7/30,4/15)
u <- runif(1)
if (u<prob[1]) 
  { 
    x=val[1]
  } else if(u<prob[1]+prob[2])
  {
    x=val[2]
  } else if(u<prob[1]+prob[2]+prob[3])
  {
    x=val[3]
  } else if (u<prob[1]+prob[2]+prob[3]+prob[4])
  {
    x=val[4]
  } else
      x=val[5]
  }

有没有办法让这一切变得更有效率？我不知道如何以不同的方式做到这一点。

Answer 1

另一种选择是使用findInterval. 例如

val <- 1:5
prob <- c(1/3,1/30,2/15,7/30,4/15)
u <- runif(1)
val[findInterval(u, cumsum(c(0, prob)))]

这也适用于任意数量的值

u <- runif(1000)
val[findInterval(u, cumsum(c(0, prob)))]

Answer 2

我不知道这是否是一个专门关于算法的问题问题，或者您是否想更快地解决问题。

\n

sample(val, size = 1, prob = prob)肯定会比你的解决方案更快，但我不知道内部算法是否从根本上比您的算法更好（例如，在操作计数方面）。

\n

查看C源代码，您可以看到该算法与您的算法类似，只是它预先计算累积概率以避免重复添加（并将元素排列为降序 \xe2\x80\x94 我认为\'s为了数值稳定性而不是效率）。

\n

（这是用于有替换的采样；无替换代码看起来非常相似，除了用于删除先前采样值的机制使其稍微复杂一些）

\n