Ruby - 从数组中随机选择一个元素，a[0]的概率为50％，a[1]的概率为25％

Question

不要太复杂，基本上我只想从数组中选择一个元素，就像我为每个索引进行硬币抛掷，并在第一次得到正面时选择索引。同时，没有正面意味着我选择最后一个元素。

我想出了以下方法，想知道是否有更好/更有效的方法。

def coin_toss(size)
  random_number = rand(2**size)
  if random_number == 0
    return size-1
  else
    return (0..size-1).detect { |n| random_number[n] == 1 }
  end
end

- paarshad

---

不应该是索引（0..index-1）吗？索引大小超出了边界。另外，为什么要传递数组的大小而不是数组本身（然后返回值a[i]而不是i）？ - tokland

已修复，谢谢。我只是传递了大小，因为我正在计时各种方法，实际上拥有一个数组并不重要。 - paarshad

Answer 1

第一次猜测...在1和2**size之间选择一个随机数，找到以2为底的对数，然后从末尾选取那么多个元素。

请原谅我的可怕的Ruby技能。

return a[-((Math.log(rand(2**size-1)+1) / Math.log(2)).floor) - 1]

如果rand返回0，则应选择最后一个元素。如果返回1或2，则选择倒数第二个元素。如果返回3、4、5或6，则选择倒数第三个元素。假设随机数均匀分布，每个元素被选中的概率是其后一个元素的两倍。

编辑：实际上，似乎有一个log2函数，因此我们不必进行对数/对数（2）的计算。

return a[-(Math.log2(rand(2**size - 1)+1).floor) - 1]

你也许可以完全摆脱那些日志调用，比如：

return a[-((rand(2**size-1)+1).to_s(2).length)]

但是您正在创建一个额外的字符串。不确定这是否比复杂的数学更好。 :)

编辑：实际上，如果您要走字符串路线，可以完全摆脱+1和-1。这将使概率更准确，因为最后两个元素应该有相等的被选择机会。（如果未选择倒数第二个值，则始终会选择最后一个值。）

编辑：我们还可以将**转换为位移，这应该会更快（除非Ruby已经足够聪明了）。

return a[-(rand(1<<size).to_s(2).length)]

- cHao

---

这个数学有点复杂...我希望它更简单一些。更新了一个额外的、更简单但更混乱的方法。 - cHao

非常有趣的方法。我用 size = 20 进行了基准测试（实际上对我来说是最常见的值），你的方法只用了我的一半时间，但不幸的是，它有一半的时间会失败，并显示“Errno::EDOM: Numerical argument out of domain - log”。 - paarshad

有点奇怪。+1 应该将 rand 的返回值推进到对数函数的定义域中。(log(1) 为零；log(0) 要么未定义，要么为负无穷，我忘记了) - cHao

啊，我在输入到 irb 时漏掉了 +1。对此感到抱歉。 - paarshad

@cHao：我相信将数学部分分离出来是有意义的。我猜你在这里做的是获取0到N之间的随机数，只是不均匀分布（不确定分布应该叫什么，跳过了一些课程:），也许是对数分布或泊松分布？ - Mladen Jablanović

Answer 2

一种非智能、简单的方法是：

def coin_toss( arr )
  arr.detect{ rand(2) == 0 } || arr.last
end

- steenslag

---

虽然不如 log 版本快，但仍比我的版本快。谢谢。 - paarshad