This was inspired by a question at a job interview: how do you efficiently generate N unique random numbers? Their security and distribution/bias don't matter.
这是受一次面试中一个问题的启发:如何有效地生成N个唯一随机数?他们的安全性和分布/偏见并不重要。
I proposed a naive way of calling rand() N times and eliminating dupes by trial and error, thus getting inefficient and flawed solution. Then I've read this SO question, these algorithms are great for getting quality unique numbers and they are O(N).
我提出了一种简单的方法来调用rand() N次，并通过反复试验来消除dupes，从而得到低效且有缺陷的解决方案。然后我读了这个问题，这些算法非常适合获得高质量的唯一数字，它们是O(N)
But I suspect there are ways to get low-quality unique random numbers for dummy tasks in less than O(N) time complexity. I got some possible ideas:
但是我怀疑有一些方法可以在小于O(N)时间复杂度的情况下获得低质量的唯一随机数。我有一些可能的想法:
- Store many precomputed lists each containing N numbers and retrieve one list randomly. Complexity is O(1) for fixed N. Storage space used is O(NR) where R is number of lists.
- 存储多个包含N个数字的预计算列表，并随机检索一个列表。复杂度为O(1)，用于固定n的存储空间为O(NR)，其中R为列表的个数。
- Generate N/2 unique random numbers and then divide them by 2 inequal parts (floor/ceil for odd numbers, n+1/n-1 for even). I know this is flawed (duplicates can pop up) and O(N/2) is still O(N). This is more of a food for thought.
- 生成N/2唯一的随机数，然后将它们除以2个不相等的部分(奇数为楼层/ceil，偶数为N +1/ N -1)。我知道这是有缺陷的(重复出现)，O(N/2)仍然是O(N)这更像是一种思考的食物。
- Generate one big random number and then squeeze more variants from it by some fixed manipulations like bitwise operations, factorization, recursion, MapReduce or something else.
- 生成一个大随机数，然后通过一些固定的操作(如位运算、分解、递归、MapReduce或其他操作)从它中挤出更多的变体。
- Use a quasi-random sequence somehow (not a math guy, just googled this term).
- 用一个准随机序列(不是一个数学家伙，只是用谷歌搜索这个术语)。
Your ideas?
你的想法呢?
2 个解决方案
#1
6
Presumably this routine has some kind of output (i.e. the results are written to an array of some kind). Populating an array (or some other data-structure) of size N is at least an O(N) operation, so you can't do better than O(N).
假定这个例程有某种输出(例如，结果被写入某种数组)。填充大小为N的数组(或其他数据结构)至少是一个O(N)操作，所以不能比O(N)做得更好。
#2
0
You can consequently generate a random number, and if the result array contains it, just add to it the maximum number of already generated numbers.
因此，您可以生成一个随机数，如果结果数组包含随机数，那么只需向它添加已经生成的数字的最大数量。
Detecting if a number already generated is O(1) (using a hash set). So it's O(n) and with only N random() calls.
检测已生成的数字是否为O(1)(使用散列集)。所以它是O(n)并且只有n个随机()调用。
Of course, this is an assumption that we do not overflow the upper limit (i.e. BigInteger).
当然，这是一个假设，即我们不溢出上限(即BigInteger)。
#1
6
Presumably this routine has some kind of output (i.e. the results are written to an array of some kind). Populating an array (or some other data-structure) of size N is at least an O(N) operation, so you can't do better than O(N).
假定这个例程有某种输出(例如，结果被写入某种数组)。填充大小为N的数组(或其他数据结构)至少是一个O(N)操作，所以不能比O(N)做得更好。
#2
0
You can consequently generate a random number, and if the result array contains it, just add to it the maximum number of already generated numbers.
因此，您可以生成一个随机数，如果结果数组包含随机数，那么只需向它添加已经生成的数字的最大数量。
Detecting if a number already generated is O(1) (using a hash set). So it's O(n) and with only N random() calls.
检测已生成的数字是否为O(1)(使用散列集)。所以它是O(n)并且只有n个随机()调用。
Of course, this is an assumption that we do not overflow the upper limit (i.e. BigInteger).
当然，这是一个假设，即我们不溢出上限(即BigInteger)。