c++ - 来自二维网格的不同随机点

Question

我有一个大的二维网格，让我们说 10000 X 10000。从这些网格中我需要选择 1000 个随机点，但我还需要注意两个点都不相同。我想到的标准方法是在选择每个点之后，我应该检查所有以前的条目以查看该点是否已经被选择，但对于大型网格和大量点来说，这将变得低效。有更好的方法吗？我正在使用 C++

Answer 1

似乎对于大型网格和大量点，这将变得低效

不必要。有两个潜在的低效率来源：

1. 拒绝采样导致的开销（即，必须不断尝试，直到找到尚未选择的点）。鉴于您选择了 0.001% 的点，随机选择同一点两次的机会非常小。因此，重试的成本应该可以忽略不计。
2. 检查随机选择的点是否已被选择的开销。如果您将所有先前选择的点存储在合适的数据结构中，则可以及时完成O(1)。为此，std::unordered_set将是一个很好的候选人。集合的大小将随着您需要选择的元素数量线性增长，并且完全独立于网格大小。

Answer 2

你可以实现这样的算法：

1. 创建一个从哈希到点的空映射
2. 选择随机点
3. 计算哈希
4. 如果在映射中散列，则转到 1
5. 保存哈希和点
6. 如果积分还不够，请转到 1

Answer 3

随机选择任何点然后如果它存在于Selected Points列表中则将其丢弃应该不会是低效的，只要您有Selected Points的良好排序集合，您也可以轻松插入。

此外，根据您的点的定义方式（即它们是否都与您定义的类或结构相关联），您可以向点对象添加一个布尔变量，名为Selected. 选择一个点后，检查它是否已标记为Selected。如果没有，请将其添加到您的列表中并将Selected值更改为TRUE. 否则，继续选择随机点。