DeepSeek总结的一种带宽高效的压缩基数排序FractalSortCPU
来源：https://github.com/mikdangana/fractalsort_cpu
FractalSortCPU
一种带宽高效的压缩基数排序，在各大平台上均优于最先进的排序算法。
在 16GB 数据集规模下，FractalSortCPU 实现了 0.92 的带宽效率——相比之下，Bonsai 为 0.34，Timsort 为 0.25，PARADIS 为 0.11，HRS/SampleSort 为 0.05。这意味着根据基线不同，带宽利用率提高了 2-18 倍，与先前规模最大的 CPU 结果相比，提升了 6 倍。
论文:FractalSortCPU: 基于 CPU 的带宽高效压缩基数排序 (arXiv:2605.10390v2, 2026 年 5 月)
主要结果
| 平台 | 先前最佳工作 | FractalSortCPU | 提升 |
|---|---|---|---|
| CPU | HRS, SampleSort, PARADIS | FractalSortCPU | 最高 6 倍 |
| GPU | 设备级基数排序 | FractalSortCPU | 最高 3 倍 |
| FPGA | 定制加速器 | FractalSortCPU | 最高 2.5 倍 |
已在 16 位精度、512MB 至 32GB 的数据集上得到验证。
关于项目
FractalSort 算法最初为 FPGA/硬件加速器设计，此为 FractalSort 的 CPU 适配版本，旨在将其引入 CPU 以提高可访问性并便于更广泛的实验。它使用直方图合并树索引进行排序和查询/检索，通过将键分解为基于 MSB 的容器，并包含紧凑条目和每批排序运行，实现了比基数排序更低的 DRAM 带宽。
架构
FractalSort 将每个 p 位键分解为两个部分：
key (p bits): ├─ top (ln-lb) bits → bin_id (MSB, 决定属于哪个容器) └─ bottom entry_bits → entry (lb + (p-ln) bits, 每个键存储)其中ln = ceil(log2(n))，lb控制容器大小，entry_bits = lb + (p - ln)。
对于小精度 (p <= 20)，使用直接直方图模式——不使用容器或分散，只是一个具有O(n + 2^p)重建的计数直方图。
阶段
- 处理：单次直接分散。对于每个键，从 MSB 提取
bin_id，从剩余位提取entry。将entry写入sbatch_mem中该容器对应的区域。键按批次处理，每批为每个容器生成一个排序后的运行。 - 排序：对每批中每个容器内的
entry进行基数排序（对于小型容器也可用插入排序）。排序后的运行被连接起来——不需要全局索引数组。 - 获取项：在容器计数上通过线段树查找找到目标容器（
O(log n_bins)）。通过二分搜索在排序后的运行中进行 K 路选择，以找到目标排名位置的entry。将键重建为(bin_id << entry_bits) | entry。 - 全部重建：对所有容器中的排序后运行进行 K 路合并，以生成完整的排序输出。
最优lb选择
lb参数控制容器数量和条目大小之间的权衡。
| 规则 | 容器数 | 使用场景 |
|---|---|---|
lb = e - 10 | 1024 | 当e <= 20时的默认值 |
lb = e - 6 | 64 | 当e > 20时的默认值，容器数更少 |
要求
- Python 3.8+
- NumPy
- Numba
pipinstallnumpy numba使用方法
排序和访问
fromfractalsort_cpuimportfractalsortimportnumpyasnp# 生成随机的 32 位键keys=np.random.randint(0,2**32,size=1_000_000,dtype=np.uint32)# 排序 (首次调用包含 JIT 编译)result=fractalsort(keys,p=32,lb=12)# 按位置访问排序后的键smallest=result[0]largest=result[-1]median=result[len(result)//2]# 重建所有排序后的键sorted_keys=result.reconstruct_all()assertnp.array_equal(sorted_keys,np.sort(keys))参数
result=fractalsort(keys,# uint32 类型的键数组p=32,# 键的精度（位数）lb=None,# log2(容器大小), 默认值: e-10 (当 e<=20) 或 e-6 (当 e>20)n_batches=4,# 处理批次 (用于流式处理))结果对象
result.get_item(position)# 点查询: O(log bins + k*log(bin_size))result[i]# 通过 __getitem__ 实现相同功能result[10:20]# 切片访问len(result)# 键的总数result.reconstruct_all()# 按排序顺序返回所有键内部数组（供高级使用）
result.sbatch_mem# 条目数组 (每个容器的区域，排序后的运行)result.bin_counts# 每个容器的条目数result.bin_cumulative# 每个容器的累积起始位置result.batch_boundaries# [n_bins, n_batches+1] 每个容器的每批运行边界result.n_batches# 批次数量result.ln# 树深度result.lb# log2(容器大小)result.entry_bits# 每个条目的位数result.n_bins# 容器数量result.seg_tree# 用于 O(log n_bins) 容器查找的线段树测试
python test_fractalsort.py[e][lb]示例:
python test_fractalsort.py# e=18, 自动 lbpython test_fractalsort.py20# e=20, 自动 lbpython test_fractalsort.py2012# e=20, lb=12性能
吞吐量 (单核, Numba JIT, p=32)
| 数据集 | n | FractalSort (百万键/秒) | 基数排序 (百万键/秒) | 加速比 |
|---|---|---|---|---|
| 1 MB | 262K | 124 | 57 | 2.2 倍 |
| 16 MB | 4.2M | 76 | 59 | 1.3 倍 |
| 64 MB | 16.8M | 98 | 67 | 1.5 倍 |
| 256 MB | 67.1M | 122 | 71 | 1.7 倍 |
| 4 GB | 1.07B | 78 | 43 | 1.8 倍 |
在这个单核 Python/Numba 配置中，FractalSortCPU 在所有数据集大小上均更快。其带宽效率优势在更大规模下进一步增长——有关高达 32GB 的完整多平台基准测试，请参阅论文。
复现基准测试
pipinstallnumpy numba python bench_frmw_io.py许可证
MIT——详见 LICENSE 文件。