所有对拍均使用固定种子 20261121ULL,运行通过
ASan + UBSan 检查。
interval_dp.cpp:交叉验证矩阵链乘(含 CLRS 6 矩阵 15125 与 4 矩阵 9375)、最优 BST(修正hi上界后的 Knuth \(O(n^2)\) 优化 vs \(O(n^3)\))、环形断链2n石子合并、以及线性石子合并 vs Garsia-Wachs \(O(n \log n)\);统计 OBST 内层根枚举次数并加锁测量标准dp[k+1][j]与转置布局dpT[j][k+1]5 次运行的中位数耗时到results/interval_bench.csv。plot_interval.py:生成../interval-layout-bench.svg。- 运行方式:
bash run.sh源码下载
本文相关源码已整理,共 3 个文件。