# pytest-algorithm

**Repository Path**: alwarse/pytest-algorithm

## Basic Information

- **Project Name**: pytest-algorithm
- **Description**: 成功创建了 pytest-benchmark + 资源监控的完整集成方案
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2025-07-15
- **Last Updated**: 2025-07-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 字符串排列算法实现与性能测试

这个项目实现了多种字符串排列算法，并提供了详细的性能测试和复杂度分析。

## 📁 项目结构

```
py/
├── string_permutation.py    # 核心算法实现
├── performance_test.py      # 自定义性能测试类
├── benchmark_test.py        # pytest-benchmark 基准测试
├── memory_profile_test.py   # memory_profiler 内存分析
├── timeit_test.py          # timeit 精确时间测试
├── cprofile_test.py        # cProfile 性能分析
├── run_tests.py            # 统一测试运行器
├── requirements.txt        # 依赖管理
├── pytest.ini             # pytest 配置
└── README.md               # 项目说明
```

## 🔧 测试框架对比

| 测试框架 | 用途 | 优势 | 适用场景 |
|----------|------|------|----------|
| 🏠 自定义测试 | 基础性能测试 | 简单直观，无依赖 | 快速验证，教学演示 |
| ⚡ pytest-benchmark | 专业基准测试 | 统计准确，报告丰富 | 正式性能评估 |
| 💾 memory_profiler | 内存分析 | 逐行内存监控 | 内存优化分析 |
| ⏱️ timeit | 精确计时 | 高精度，多次测量 | 微观性能对比 |
| 🔬 cProfile | 详细性能分析 | 函数级分析，调用栈 | 性能瓶颈定位 |

## 🔧 算法实现

项目实现了5种不同的字符串排列算法：

### 1. 📚 递归方法 (`permute_recursive`)
- **算法思想**: 经典递归分治
- **时间复杂度**: O(n! × n)
- **空间复杂度**: O(n! × n) + O(n) [递归栈]
- **特点**: 最直观易懂，适合教学

### 2. ⚡ 迭代方法 (`permute_iterative`)
- **算法思想**: 使用 `itertools.permutations`
- **时间复杂度**: O(n!)
- **空间复杂度**: O(n! × n)
- **特点**: 性能最优，生产环境推荐

### 3. 📖 字典序法 (`permute_lexicographic`)
- **算法思想**: 按字典序生成下一个排列
- **时间复杂度**: O(n! × n)
- **空间复杂度**: O(n! × n) + O(n)
- **特点**: 有序输出，适合需要字典序的场景

### 4. 🔧 Heap算法 (`permute_heap`)
- **算法思想**: Heap's algorithm
- **时间复杂度**: O(n!)
- **空间复杂度**: O(n! × n) + O(n)
- **特点**: 经典高效算法

### 5. 🔄 生成器法 (`permute_generator`)
- **算法思想**: 基于字典序的生成器实现
- **时间复杂度**: O(n × k)，k为已生成的排列数
- **空间复杂度**: O(n) [仅存储当前排列]
- **特点**: 内存最优，按需生成

## 🚀 使用方法

### 📦 安装依赖

```bash
# 基础功能（无需额外依赖）
python string_permutation.py

# 安装所有测试依赖
pip install -r requirements.txt

# 或单独安装核心测试依赖
pip install pytest pytest-benchmark memory-profiler psutil
```

### 🎯 快速开始

```bash
# 交互式测试菜单
python run_tests.py

# 基本算法演示
python run_tests.py demo

# 自定义性能测试
python run_tests.py custom
```

### 🔧 专业性能测试

#### 1. pytest-benchmark 基准测试
```bash
# 基本基准测试
pytest benchmark_test.py -v --benchmark-only

# 按性能排序
pytest benchmark_test.py --benchmark-sort=mean

# 生成JSON报告
pytest benchmark_test.py --benchmark-json=results.json

# 生成性能直方图
pytest benchmark_test.py --benchmark-histogram

# 与基线比较
pytest benchmark_test.py --benchmark-compare=baseline.json
```

#### 2. 内存分析
```bash
# 基本内存分析
python memory_profile_test.py

# 使用 memory_profiler
python -m memory_profiler memory_profile_test.py

# 生成内存使用图表
mprof run memory_profile_test.py
mprof plot
```

#### 3. 精确时间测试
```bash
# timeit 精确计时
python timeit_test.py
```

#### 4. 详细性能分析
```bash
# cProfile 分析
python cprofile_test.py

# 命令行分析
python -m cProfile -s cumtime cprofile_test.py

# 交互式分析
python -m pstats profile_递归方法.prof

# 可视化分析（需要安装 snakeviz）
pip install snakeviz
snakeviz profile_递归方法.prof
```

### 🎮 测试运行器选项

```bash
python run_tests.py          # 交互式菜单
python run_tests.py demo     # 基本演示
python run_tests.py custom   # 自定义性能测试  
python run_tests.py pytest   # pytest 基准测试
python run_tests.py memory   # 内存分析
python run_tests.py timeit   # 精确时间测试
python run_tests.py cprofile # 性能分析
python run_tests.py all      # 运行所有测试
python run_tests.py advanced # 显示高级命令
```
```python
from string_permutation import (
    permute_recursive,
    permute_iterative,
    permute_lexicographic,
    permute_heap,
    permute_generator
)

# 使用递归方法
result = permute_recursive("abc")
print(result)  # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

# 使用生成器（内存友好）
for perm in permute_generator("abc"):
    print(perm)
```

## 📊 性能测试特性

### 🔍 测试内容
- **执行时间测量**: 使用 `time.perf_counter()` 高精度计时
- **内存使用追踪**: 使用 `tracemalloc` 监控内存使用
- **智能单位显示**: 自动选择最合适的时间和内存单位
- **理论复杂度对比**: 显示理论和实际性能差异

### 📈 测试结果示例
```
测试字符串: 'abcd' (长度: 4)
理论时间复杂度: O(n!) = O(4!) = 24
理论空间复杂度: O(n!) = O(4!) = 24

测试 迭代方法...
  结果数量: 24
  执行时间: 42.200 微秒
  峰值内存: 1.59 KB
  当前内存: 1.45 KB

性能比较:
  迭代方法: 1.00x (基准)
  Heap算法: 1.24x
  字典序法: 3.43x
  递归方法: 4.61x

最快算法: 迭代方法
最省内存算法: 字典序法
```

### 💾 生成器优势演示
特别展示了生成器在处理大数据集时的内存优势：
- 一次性生成720个排列：39.16 KB
- 生成器处理100个排列：983字节 (**节省40倍内存**)

## 🎯 使用建议

| 场景 | 推荐算法 | 原因 |
|------|----------|------|
| 🔹 小规模数据(n ≤ 8) | 任何算法 | 性能差异不明显 |
| 🔸 中等规模数据(8 < n ≤ 10) | 迭代方法/Heap算法 | 高性能 |
| 🔶 大规模数据(n > 10) | 考虑是否真需要所有排列 | 组合爆炸问题 |
| 💾 内存敏感场景 | 生成器法 | 按需生成，内存最优 |
| 📚 字典序要求 | 字典序法 | 有序输出 |
| 🎓 教学目的 | 递归方法 | 最直观易懂 |
| 🔍 查找特定排列 | 生成器法 | 可提前终止 |
| ⚡ 高性能要求 | 迭代方法 | 库函数优化 |

## 🔬 技术细节

### 时间单位自动选择
- **微秒级** (< 1毫秒): `24.400 微秒`
- **毫秒级** (1毫秒 - 1秒): `1.203 毫秒`
- **秒级** (≥ 1秒): `1.234 秒`

### 内存单位自动选择
- **字节级** (< 1KB): `318.00 字节`
- **KB级** (1KB - 1MB): `7.84 KB`
- **MB级** (≥ 1MB): `1.25 MB`

## 📦 依赖要求

- Python 3.6+
- 标准库模块：
  - `itertools` (迭代方法)
  - `time` (性能测量)
  - `tracemalloc` (内存追踪)
  - `math` (阶乘计算)

## 🚀 扩展性

项目采用模块化设计，易于扩展：
1. 在 `string_permutation.py` 中添加新的排列算法
2. 在 `performance_test.py` 中的算法字典中注册新算法
3. 新算法会自动被纳入性能测试框架

## 📚 学习价值

这个项目非常适合：
- 学习不同的排列生成算法
- 理解算法的时间和空间复杂度
- 掌握Python性能测试技巧
- 了解生成器的内存优化原理
- 实践模块化代码设计

## 🔍 相关概念

- **排列 (Permutation)**: 从n个不同元素中取出m个元素的所有不同排列
- **时间复杂度**: 算法执行时间随输入规模增长的趋势
- **空间复杂度**: 算法使用内存随输入规模增长的趋势
- **生成器 (Generator)**: Python中的惰性计算机制，按需生成数据
- **字典序**: 按照字典中单词排列顺序的比较方法