A+B 问题：算法性能对比研究
下载链接：https://chenyuheee.github.io/blog/notes/FDS/hard/submission.zip
研究目标：对比两种求解两数之和问题的算法的实际性能差异：
- 算法 1：暴力穷举 (O(N²))
- 算法 2：排序+双指针 (O(N log N))
系统要求
项目已在 macOS 环境验证；Linux/Windows 可按下列等价命令复现。
- 编译器：
gcc（或其他支持 C11 的兼容编译器） - Python 3（用于绘图，可选）
- pdflatex（用于编译报告，可选；PDF 已预编译）
快速开始
在项目根目录执行以下命令：
bash
# 1. 编译基准测试程序
gcc src/test.c -O0 -std=c11 -Wall -Wextra -o build/test_bench
# 2. 生成基准数据（预计耗时：1-2 分钟）
./build/test_bench 1000 42 > data/results_v1000.csv
./build/test_bench 10000 42 > data/results_v10000.csv
./build/test_bench 100000 42 > data/results_v100000.csv
# 3. 合并结果
{ head -n 1 data/results_v1000.csv; tail -n +2 data/results_v*.csv; } > data/results.csv
# 4. （可选）使用 matplotlib 生成性能对比图
python3 src/graph.py --input data/results.csv --out-dir figures --format png
# 5. 查看编译后的报告（按系统选择其一）
open report/report.pdf # macOS
# xdg-open report/report.pdf # Linux
# start report/report.pdf # Windows (PowerShell/CMD)目录结构
.
├── src/ # 源代码
│ ├── main.c # 交互式版本（手动测试用）
│ ├── test.c # 基准测试程序（8个N值 × 3个V值）
│ └── graph.py # 绘图脚本（基于 matplotlib）
├── data/ # 原始基准测试结果
│ ├── problem.txt # 原题目描述
│ ├── results_v1000.csv # V=1000 的结果（8行）
│ ├── results_v10000.csv # V=10000 的结果（8行）
│ ├── results_v100000.csv # V=100000 的结果（8行）
│ └── results.csv # 合并结果（24行）
├── figures/ # 生成的性能对比图
│ ├── runtime_V1000.png # V=1000 对比图
│ ├── runtime_V10000.png # V=10000 对比图
│ └── runtime_V100000.png # V=100000 对比图
├── report/ # 报告文件
│ ├── report.tex # LaTeX 源文件（供参考）
│ └── report.pdf # 编译后的最终报告（当前版本 3 页）
├── build/ # 编译后的可执行文件
│ └── test_bench # 基准测试可执行程序
└── README.md # 本文件算法实现
| 算法 | 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|---|
| 1 | 暴力穷举 O(N²) | O(N²) | O(1) | 嵌套循环枚举所有数对 |
| 2 | 排序+双指针 | O(N log N) | O(N) | 使用辅助数组备份 |
基准数据格式
每个 CSV 文件的结构如下：
V,N,K1,func1_time,K2,func2_time
1000,1000,1,0.000207000,1,0.000059000
...列的含义：
- V：数值范围 [2, V]
- N：数组元素个数
- K1, K2：每个算法的重复次数（自动选择以达到 ≥10 个 clock ticks）
- func1_time：算法 1 的平均执行时间（秒）
- func2_time：算法 2 的平均执行时间（秒）
预期输出文件
运行完所有步骤后，应该生成以下文件：
| 文件 | 说明 | 行数 |
|---|---|---|
data/results.csv | 合并后的基准数据 | 1 个表头 + 24 行数据 |
figures/runtime_V*.png | 3 张性能对比图 | — |
report/report.pdf | 正式报告（页数可能随排版微调） | — |
数据验证：
bash
# 检查行数
wc -l data/results.csv # 应显示 25（1 个表头 + 24 行数据）
# 查看前几行结果
head -n 3 data/results.csv
# 预期加速比（算法 1 vs 算法 2）：
# ~100-400 倍，取决于 N 和 V 的大小实现细节
测试数据生成
- 随机值：均匀分布在 [2, V] 范围内
- 保证的解：最后两个元素都是 1，保证和为 2
- 目的：避免最佳情况偏差（解在数组开头）
计时方法
- 使用 C 标准库的
clock()函数 - 自适应 K 选择：K 从 1 开始，每次翻倍，直到经历 ≥10 个 ticks
- 目的：根据题目要求达到 ≥10% 的测量精度
- 公式：平均时间 = (总 ticks / K) / CLOCKS_PER_SEC
关键特性
- 两个算法操作相同的测试数据（无输入偏差）
- 算法 2 使用备份数组（
memcpy）以保护原始数据 - 测量不包括内存分配/释放的开销
- 在
-O0编译下，编译器通常不会把函数调用优化掉
常见问题与解决方案
| 问题 | 解决方案 |
|---|---|
| "command not found: gcc" | 安装编译器：brew install gcc（macOS）或 apt install build-essential（Ubuntu） |
| "No module named 'matplotlib'" | 安装：pip3 install matplotlib（可选，仅用于绘图） |
| "pdflatex: command not found" | 安装：brew install basictex（macOS）或 apt install texlive-latex-base（Ubuntu） |
| "Memory error for large N" | 增加系统内存或减小 N 值 |
| 结果与示例不同 | CPU 负载导致的正常波动；检查 K 值是否 ≥1 |
报告结构
编译后的 report/report.pdf 包含：
- 第 1 章：问题描述与算法设计
- 第 2 章：复杂度分析、实验设置、结果、可视化图表及讨论
说明：LaTeX 源文件（report.tex）用于追踪排版与内容来源；peer review 可直接基于仓库现有数据与 PDF 完成复核。
注意事项与提示
- 随机数种子：使用 seed=42 可确保测试数据的可重复性
- 运行时间：完整基准测试（三个 V 值）通常需要 1-2 分钟
- 性能图表：
figures/中的三张 PNG 图表清晰展示算法 2（对数坐标）相比算法 1 的性能优势 - CSV 格式：结果格式清晰易读，便于导入 Excel 或 Python 进行进一步分析
如有疑问，请参考 data/problem.txt 中的原题目描述。