找到无碰撞随机数的有效方法

Question

我有一个用户表,用户ID是公共的.但是我想混淆注册用户的数量和项目的趋势,所以我不希望公共递增ID.

创建新用户时,我想找到一个大于某个数字但尚未存在于数据库中的随机整数.

天真的代码:

<?php
    $found = false;
    while(!$found) {
      $uid = rand(1000000000,4294967295) // find random number betwen minimum and maximum
      $dbh->beginTransaction();
      // check if user id is in use, and if not insert it
      if($dbh->query("SELECT * FROM users WHERE uid = $uid")) {
        $dbh->exec("INSERT INTO users (uid) VALUES ($uid)");
        $found = true;
      }
      $dbh->commit();
    }
    // we just got our new uid ...
?>

这将起作用,但可能会变得低效.确实有一个很大的范围,击中未使用的uid的可能性很高.但是,如果我想使用较小的范围,因为我不想拥有这么长的用户名怎么办？

我担心的例子:

• 所有用户ID的60%正在使用中
• 击中未使用的uid的几率为0.4
• 第一次尝试的成功率为0.4%
• 如果第一次没有成功,第二次尝试的概率为0.6*0.4
• 所以最多两次尝试我有0.4 + 0.6*0.4的能力(是吗？)

因此,我想到的一种优化方法如下:

• 找到一个随机数,检查它是否有空,如果不是,则将其递增1并再试一次,依此类推
• 如果达到最大数量,则继续使用最小数量

这应该给我一个最大运行时间为O(范围)的数字

这听起来很糟糕,但我认为不是,因为我向数据库提交随机数,并且他们都是初学者,这是不太可能的.那真的有多好/多少呢？

我认为这样可以正常工作,但我希望它更好

那么这个怎么样？

• 找一个随机数
• 查询数据库,从该数字开始,在整个范围内占用了多少个数字(这第一步很简单...)
• 如果在该范围内有数字,则将范围除以一半再试一次.从初始号码开始
• 如果有数字占用,则将范围除以一半,然后再试一次.从初始号码开始

如果我正确思考,这将给ma一个最大为O(log(范围))时间的数字.

这非常令人满意,因为log()非常好.但是我认为这种方法通常会尽可能地糟糕.因为使用我们的随机数字,我们可能总是在较大的间隔中命中数字.

所以在开始时我们的纯随机方法可能更好.

那么有这样的限制怎么样？

• 选择当前使用的号码数
• 它是否大于X,对数范围方法
• 如果不是,请使用纯随机方法

X会是什么？为什么？

最后一个问题:

这很简单,同时也非常复杂.

我认为这是一个标准问题,因为很多系统都使用随机ID(支持票等),所以我无法想象我是第一个偶然发现这个问题的人.

你怎么解决这个问题？任何输入都是适合的!

我可以使用maby现有的类/程序吗？

或maby一些我可以使用的数据库函数？

我想在PHP/Mysql中做到这一点

重要编辑:

我只是考虑了范围/对数解决方案.对于我的措辞,这似乎是完全废话 ,因为:

• 如果我在开始时击中占用的数字怎么办？

然后,如果它只有1,我将我的范围划分得很长.即使这样,这个数字也会出现.

所以从开始就完全和纯随机方法一样,只会更糟......

我有点尴尬,我做了这个,但我会留下它,因为我认为这是一个过于复杂的思想的好例子!

Answer 1

如果p是正在使用的ID的比例,那么您的"天真"解决方案平均需要1 /(1-p)次尝试才能找到未使用的ID.(见指数分布).在占用率为60%的情况下,这仅仅是1/0.4 = 2.5的查询......

您的"改进"解决方案需要有关log(n)数据库调用,其中n是正在使用的ID数.这比"天真"的解决方案要多得多.此外,您改进的解决方案是不完整的(例如,它不处理子范围中的所有数字都采用的情况,并且没有详细说明您递归到的子范围)并且实现引导更复杂.

最后,请注意,如果数据库提供非常严格的事务隔离(您的扩展性很差),并且可能不是数据库系统的默认行为,那么您的实现将只是线程安全的.如果结果证明是一个问题,您可以推测性地插入随机ID,并在发生约束违规时重试.