算法单元测试与小规模暴力对拍器（test_algorithms.html）

1 · 功能说明与手机端直读指南

使用 Python 标准库 unittest 编写的自动化对拍测试集：将二分搜索与 bisect_left 对拍、将 0-1 背包 DP 与 2^n 子集暴力枚举对拍、将贪心活动选择与全子集相容性检查对拍，并验证 n 皇后（1~8 皇后解数 1,0,0,2,10,4,40,92）与 Edmonds–Karp 最大流。

  1import unittest, random, sys, itertools
  2from pathlib import Path
  3from bisect import bisect_left
  4
  5sys.path.insert(0, str(Path(__file__).resolve().parents[1]))
  6from practice_algorithms import (
  7    lower_bound,
  8    merge_sort,
  9    count_inversions,
 10    quick_select,
 11    matrix_chain_order,
 12    lcs_length,
 13    max_subarray,
 14    knapsack_01,
 15    optimal_bst,
 16    activity_selection,
 17    weighted_interval_scheduling,
 18    dijkstra,
 19    n_queens,
 20    knapsack_branch_and_bound,
 21    edmonds_karp,
 22    vertex_cover_approx,
 23)
 24
 25
 26class TestAlgorithms(unittest.TestCase):
 27    def test_binary_and_sort(self):
 28        r = random.Random(41)
 29        for n in range(30):
 30            a = sorted(r.randrange(-10, 11) for _ in range(n))
 31            self.assertEqual(merge_sort(a), a)
 32            for x in range(-11, 12):
 33                self.assertEqual(lower_bound(a, x), bisect_left(a, x))
 34
 35    def test_inversions_and_quick_select(self):
 36        r = random.Random(19)
 37        for n in range(1, 20):
 38            arr = [r.randrange(-15, 16) for _ in range(n)]
 39            brute_inv = sum(
 40                1 for i in range(n) for j in range(i + 1, n) if arr[i] > arr[j]
 41            )
 42            self.assertEqual(count_inversions(arr), brute_inv)
 43            s = sorted(arr)
 44            for k in range(n):
 45                self.assertEqual(quick_select(arr, k), s[k])
 46
 47    def test_matrix_chain_and_obst_and_kadane(self):
 48        self.assertEqual(matrix_chain_order([30, 35, 15, 5, 10, 20, 25]), 15125)
 49        self.assertEqual(max_subarray([-2, 11, -4, 13, -5, -2]), 20)
 50        p = [0.15, 0.10, 0.05, 0.10, 0.20]
 51        q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
 52        self.assertAlmostEqual(optimal_bst(p, q), 2.75, places=6)
 53
 54    def test_lcs(self):
 55        self.assertEqual(lcs_length('ABCBDAB', 'BDCABA'), 4)
 56        self.assertEqual(lcs_length('', 'abc'), 0)
 57
 58    def test_knapsack_bruteforce_and_bb(self):
 59        r = random.Random(7)
 60        for n in range(1, 9):
 61            w = [r.randint(1, 8) for _ in range(n)]
 62            v = [r.randint(1, 19) for _ in range(n)]
 63            for capacity in range(14):
 64                brute = max(
 65                    (
 66                        sum(v[i] for i in range(n) if mask >> i & 1)
 67                        for mask in range(1 << n)
 68                        if sum(w[i] for i in range(n) if mask >> i & 1) <= capacity
 69                    ),
 70                    default=0,
 71                )
 72                self.assertEqual(knapsack_01(w, v, capacity), brute)
 73                self.assertEqual(knapsack_branch_and_bound(w, v, capacity), brute)
 74
 75    def test_activity_and_weighted_interval(self):
 76        a = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
 77        self.assertEqual(len(activity_selection(a)), 4)
 78        w_jobs = [(1, 4, 5), (3, 5, 1), (0, 6, 8), (4, 7, 4), (3, 8, 6), (5, 9, 3), (6, 10, 2), (8, 11, 4)]
 79        self.assertEqual(weighted_interval_scheduling(w_jobs), 13)
 80
 81    def test_dijkstra(self):
 82        self.assertEqual(dijkstra([[(1, 1), (2, 4)], [(2, 2)], []], 0), [0, 1, 3])
 83        with self.assertRaises(ValueError):
 84            dijkstra([[(0, -1)]], 0)
 85
 86    def test_queens(self):
 87        self.assertEqual([len(n_queens(n)) for n in range(1, 9)], [1, 0, 0, 2, 10, 4, 40, 92])
 88
 89    def test_max_flow_and_vc_approx(self):
 90        c = [
 91            [0, 16, 13, 0, 0, 0],
 92            [0, 0, 10, 12, 0, 0],
 93            [0, 4, 0, 0, 14, 0],
 94            [0, 0, 9, 0, 0, 20],
 95            [0, 0, 0, 7, 0, 4],
 96            [0, 0, 0, 0, 0, 0],
 97        ]
 98        self.assertEqual(edmonds_karp(c, 0, 5), 23)
 99        edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
100        cov = set(vertex_cover_approx(edges))
101        self.assertTrue(all(u in cov or v in cov for u, v in edges))
102
103
104if __name__ == &#x27;__main__':
105    unittest.main()

3 · 核心实现要点与复杂度对照

被测核心算法源码请查看：🐍 Python 算法核心模板库（practice_algorithms.html）。