随机算法

前言 多年项目开发，总是会遇到很多随机算法场景，特别是策划要求进行权重累加且不放回抽取模式的场景。现总结一套圆桌随机算法以供参考。 第 1 版 —— 基础实现 第 1 版为最初版本，为了解决基本的项目需求而设计，实现了权重区间查找的核心逻辑。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 -- 圆桌随机类 g_tRoundTable = {} g_tRoundTable.__index = g_tRoundTable -- 构造函数 function g_tRoundTable:new() local instance = { items = {}, -- 保存随机项，形式： { {id=1, weight=10}, {id=2, weight=20} } totalWeight = 0, -- 权重总和 lastError = "" -- 保存最近的错误信息 } setmetatable(instance, self) return instance end -- 添加随机项 function g_tRoundTable:addItem(id, weight) if weight <= 0 then self.lastError = "Invalid weight: " .. tostring(weight) return false end table.insert(self.items, {id = id, weight = weight}) self.totalWeight = self.totalWeight + weight return true end -- 清空所有随机项 function g_tRoundTable:clearItems() self.items = {} self.totalWeight = 0 end -- 获取随机数（工具函数） function g_tRoundTable:getRandom(low, high) return math.random(low, high) -- 返回 [low, high] 间的随机数 end -- 查找随机数属于哪个区间 function g_tRoundTable:getZoneIndex(randomValue) for i, item in ipairs(self.items) do if randomValue < item.weight then return i else randomValue = randomValue - item.weight end end -- 理论上不会执行到这里 self.lastError = "Random value out of range" return 1 end -- 提取随机项 function g_tRoundTable:fetchItems(count, independent) local ntotalItems = #self.items if self.totalWeight <= 0 or ntotalItems == 0 then self.lastError = "No items to fetch from" return {} -- 空数组 end local results = {} for _ = 1, count do if self.totalWeight <= 0 or ntotalItems == 0 then break -- 如果池中没有可用项，跳出 end -- 生成随机数[0, totalWeight) local randomValue = self:getRandom(0, self.totalWeight - 1) local zoneIndex = self:getZoneIndex(randomValue) -- 添加结果 table.insert(results, self.items[zoneIndex].id) -- 如果是非独立模式，需要移除已取出的项 if not independent then self.totalWeight = self.totalWeight - self.items[zoneIndex].weight table.remove(self.items, zoneIndex) end end return results end -- 获取最近的错误 function g_tRoundTable:getLastError() return self.lastError end 第 2 版 —— 性能与功能升级 后来因需求越来越复杂，要求也越来越多，比如需要频繁动态调整、需要重复抽取，且性能也急需提升，故而 2.0 版本诞生了。 ...