algorithm - 获取随机生成器生成的百分比唯一数字

Question

我在我的 python 代码中使用随机生成器。我想获得在很大范围内生成的唯一随机数的百分比，例如随机(0:10 ^ 8)。我需要生成 10 ^ 12 个数字就空间复杂度而言，什么是有效的算法？ 代码类似于:

import random
dif = {}
for i in range(0,1000):
    rannum = random.randint(0,50)
    dif[rannum] = "True"
dif_len = len(dif)
print dif_len
per = float(dif_len)/50
print per

Answer 1

您必须跟踪生成器生成的每个数字，否则无法知道以前是否见过某个新数字。最好的方法是什么？这取决于您要检查多少个数字。对于小 N，使用 HashSet。在 N 较大的情况下，使用位图会变得更加高效。

对于小 N...

public class Accumulator {
   private int uniqueNumbers = 0;
   private int totalAccumulated = 0;
   private HashSet<int> set = new HashSet<int>();

   public void Add(int i) {
     if (!set.Contains(i)) {
       set.Add(i);
       uniqueNumbers++;
     }

     totalAccumulated++;

   }

   public double PercentUnique() {
     return 100.0 * uniqueNumbers / totalAccumulated;
   }
}