performance - 在非常大的数组中找到 N 个唯一随机数的最佳算法

Question

我有一个数组，例如，包含 1000000000000 个元素(整数)。例如，从该数组中仅选择 3 个随机且独特的元素的最佳方法是什么？元素在整个数组中必须是唯一的，而不是在 N 个(在我的示例中为 3 个)元素的列表中。

我阅读了 Reservoir sampling，但它只提供了选择随机数的方法，这些随机数可以是非唯一的。

Answer 1

如果命中非唯一值的几率很低，最好的办法是从数组中选择 3 个随机数，然后对照整个数组检查每个数以确保它是唯一的 - 如果不是，请选择另一个随机样本更换它并重复测试。

如果命中非唯一值的几率很高，这会增加您需要扫描数组以寻找唯一性的次数，并使简单的解决方案成为非最佳解决方案。在这种情况下，您需要将确保唯一编号的任务与进行随机选择的任务分开。

对数组进行排序是查找重复项的最简单方法。大多数排序算法都是 O(n log n)，但由于您的键是整数 Radix sort可能会更快。

另一种可能性是使用哈希表来查找重复项，但这将需要大量空间。您可以使用较小的哈希表或 Bloom filter识别潜在的重复项，然后使用另一种方法遍历较小的列表。