数据结构与算法 / 系统课时

算法与数据结构选型

算法与数据结构选型

问题模型确定后,仍需选择能满足规模、延迟和内存目标的实现。本课以“百万级整数用户 ID 的在线状态查询”为例,建立一套从操作分布到候选结构、再到验证结论的选型方法。

学习目标

  • 从数据规模、操作频率、内存和实时性四个维度比较方案
  • 根据业务约束缩小算法与数据结构的候选范围
  • 使用可运行样例和验收指标验证选型结论

先建立选择维度

选型不是背诵复杂度表,而是把复杂度与真实工作负载结合。对于同一个集合,查询占 99% 与写入占 99% 时,最佳结构可能完全不同;数据是否有界、是否要求排序,也会直接改变候选范围。

维度 必须确认的问题 对选型的影响
数据规模 元素数量和键空间上限是多少 决定内存预算与复杂度常数
操作频率 查询、插入、删除、遍历各占多少 决定需要优先优化的操作
内存限制 单实例可用内存和对象开销是多少 排除高额对象封装方案
实时性 关注平均延迟还是尾延迟 决定是否需要稳定上界和压测
数据特征 键是否连续、有界、重复或有序 决定能否使用数组、位图或树

算法与数据结构选型决策流程

用操作分布估算总成本

可以用一个简化表达式比较候选方案:

C=qrTr+qwTw+qdTdC = q_r T_r + q_w T_w + q_d T_d

其中 qrq_r、qwq_w、qdq_d 分别表示查询、写入和删除次数,TrT_r、TwT_w、TdT_d 表示对应操作的单次成本。这个表达式不是精确性能预测,但能避免只看某一个操作的复杂度。

以成员查询为核心时,常见候选结构可这样比较:

结构 成员查询 插入或设置 顺序能力 适用条件
ArrayList O(n)O(n) 尾部均摊 O(1)O(1) 保留插入顺序 数据较少,遍历多于查询
HashSet 期望 O(1)O(1) 期望 O(1)O(1) 不保证稳定顺序 键空间离散,通用成员查询
TreeSet O(log⁡n)O(\log n) O(log⁡n)O(\log n) 自动有序 需要范围查询或有序遍历
BitSet O(1)O(1) O(1)O(1) 按整数下标扫描 非负整数键有明确上界

复杂度相同也不代表实际成本相同。对象数量、缓存局部性、哈希计算、扩容和垃圾回收都会影响延迟,因此复杂度用于初筛,基准测试用于最终确认。

场景选型

假设系统维护用户是否在线,用户 ID 是 00 到 999999999999 的非负整数。业务每秒进行大量成员查询,写入和删除较少,不要求按上线时间排序,并希望单实例内存尽量小。

在这个约束下,BitSet 比 HashSet<Integer> 更合适:

  • 键空间连续且上界明确,可以直接用用户 ID 作为位下标。
  • 每个状态只占 1 位,100 万个位约需 125000 字节的位存储空间,约为 122 KiB,不包含少量对象开销。
  • 查询、设置和清除都通过位运算完成,路径短且没有整数装箱。
  • 如果键改为 UUID,或整数上界极大而实际元素极少,BitSet 会浪费空间,此时应重新评估 HashSet。

完整可运行示例

下面的 Java 17 程序使用 BitSet 保存在线状态,并演示设置、清除、查询和统计操作。

java
import java.util.BitSet;

public class BitSetSelectionDemo {

    public static void main(String[] args) {
        int userIdUpperBound = 1_000_000;
        BitSet onlineUsers = new BitSet(userIdUpperBound);

        // 用户上线时设置对应位,下线时清除对应位。
        onlineUsers.set(42);
        onlineUsers.set(700_000);
        onlineUsers.set(999_999);
        onlineUsers.clear(700_000);

        System.out.println("用户 42 在线: " + onlineUsers.get(42));
        System.out.println("用户 700000 在线: " + onlineUsers.get(700_000));
        System.out.println("当前在线人数: " + onlineUsers.cardinality());

        // previousSetBit 用于从右向左寻找最高的已设置下标。
        int highestOnlineUser = onlineUsers.previousSetBit(onlineUsers.length() - 1);
        System.out.println("最大在线用户 ID: " + highestOnlineUser);
    }
}

将代码保存为 BitSetSelectionDemo.java,然后执行:

bash
javac BitSetSelectionDemo.java
java BitSetSelectionDemo

预期输出

text
用户 42 在线: true
用户 700000 在线: false
当前在线人数: 2
最大在线用户 ID: 999999

输出验证了用户 42 和 999999 仍在线,用户 700000 已被清除,集合中共有两个有效状态。

用指标验证选型

完成初步选择后,应使用接近生产的数据验证,而不是只运行一个功能样例。验证清单至少包括:

  • 使用真实数量级和相似分布的数据,避免只测几十个元素。
  • 分别记录查询、写入和删除的吞吐量、平均延迟与高分位延迟。
  • 测量稳定状态下的内存占用,并观察扩容或垃圾回收带来的波动。
  • 覆盖空集合、最大合法键、重复写入和非法键等边界。
  • Java 微基准应使用 JMH 等专用框架,避免把 JVM 预热和编译优化误判为算法差异。

常见错误

  • 只看大 O 记号:两个期望 O(1)O(1) 的结构可能有显著不同的对象和缓存成本。修复方式是同时比较常数、内存和目标硬件上的实测结果。
  • 忽略数据特征变化:当前整数键有界,不代表未来接入的键仍然有界。应把键空间假设写入设计文档和监控指标。
  • 用平均延迟代替实时性结论:平均值可能掩盖扩容或回收造成的尖峰。需要同时检查高分位延迟和最坏业务场景。

本课练习

  1. 为“保存 500 万个商品 ID,并频繁判断是否已售罄”设计候选方案。分别讨论连续整数 ID 与 UUID 两种输入,给出首选结构、排除理由和需要验证的指标。
  2. 一个任务调度器需要频繁插入任务并获取最早截止任务。比较排序数组、TreeSet 和优先队列,写出操作频率假设与验收条件,要求结论能解释为何成员查询不是首要指标。

本课总结

  • 选型必须同时考虑数据规模、操作分布、内存、实时性和键特征。
  • 复杂度用于缩小候选范围,功能样例与基准测试用于验证真实可用性。
  • 任何选型结论都依赖明确假设,假设变化时应重新评估,而不是沿用旧方案。

下一课预告

下一阶段将把需求建模与选型方法应用到综合算法项目中,继续完成实现、测试、性能验证和验收闭环。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

算法与数据结构选型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通