lua实现游戏抽奖的几种方法？

^_^内容原创，禁止转载

假设配置如下：

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