Kensler 的 permute()：不建表的随机顺序遍历
来源：andrew-helmer.github.io — 2026-11-11
📋 概述
想从长度为 n 的数组里随机不重复地取 k 个元素，常规做法是 Fisher-Yates 洗牌：O(n) 时间加 O(n) 内存，还得真造出洗牌后的数组。Andrew Kensler 的 permute() 把它压到 O(k) 时间、O(1) 内存——用哈希函数充当伪随机置换，第 i 个元素的下标可以随时算出，因此能在多线程、多机器上并行，也能对十亿级的库只取一万条而不做全表扫描。
🔑 核心要点
- Fisher-Yates 需要 O(n) 时间与 O(n) 内存，permute() 只要 O(k) 时间与 O(1) 内存
- 核心是把哈希函数当作伪随机置换，任意下标常数时间查询
- 不产生重复：每个输出下标唯一，等价于无放回抽样
- 典型场景是渲染时同时遍历成千上万个数组，或从超大库里抽小样本
- 中间方案是稀疏表版的增量 Fisher-Yates，仍需 O(k) 内存
- 它不是密码学安全的，作者只保证够用于渲染积分与一般统计
💡 金句
它把内存压到 O(1)，这已经是最好的可能。
← 返回 Lobsters 首页
👍 0
👎 0