数据结构与算法 / 系统课时

搭建算法练习环境

搭建算法练习环境

学习目标

  • 搭建统一的 Python 3 算法练习工程。
  • 理解算法实现、演示入口和自动测试之间的职责划分。
  • 掌握脚本运行、模块运行、单元测试和断点调试的基本方法。
  • 建立可重复验证的练习流程,避免只通过人工观察输出判断正确性。
  • 开发环境
    • Python 3
    • 编辑器或 IDE
    • 终端
  • 工程结构
    • algorithms
    • tests
    • README
  • 代码职责
    • 算法函数
    • 演示入口
    • 测试用例
  • 运行方式
    • 运行脚本
    • 运行模块
    • 运行全部测试
    • 运行单个测试
  • 调试方法
    • 打印中间状态
    • 断点调试
    • 查看调用栈
    • 检查变量变化
  • 验证流程
    • 编写实现
    • 编写测试
    • 运行测试
    • 修复问题
    • 保留回归用例

问题背景或应用场景

算法练习看起来只需要新建一个文件并运行,但如果没有统一环境,很快会出现以下问题:

  • 每个文件的目录结构不同。
  • 算法函数和演示代码混在一起。
  • 导入模块时意外执行打印逻辑。
  • 修改输入后无法确认旧功能是否仍然正确。
  • 只验证一个示例,没有覆盖边界输入。
  • 代码出错时只能反复添加打印语句。
  • 不同机器使用不同 Python 版本,结果不一致。
  • 测试依赖当前工作目录,换一个运行位置就失败。

成熟的算法练习工程应具备以下能力:

  1. 算法可以独立导入。
  2. 示例可以直接运行。
  3. 测试可以自动执行。
  4. 错误可以通过调试器定位。
  5. 新增算法时目录规则保持一致。
  6. 旧算法可以通过回归测试持续验证。

本课程统一使用 Python 3。Python 语法简洁,能够减少语言细节对算法理解的干扰,同时支持类型标注、标准测试框架和调试工具。

核心原理

1. 算法函数只负责计算

算法函数应尽量满足以下特点:

  • 输入通过参数传入。
  • 输出通过返回值给出。
  • 不依赖全局变量。
  • 不在函数内部读取终端输入。
  • 不在函数内部随意打印调试信息。
  • 不修改输入,除非函数契约明确说明。
  • 对异常输入有明确处理方式。

例如,线性查找函数只负责接收列表和目标值,并返回索引。

2. 演示入口只负责展示

演示入口用于准备示例数据、调用函数和打印结果。Python 中常用以下入口判断:

python
if __name__ == "__main__":
    main()

当文件被直接运行时,main 函数会执行;当文件被其他模块导入时,main 函数不会自动执行。这可以避免测试代码导入算法模块时产生无关输出。

3. 测试代码负责自动判断

单元测试不只是运行函数,而是自动比较实际结果与预期结果。一个测试通常包含三个阶段:

  1. 准备输入。
  2. 执行算法。
  3. 断言结果。

例如:

python
def test_target_exists(self) -> None:
    values = [12, 7, 19]
    result = linear_search(values, 19)
    self.assertEqual(2, result)

如果实际结果不是 2,测试会失败并报告位置。

4. 测试与演示的职责不同

演示代码回答“这个算法如何使用”。测试代码回答“这个算法是否满足约定”。

演示输出适合教学展示,但不能替代自动测试。人工观察容易漏掉错误,也不适合大量重复验证。

5. 调试器用于观察执行过程

断点调试可以:

  • 暂停在指定代码行。
  • 查看当前变量值。
  • 单步执行下一行。
  • 进入函数调用。
  • 返回上一层调用。
  • 查看调用栈。
  • 观察循环边界和索引变化。

对于二分查找、递归、链表操作等算法,断点调试比无目的打印更高效。

基础用法

1. 检查 Python 版本

bash
python --version

预期输出类似:

text
Python 3.11.9

如果系统使用 python3 命令:

bash
python3 --version

2. 创建项目目录

bash
mkdir data-structures-algorithms
cd data-structures-algorithms
mkdir algorithms
mkdir tests

创建空文件:

bash
touch algorithms/__init__.py
touch tests/__init__.py

Windows PowerShell 可以使用:

powershell
New-Item algorithms/__init__.py -ItemType File
New-Item tests/__init__.py -ItemType File

推荐目录:

text
data-structures-algorithms/
├── algorithms/
│   ├── __init__.py
│   └── linear_search.py
├── tests/
│   ├── __init__.py
│   └── test_linear_search.py
└── README.md

3. 运行单个模块

bash
python -m algorithms.linear_search

使用模块方式运行的好处是,Python 会按照项目根目录解析包路径。

4. 运行全部测试

bash
python -m unittest discover -s tests -v

参数含义:

  • discover:自动发现测试。
  • -s tests:从 tests 目录开始搜索。
  • -v:显示详细测试名称和结果。

5. 运行单个测试文件

bash
python -m unittest tests.test_linear_search -v

6. 运行单个测试方法

bash
python -m unittest tests.test_linear_search.LinearSearchTest.test_target_exists -v

完整可运行示例

文件 algorithms/linear_search.py:

python
from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")

def linear_search(values: Sequence[T], target: T) -> int:
    for index, value in enumerate(values):
        if value == target:
            return index

    return -1

def main() -> None:
    numbers = [12, 7, 19, 7, 25]
    names = ["Alice", "Bob", "Carol"]

    print(f"index of 19: {linear_search(numbers, 19)}")
    print(f"index of 8: {linear_search(numbers, 8)}")
    print(f"first index of 7: {linear_search(numbers, 7)}")
    print(f"index of Bob: {linear_search(names, 'Bob')}")

if __name__ == "__main__":
    main()

文件 tests/test_linear_search.py:

python
import unittest

from algorithms.linear_search import linear_search

class LinearSearchTest(unittest.TestCase):
    def test_target_exists(self) -> None:
        values = [12, 7, 19]
        self.assertEqual(2, linear_search(values, 19))

    def test_returns_first_match(self) -> None:
        values = [12, 7, 7, 25]
        self.assertEqual(1, linear_search(values, 7))

    def test_target_missing(self) -> None:
        values = [12, 7, 19]
        self.assertEqual(-1, linear_search(values, 8))

    def test_empty_input(self) -> None:
        self.assertEqual(-1, linear_search([], 8))

    def test_single_element_match(self) -> None:
        self.assertEqual(0, linear_search([8], 8))

    def test_single_element_missing(self) -> None:
        self.assertEqual(-1, linear_search([8], 9))

    def test_string_values(self) -> None:
        values = ["Alice", "Bob", "Carol"]
        self.assertEqual(1, linear_search(values, "Bob"))

    def test_input_is_not_modified(self) -> None:
        values = [3, 1, 2]
        original = values.copy()

        linear_search(values, 1)

        self.assertEqual(original, values)

if __name__ == "__main__":
    unittest.main()

运行演示:

bash
python -m algorithms.linear_search

运行测试:

bash
python -m unittest discover -s tests -v

预期输出

演示输出:

text
index of 19: 2
index of 8: -1
first index of 7: 1
index of Bob: 1

测试输出核心部分:

text
test_empty_input ... ok
test_input_is_not_modified ... ok
test_returns_first_match ... ok
test_single_element_match ... ok
test_single_element_missing ... ok
test_string_values ... ok
test_target_exists ... ok
test_target_missing ... ok

Ran 8 tests in 0.000s

OK

实际测试顺序和耗时可能因环境不同而变化,但最终应显示所有测试通过。

调试建议

调试线性查找时,可以在以下位置设置断点:

python
for index, value in enumerate(values):

每次暂停时观察:

  • index 当前是多少。
  • value 当前是什么。
  • target 是什么。
  • 条件 value == target 是否成立。
  • 何时执行 return。
  • 未命中时为什么返回 -1。

Tips

  • 从项目根目录运行模块和测试。
  • 算法文件名使用小写字母和下划线。
  • 测试文件名使用 test_ 前缀。
  • 测试类名表达被测试对象。
  • 测试方法名表达具体行为。
  • 一个测试尽量只验证一个核心行为。
  • 算法函数避免读取终端输入。
  • 演示输出和自动测试应同时保留。
  • 发现缺陷后,先写能复现缺陷的测试,再修改实现。
  • 使用类型标注帮助编辑器发现参数和返回值问题。
  • 不要让多个测试共享可变列表。
  • 测试失败时,先阅读实际值、预期值和调用栈。

常见错误

错误一:在错误目录运行

如果不在项目根目录运行,可能出现模块找不到。错误示例:

text
ModuleNotFoundError: No module named 'algorithms'

解决方法是回到包含 algorithms 和 tests 的根目录,再执行模块命令。

错误二:缺少入口判断

如果直接在文件顶层调用 main,导入模块时也会执行打印逻辑,导致测试输出混乱。

错误三:只打印结果,不写断言

打印只能帮助观察,无法自动判断正确性。

错误四:测试依赖执行顺序

每个测试都应独立准备数据,不能假设另一个测试已经执行。

错误五:测试名称过于模糊

例如 test_1 无法说明失败原因。应使用 test_target_missing 这类名称。

错误六:在算法函数中混入输入输出

如果函数内部调用 input 或 print,复用和测试都会变得困难。

错误七:使用错误的 Python 解释器

编辑器选择的解释器和终端执行的解释器可能不同。需要确认两者使用同一 Python 3 环境。

本课练习

  1. 新增 algorithms/count_even.py,实现统计偶数数量。
  2. 新增 tests/test_count_even.py,覆盖空列表、全偶数、全奇数和混合数据。
  3. 为线性查找增加元组输入测试。
  4. 故意把返回值 -1 修改为 0,观察哪些测试失败。
  5. 使用断点调试线性查找未命中的过程。
  6. 增加一个测试,验证重复值时返回第一次出现的位置。
  7. 将项目提交到 Git,并为每个算法保留独立提交记录。
  8. 在 README.md 中记录运行命令和测试命令。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

搭建算法练习环境

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通