^_^内容原创，禁止转载
假设配置如下：
1 local reward_pool = {
2 {weight = 1000, item = {type = 100218, num = 12}},
3 {weight = 1000, item = {type = 100218, num = 12}},
4 {weight = 1000, item = {type = 100218, num = 12}},
5 {weight = 1000, item = {type = 100218, num = 12}},
6 {weight = 1000, item = {type = 100218, num = 12}},
7 {weight = 1000, item = {type = 100218, num = 12}},
8 }
1.顺序查找，预处理时间复杂度O(n)，抽奖最坏情况O(n)
1 --预处理
2 local N = #reward_pool
3 local total_weight = 0
4 for _, v in ipairs(reward_pool) do
5 total_weight = total_weight + v.weight
6 end
7
8 --实现
9 local rand_weight = math.random(total_weight)
10 local reward_index
11 local _total_weight = 0
12 for k, v in ipairs(reward_pool) do
13 _total_weight = _total_weight + v.weight
14 if _total_weight >= rand_weight then
15 reward_index = k
16 break
17 end
18 end
2.按照离散思路进行分割，二分查找，预处理时间复杂度O(n)，抽奖最坏情况O(logn)
1 --预处理
2 local N = #reward_pool
3 local com_weight = 0
4 for _, v in ipairs(reward_pool) do
5 com_weight = com_weight + v.weight
6 v.weight = com_weight
7 end
8
9 --实现
10 local left, right = 1, #reward_pool
11 while right >= left then
12 local mid = math.floor((left + right) / 2)
13 local mid_weight = reward_pool[mid].weight
14 if value == mid_weight then
15 right = right - 1
16 break
17 elseif value < mid_weight then
18 right = mid - 1
19 else
20 left = mid + 1
21 end
22 end
23 right = right + 1 --此时right为reward_pool中抽到的索引
这种方法在实际上是对第一种方法的优化，在大多数情况下都可以取代第一种方法，但取舍还要看实际情况，一个极端且明显的例子如下：
1 local reward_pool = {
2 {weight = 1000, item = {type = 100218, num = 12}}, {weight = 1000, item = {type = 100218, num = 12}},
3 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}},
4 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}},
5 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}},
6 {weight = 1, item = {type = 100218, num = 12}}, {weight = 1, item = {type = 100218, num = 12}},
7 }
3.AliasMethod，个人实现的预处理O(3n)，抽奖时间复杂度O(1)，下面是实现过程，证明日后有时间再整理给出
1 queue = {}
2
3 function queue:new()
4 local res = {first = 0, last = -1}
5 self.__index = self
6 setmetatable(res, self)
7 return res
8 end
9
10 function queue:push(value)
11 self.last = self.last + 1
12 self[self.last] = value
13 end
14
15 function queue:pop()
16 local first = self.first
17 if first > self.last then
18 self.first = 0
19 self.last = -1
20 return nil
21 end
22 local value = self[first]
23 self[first] = nil
24 self.first = self.first + 1
25 return value
26 end
27
28 function queue:front()
29 return self[self.first]
30 end
31
32 --预处理
33 local N = #reward_pool
34 local total_weight = 0
35 for _, v in ipairs(reward_pool) do
36 total_weight = total_weight + v.weight
37 end
38
39 local Prob = {}
40 local Alias = {}
41 local weightN_queue_L = queue:new()
42 local weightN_queue_U = queue:new()
43 for k, v in ipairs(reward_pool) do
44 local weight_N = v.weight * N
45 if weight_N == total_weight then
46 Prob[k] = weight_N
47 else
48 local tb = {index = k, value = weight_N}
49 local qu = weight_N > total_weight and weightN_queue_U or weightN_queue_L
50 qu:push(tb)
51 end
52 end
53
54 while true do
55 local l_qu = weightN_queue_L:pop()
56 if not l_qu then
57 break
58 end
59 local u_qu = weightN_queue_U:front() --或直接pop，比total_weight大再push回去
60 Prob[l_qu.index] = l_qu.value
61 Alias[l_qu.index] = u_qu.index
62 u_qu.value = u_qu.value + l_qu.value - total_weight
63 if u_qu.value < total_weight then
64 weightN_queue_U:pop()
65 weightN_queue_L:push(u_qu)
66 elseif u_qu.value == total_weight then
67 weightN_queue_U:pop()
68 Prob[u_qu.index] = total_weight
69 end
70 end
71 weightN_queue_U = nil
72 weightN_queue_L = nil
73
74 --实现
75 local n = math.random(N)
76 local weight = math.random(total_weight)
77 local reward_index = weight > Prob[n] and Alias[n] or n
请发表评论