加权随机映射

Question

假设我有一个很大的二维值数组，其范围在[0,1]之间，其中0表示“不可能”而1表示“极有可能”。

根据上述概率，如何选择这个数组中的一组随机点？

- Nicolas Repiquet

---

重复。已经有许多关于这个问题的变体，这里是其中一个。https://dev59.com/D3I95IYBdhLWcg3wzhd9 - Samsdram

Answer 1

一种解决问题的方法是暂时忽略你正在处理一个二维网格的事实。你所拥有的是一组加权项目。从这样的一组中随机选择的标准方法是：

1. 求和权重，称之为s
2. 选择一个均匀的随机值0 <= u < s
3. 遍历项目，保持正在检查的项目的权重的运行总计t
4. 当t >= u时，立即选择你当前正在查看的项目（刚刚添加其权重的项目）。

这可以通过添加以下步骤来修改以进行多个不带替换的选择：

• 每次选择后，从s中减去所选项目的权重（如果您的权重是浮点数并且稳定性是一个问题，则您可能更喜欢偶尔从头开始重新计算它）。

• 重复从2开始，但在第3步跳过已经被选择过的项目。

如果求和权重是不可行或不可取的（如果您的数组特别大），则有其他选项。我首先想到的是拒绝抽样，这是一个相当广泛的主题，所以我会向您推荐谷歌和维基百科，因为它们的覆盖范围非常好。

编辑：忘记回到你有一个二维数组的事实。通过预先计算地图中一系列区域的权重总和（MIPMAP样式），您可以显着加快速度，以便快速跳转到实际选择的权重的位置。

- mokus

---

我的数组确实非常大，所以你描述的第一种解决方案似乎不可行。拒绝抽样看起来很有前途。谢谢你的帮助。 - Nicolas Repiquet

@Nicholas Repiquet：我也不会完全否定第一种方法。将数组求和的成本与首次创建它的成本相当，并且通过一些工作可以同时完成（如果数组经常更改，则可以保持最新）。但是，如果您可以想出一个相对紧密的上限，或者如果您不需要大量样本（因此许多潜在的拒绝是可以接受的），那么拒绝是一个非常好的选择。 - mokus

实际上，经过进一步的思考，我想起了另一种值得研究的技术——蓄水池抽样。它需要对数组进行单次遍历，并为每个元素生成一个随机变量。维基百科文章非常简洁，但至少可以传达要点，至少对于非加权情况是如此。通过一些数学计算，将其推广到加权抽样并不太困难。 - mokus

实现区域层次结构的简单高效方法是将每个区域作为索引范围处理，这并不依赖于它本身是否为二维数组。但在层次结构的较高级别，它们将成为行范围，在较低级别则是单行元素范围。 - Stewart

Answer 2

代码：

  count = 0
  maxPointsInSet = 100
  foreach(point in array){
      if(randomWithChacnce(point.value))) {
         addToSet(point)
         count++
      }
      if(count == maxPointsInSet)
         break;
  }

  function randomWithChacnce(int num){
    random = a randomized number between 0 to 1 // or random from 1 to 100 num*100
    if(num >= random)
     return true;
    return false
  }

如果您需要以任何特定语言，请告诉我

- The GiG

---

谢谢！不过，这会选择所有设置为1的点，是吗？此外，我需要一种控制放入集合中的点数的方法。比如说，“我需要在这张地图上选择100个随机点”。 - Nicolas Repiquet

我稍微修改了代码，使其符合您的要求，现在它可以工作1。 - The GiG

它是否均匀分布？它是否偏向于数组开头的点？ - Nicolas Repiquet