Swift中如何从频率映射表按概率随机选取键

数据老陈

2026-7-3

按权重概率随机选取元素的高效实现

你提到的朴素方案确实会在权重较大时造成严重的内存浪费，这里给你一种更高效的实现思路——前缀和+二分查找，不需要存储大量重复元素，内存占用仅和水果种类数成正比。

实现步骤

第一步：构建前缀和映射表
把原字典的权重转换成前缀和形式，同时保留对应的水果名称。比如针对你的freqs字典，处理后得到：
```
[
  ("Apple", 3823),
  ("Banana", 4316),  // 3823+493
  ("Grape", 12645),  // 4316+8329
  ("Orange", 12894)  // 12645+249
]
```
第二步：生成随机数
生成一个范围在1到总数量（12894）之间的随机整数randomNum。
第三步：二分查找匹配区间
用二分查找找到第一个前缀和值大于等于randomNum的条目，对应的水果名称就是符合概率要求的结果。

Swift代码示例

import Foundation

func randomFruit(from freqs: [String: Int]) -> String? {
    guard !freqs.isEmpty else { return nil }
    
    // 构建前缀和数组
    var prefixSum = [(fruit: String, sum: Int)]()
    var currentSum = 0
    for (fruit, count) in freqs {
        currentSum += count
        prefixSum.append((fruit, currentSum))
    }
    let total = currentSum
    
    // 生成1到total之间的随机数
    let randomNum = Int.random(in: 1...total)
    
    // 二分查找
    var left = 0
    var right = prefixSum.count - 1
    while left < right {
        let mid = (left + right) / 2
        if prefixSum[mid].sum < randomNum {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return prefixSum[left].fruit
}

// 测试调用
let freqs = [
    "Apple": 3823,
    "Banana": 493,
    "Grape": 8329,
    "Orange": 249,
]
if let fruit = randomFruit(from: freqs) {
    print("随机选中的水果：\(fruit)")
}