TypeScript加权随机表优化：寻求替代重复元素数组的数据结构

你的当前实现（重复元素数组）虽然查询快，但权重总和大时内存开销会急剧膨胀，比如单条目权重10000就要存10000次副本，完全没必要。针对这个场景，有两种更合适的方案：

一、前缀和数组 + 二分查找（静态表首选） #

这是静态加权随机选择的标准优化方案，内存只和条目数相关，和权重大小无关：

实现步骤 #

1. 解析原始表时，将条目和对应权重存储为结构化数组，比如：

   const items = [
     { value: "alcohol", weight: 5 },
     { value: "salt packing", weight: 2 },
     { value: "formaldehyde", weight: 1 }
   ];
   

2. 计算前缀和数组，每个元素是前面所有条目的权重累加和：[5, 7, 8]（总权重为7）。
3. 生成一个0到总权重之间的随机数，用二分查找定位该随机数落在哪个前缀和区间，返回对应条目。

TypeScript实现示例 #

interface WeightedEntry<T> {
  value: T;
  weight: number;
}

class StaticWeightedTable<T> {
  private readonly entries: WeightedEntry<T>[];
  private readonly prefixSums: number[];
  private readonly totalWeight: number;

  constructor(rawEntries: WeightedEntry<T>[]) {
    this.entries = [...rawEntries];
    this.prefixSums = [];
    let sum = 0;
    for (const entry of this.entries) {
      sum += entry.weight;
      this.prefixSums.push(sum);
    }
    this.totalWeight = sum;
  }

  pick(): T {
    const rand = Math.random() * this.totalWeight;
    // 二分查找第一个大于rand的前缀和索引
    let left = 0;
    let right = this.prefixSums.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.prefixSums[mid] > rand) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return this.entries[left].value;
  }
}

// 使用示例
const preservationTable = new StaticWeightedTable([
  { value: "alcohol", weight: 5 },
  { value: "salt packing", weight: 2 },
  { value: "formaldehyde", weight: 1 }
]);
console.log(preservationTable.pick());

优缺点 #

• 内存开销：O(n)（n为条目数量），完全不受权重大小影响。
• 查询性能：O(log n)，相比原方案的O(1)略有下降，但绝大多数场景下可以忽略，内存收益远大于性能损失。
• 局限性：适合权重固定的静态表，修改权重需要重新计算前缀和数组（O(n)时间）。

二、线段树（动态表首选） #

如果你的库需要支持运行时修改条目权重，线段树是更优的选择，它能做到O(log n)的查询和权重修改：

核心原理 #

线段树的每个节点存储对应区间的权重总和，查询时从根节点开始：

1. 生成随机数后，比较随机数与左子树的总权重。
2. 如果随机数小于左子树总和，递归查询左子树；否则减去左子树总和，递归查询右子树。
3. 到达叶子节点时，返回对应条目。

优缺点 #

• 内存开销：O(4n)（最坏情况），比前缀和数组略高，但依然远低于重复元素数组。
• 查询/修改性能：均为O(log n)，适合需要动态调整权重的场景。
• 实现复杂度：比前缀和数组高一些，需要额外处理树的构建、更新逻辑。

三、简单遍历累加（小条目场景） #

如果你的表条目数量极少（比如10条以内），可以直接生成随机数后遍历条目累加权重，直到累加和超过随机数就返回当前条目。这种实现最简单，但查询时间是O(n)，条目多的时候性能会下降。

总结 #

• 静态权重表：优先用前缀和数组+二分查找，平衡内存与性能。
• 动态权重表：用线段树支持高效的权重修改和查询。
• 小条目表：任意方案都可以，甚至原方案也能凑合。

内容的提问来源于stack exchange，提问作者joshlyle