生成非重复的随机数字
我想在C中创build一个函数。它将返回一个范围为N的随机整数，如： – rand（）％N; 但事情是我想跟踪唯一性。 我不希望数字重复。 但我也可以做一个数组，并复制生成的整数。 如： – array[count] = rand() % N; 并每次检查生成的数字是否已经在里面。 （只需通过在数组[]中search它）; 这是一个简单的方法，但是一个正确的方法。 它会采取很多如果和为了; 为此工作。 这是我能想到的最好的。
事情是，我想为这个问题得到最好的/优化的解决scheme。 什么将是最有效的方式来做到这一点？
让我们清除一些事情： – 我想从一个总是唯一的NSArray中设置一个UILabel文本。 我的NSArray从Plist获取数据，而我的Plist有超过1000个条目。 如果我想多次这样做会影响性能，所以我想要一些有效的方法来做到这一点。
这听起来像你想要的是真正的数字1..N的随机排列。 所以，用一个连续的整数1..N填充一个数组，然后对数组进行洗牌。 有一个众所周知的洗牌algorithm ，你可以查找。
而不是一个数组，你可以使用一个超快的高效布隆filter 。 如果你正在生成大量的数字，这将比在数组中循环更快。
使用某种散列表来存储已经生成的号码，并快速检查已经看到的号码。 我不知道你在做什么，但是因为你需要独特的rand，所以我想你正在试图对一个有限集进行置换，如果是这样的话，看看一些Shufflingalgorithm 。
四个选项，全部在内存和时间都是O （1）：
- 只是增加一个全球计数器。 既然你想要唯一性，不pipe怎样都不能生成随机数。
- 从一个足够大的集合中产生一个数字，这是很不可能重复的一个数字。 64位对于应用内唯一性已经足够了; 全球唯一性足够128位。 这是UUID的工作原理。
- 如果选项1对您来说不够“随机”，则使用全局（32位）计数器的CRC-32哈希值。 在N位整数和它们的CRC-N之间有1对1的映射（双射），所以唯一性仍将得到保证。
- 使用线性反馈移位寄存器生成数字。 这些是N位计数器，它们看起来是“随机的”（虽然明显是确定性的）模式。 为了您的目的，这基本上是选项3的适度更快的版本。
所描述的algorithm是非常糟糕的，因为它search每个新条目的新数组。 这意味着随着数组的增长，它必须search越来越多的数据，更糟糕的是，随着剩余项目的数量减less，它将最终循环更多。
例如，如果你有一个从1到10的列表，当你填充了8个项目时，只剩下两个项目（比如7和9），现在每次产生一个随机数字， 80％的时间是唯一的数字，并且在检测到重复之前必须扫描至less六个条目。
在某些库中可能有一些更好的方法，但是比问题更好的方法是创build一个（链接的）项目列表，随机select一个， 删除它，并将其添加到新列表中。 这样，每次你随机挑选一个，保证是唯一的，因为使用的已经不在池中了。
