algorithm - 在包含一组给定数字的范围内随机选择一些数字的最快方法是什么？

Question

这是我想要的功能

random_select(contain_list, ttl_num, sample_num)

从0到ttl_num-1有ttl_num个整数可供选择，我想返回一个sample_num的列表 唯一整数，其中 contain_list 中提供的数字必须在列表中，其他数字随机选择。

我必须经常做这个查询，每次都有不同的contain_list，但是ttl_num, sample_num对所有的都是一样的查询。

目前我在做的是，首先生成一组ttl_num整数，从集合中减去contain_list，随机选择一些数字，其余数字不替换，然后将其与 contain_list 连接以获得结果。

我认为这不是最快的方法，还有更好的想法吗？

如果需要，可以使用全局变量。

编辑:
sample_num不小于contain_list长度，我想得到contain_list加上sample_num - contain_list.length其他随机数
保证 contain_list 中的数字都在 0 到 ttl_num-1 范围内。

Answer 1

这里有几种可能性。两者都没有您已有的复杂，但它们中的一个或两者可能会更快，具体取决于参数值的大小。只有根据您的实际数据进行基准测试才能确定。

方法一

此处的逻辑与您已经在做的基本相同。它只是用整数数组代替了集合的生成和操作，应该更轻量级。但是，它确实需要对 contain_list 进行排序(降序)，因此它实际上是否比您已有的运行速度更快可能取决于 contain_list.count 的大小和 ttl_num。

1) initialize a tracking var, remaining_num = ttl_num

2) initialize an integer array with value = index

3) sort contain_list descending

4) iterate through contain_list (now in descending order); for each:
4.1) decrement remaining_num
4.2) swap the element at the selected index with the one at index = remaining_num

5) iterate (sample_num - contain_list.count) times; for each:
5.1) generate a random index between 0 and remaining_num (inclusive and exclusive, respectively)
5.2) decrement remaining_num
5.3) swap the element at the selected index with the one at index = remaining_num

6) The resultant samples will start at index reamining_num and run through the end of the array.

这是一个运行 random_select({3, 7}, 10, 5)...的例子

remaining_num = 10

available_num[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

contain_list = {7, 3}

select the 7
remaining_num = 9
available_num[] = {0, 1, 2, 3, 4, 5, 6, 9, 8, 7}

select the 3
remaining_num = 8
available_num[] = {0, 1, 2, 8, 4, 5, 6, 9, 3, 7}

select a random(0,8), e.g. 2
remaining_num = 7
available_num[] = {0, 1, 9, 8, 4, 5, 6, 2, 3, 7}

select a random(0,7), e.g. 3
remaining_num = 6
available_num[] = {0, 1, 9, 6, 4, 5, 8, 2, 3, 7}

select a random(0,6), e.g. 0
remaining_num = 5
available_num[] = {5, 1, 9, 6, 4, 0, 8, 2, 3, 7}

result = {0, 8, 2, 3, 7}

方法二

如果 ttl_num 足够大而 sample_num 足够低，则可能值得将事情颠倒过来。也就是说，不是创建和操纵一组可用号码，而是仅跟踪选定号码的列表。然后，在选择每个随机目标时，通过遍历所选数字列表并计算小于或等于目标索引的次数来“跳过”先前选择的数字。

1) initialize a tracking var, remaining_num = ttl_num - contain_list.count

2) declare an empty list (vector) of integers, selected_num[]

4) iterate through contain_list; for each:
4.1) insert cointain_list[i] into selected_num[]

5) iterate (sample_num - contain_list.count) times; for each:
5.1) generate a random target between 0 and remaining_num (inclusive and exclusive, respectively)
5.2) decrement remaining_num
5.3) iterate through selected_num; for each:
5.3.1) if target >= selected_list[j], increment target
5.4) insert target into selected_num[]

6) The resultant samples will be all elements in selected_num.

这是一个运行 random_select({3, 7}, 10, 5)...的例子

remaining_num = 8

selected_num[] = {}

select the 3
selected_num[] = {3}

select the 7
selected_num[] = {3, 7}

select a random(0,8), e.g. target = 2
remaining_num = 7
2 < 3; target still 2
2 < 7; target still 2
selected_num[] = {3, 7, 2}

select a random(0,7), e.g. target = 3
remaining_num = 6
3 >= 3; target becomes 4
4 < 7; target still 4
4 >= 2; target becomes 5
selected_num[] = {3, 7, 2, 5}

select a random(0,6), e.g. target = 0
remaining_num = 5
0 < 3; target still 0
0 < 7; target still 0
0 < 2; target still 0
0 < 5; target still 0
selected_num[] = {3, 7, 2, 5, 0}

显然，如果 sample_num 很大，在选择每个新数字时遍历 selected_num[] 可能会变得很昂贵。这可以通过保持 selected_num[] 降序排列并在看到小于目标的数字时立即中断内部循环来缓解。在列表中的那个点插入目标以保持排序。