从2维网格不同的随机点(Different random points from a 2 dimen

我有一个大的2维网格，让我们说10000×10000从这些格子，我需要选择1000个随机点，但我也需要照顾，没有任何两点是相同的。 这使我想到的标准方法是选择每一点我应该检查所有以前的条目，看看是否能点已经选定，或不经过，但它似乎对大电网和大量的点，这将成为效率低下。 有没有更好的办法做到这一点？ 我使用C ++

Answer 1:

随机选择的任何一点，然后丢弃它，如果它在所选择的点列表中存在不应该是低效率的，只要你有好整理选定点的集合，你也可以很容易地插入。

另外，根据您的积分是如何定义的（即他们在每一个类或结构，您已经定义的关联），你可以一个布尔变量添加到点对象，命名Selected 。 一旦你选择一个点，检查，看它是否已被标记为Selected 。 如果没有，把它添加到你的列表并更改Selected值TRUE 。 否则，继续与您的随机点的选择。

Answer 2:

它似乎对大电网和大量的点，这将成为低效

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

1. 开销拒绝抽样引起的（即具有不断尝试，直到你找到一个还未选定点）。 既然你选择的点的0.001％，随机选择的相同点的两次机会非常小。 因此，重新尝试成本可以忽略不计。
2. 检查是否随机选择的点的开销已经被选择。 如果您存储所有之前选择的点在合适的数据结构，这可以做到O(1)时间。 对于这一点， std::unordered_set将是一个不错的人选。 该集的大小将在您需要选择元素的数量呈线性增长，并且将完全独立于电网的大小。

Answer 3:

您可以实现这样的算法：

1. 从创建到哈希点空映射
2. 选择随机点
3. 计算哈希
4. 如果散列映射，转到1
5. 保存散列和点
6. 如果不够分呢，转到1

文章来源: Different random points from a 2 dimensional grid