来源：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

pip install numpy numba

使用方法

排序和访问

from fractalsort_cpu import fractalsort
import numpy as np

# 生成随机的 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()
assert np.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, 自动 lb
python test_fractalsort.py 20       # e=20, 自动 lb
python test_fractalsort.py 20 12    # 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 的完整多平台基准测试，请参阅论文。

复现基准测试

pip install numpy numba
python bench_frmw_io.py

许可证

MIT——详见 LICENSE 文件。