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

Question

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

Answer 1

it seems for large grids and large number of points this will become inefficient

不一定。有两个潜在的低效率来源:

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