dv-homework-2/report.md

第二讲大作业实验报告：海量 float32 索引排序算法设计与实现

1. 数据生成或来源

本实验使用纯 Python + NumPy 生成两类 float32 数据作为评测输入：

• uniform：使用随机均匀分布生成数据
• clustered：使用三段高斯混合分布生成数据

实验中所有数据都在本地实时生成，不依赖外部数据集。测试类型和规模如下：

• 数据类型：float32
• 数据分布：uniform, clustered
• 数据规模：10,000,000
• 每组重复次数：1

2. NumPy原生argsort性能基准测试

NumPy 原生基准作为参考上界，使用 stable 模式执行。结果如下：

数据分布	规模	平均耗时/s	标准差/s
clustered	10,000,000	1.5460	0.0000
uniform	10,000,000	1.4686	0.0000

从基准可以看到，在千万级规模下，NumPy 官方实现仍然非常高效，是后续自定义算法的核心对照对象。

3. 算法原理（含图）

3.1 方案一：浮点数位级 LSD Radix Sort

将 float32 视图解释为 uint32，并进行单调映射：

• 负数：key = ~raw_bits
• 非负数：key = raw_bits ^ 0x80000000

然后执行 4 趟 8-bit 稳定分发（shift = 0, 8, 16, 24）得到最终索引。

3.2 方案二：多级直方图 + Bucket Sort

从最高字节开始进行分桶，再对每个非平凡桶递归下钻，直到桶规模低于阈值后使用插入排序收尾。该策略能在分布相对分散时减少不必要搬运，但在桶不均衡时会出现局部退化。

4. 核心代码实现（分函数写）

主要函数划分如下：

1. float32_to_ordered_uint32：完成浮点到可比较无符号键的映射
2. stable_digit_scatter：实现单趟稳定计数分发
3. argsort_float32_radix：实现 4-pass LSD Radix 索引排序
4. argsort_float32_bucket：实现 MSD 多级分桶 + 小桶插入排序
5. run_benchmarks：完成对照组与实验组计时与统计

正确性检查结论：共验证 12 组算法/数据组合，其中 12 组通过排序正确性检查，12 组与 stable numpy argsort 索引完全一致。

5. 实验环境与结果（多组数据对比表 + 图）

实验环境：

• Python：3.12.3
• NumPy：2.4.3
• 平台：Linux-6.17.0-14-generic-x86_64-with-glibc2.39
• 逻辑 CPU 数：6

最终多组数据汇总如下：

数据分布	算法	规模	平均耗时/s	标准差/s	相对 numpy
clustered	bucket_msd	10,000,000	60.2848	0.0000	38.99x
clustered	numpy_argsort	10,000,000	1.5460	0.0000	1.00x
clustered	radix_lsd	10,000,000	27.4960	0.0000	17.79x
uniform	bucket_msd	10,000,000	64.0348	0.0000	43.60x
uniform	numpy_argsort	10,000,000	1.4686	0.0000	1.00x
uniform	radix_lsd	10,000,000	26.0530	0.0000	17.74x

图4给出最终性能对比柱状图（对数纵轴）：

图6给出不同算法在规模变化下的运行时间曲线：

图7给出相对 NumPy argsort 的性能倍率：

6. 性能分析与瓶颈讨论

1. 在千万级输入上，NumPy 原生 argsort 仍保持明显优势。
2. Radix 路线的理论复杂度接近 O(n)，但纯 NumPy 稳定散射的常数项较高，且强依赖内存带宽。
3. Bucket 路线在数据分布集中时更容易出现不均衡桶，导致局部处理时间上升。
4. 当前实现的主要瓶颈在于大规模数据搬运和块内前缀计算；若引入低层并行或 JIT，有机会继续压缩差距。

7. 总结与展望

本实验已按课程要求完成两条实现路径、千万级数据基准、图1-图7可视化与完整报告自动生成流程。结论如下：

1. 在禁止直接调用 np.sort 和 np.argsort 的约束下，两条方案都可得到正确排序索引。
2. 千万级规模下，自定义纯 NumPy 实现可以稳定运行，但性能与官方底层优化实现仍存在差距。
3. 后续可尝试方向包括：减少中间数组写放大、优化桶阈值自适应策略、采用更底层 SIMD/JIT 机制。

复现实验：

1. source venv/bin/activate
2. pip install -e .
3. python scripts/run_all.py