個(gè)人項(xiàng)目報(bào)告

項(xiàng)目	內(nèi)容
這個(gè)作業(yè)屬于哪個(gè)課程	[軟件工程](首頁(yè) - 計(jì)科23級(jí)12班 - 廣東工業(yè)大學(xué) - 班級(jí)博客 - 博客園)
這個(gè)作業(yè)要求在哪里	[作業(yè)要求](個(gè)人項(xiàng)目 - 作業(yè) - 計(jì)科23級(jí)12班 - 班級(jí)博客 - 博客園)
這個(gè)作業(yè)的目標(biāo)	訓(xùn)練個(gè)人項(xiàng)目軟件開(kāi)發(fā)能力，學(xué)會(huì)使用性能測(cè)試工具和實(shí)現(xiàn)單元測(cè)試

一、代碼組織與模塊設(shè)計(jì)

1. 模塊劃分與函數(shù)職責(zé)（函數(shù)式模塊化）

模塊	函數(shù)/組件	職責(zé)
文件處理模塊	load_text / only_name / save_line_append（io_utils.py）	讀取/寫(xiě)入文本（UTF-8 優(yōu)先，GBK 回退），抽取文件名，結(jié)果追加寫(xiě)入
核心算法模塊	lcs_length / lcs_similarity_pct（algos.py）	計(jì)算 LCS 長(zhǎng)度與相似度（百分比，抄襲文本長(zhǎng)度為分母）
流程控制模塊	run_once / main（runner.py）	解析命令行參數(shù)、協(xié)調(diào) I/O 與算法、統(tǒng)一輸出格式
評(píng)測(cè)兼容入口	main.py	只做轉(zhuǎn)發(fā)到 runner.main，兼容評(píng)測(cè)機(jī)命令

Gitnub倉(cāng)庫(kù)鏈接：https://github.com/fanqieren123-wq/3123004591

2. 類(lèi)與函數(shù)關(guān)系圖

main.py
└─> runner.main()
├─> run_once()
│ ├─> io_utils.load_text()
│ ├─> algos.lcs_length()
│ └─> io_utils.save_line_append()
└─> argparse 解析

二、算法關(guān)鍵實(shí)現(xiàn)（LCS）

核心轉(zhuǎn)移方程

dp[i][j] = {
    dp[i-1][j-1] + 1,            if a[i-1] == b[j-1]
    max(dp[i-1][j], dp[i][j-1]), otherwise
}

空間優(yōu)化：滾動(dòng)數(shù)組（algos.py:lcs_length）

prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
    ai = a[i - 1]
    for j in range(1, n + 1):
        if ai == b[j - 1]:
            curr[j] = prev[j - 1] + 1
        else:
            curr[j] = max(curr[j - 1], prev[j])
    prev, curr = curr, [0] * (n + 1)

進(jìn)一步優(yōu)化：讓較短的字符串做“列”(n)，減少數(shù)組長(zhǎng)度與緩存壓力。
中文處理：相似度基于字符級(jí)，天然兼容中文字符。

---

三、設(shè)計(jì)獨(dú)到之處

• 內(nèi)存效率優(yōu)化：滾動(dòng)數(shù)組 + 短串做列，顯著降低空間開(kāi)銷(xiāo)與 cache miss。

• 魯棒性設(shè)計(jì)：

  • load_text：UTF-8 優(yōu)先、GBK 回退，不拋異常。
  • 空文件直接輸出 0.00%。
  • runner.main 捕獲異常返回碼，避免評(píng)測(cè)崩潰。

• 輸出友好：統(tǒng)一由 format_result_line 生成固定兩位小數(shù)的英文描述，與評(píng)測(cè)一致。

---

四、計(jì)算模塊接口部分的性能改進(jìn)實(shí)踐

1. 基線性能與瓶頸

• 固定輸入：data/orig_1.txt 與 data/copy_1.txt

• 命令：

  Measure-Command { python main.py data/orig_1.txt data/copy_1.txt result.txt }
  

• 基線耗時(shí)：填寫(xiě)你的實(shí)際秒數(shù)

• 性能畫(huà)像：cProfile → SnakeViz/VS，熱點(diǎn)集中在 algos.lcs_length 的雙重循環(huán)。

2. 優(yōu)化策略與實(shí)現(xiàn)

優(yōu)化方向	具體措施	效果
算法內(nèi)存	2D 表 → 滾動(dòng)數(shù)組；短串做列	空間從 O(m·n) 降到 O(min(m, n))
內(nèi)存訪問(wèn)	行內(nèi)順序訪問(wèn)、局部性更好	減少 cache miss，時(shí)間下降
I/O 穩(wěn)定性	UTF-8 優(yōu)先 + GBK 回退	兼容不同編碼，避免崩潰

關(guān)鍵代碼（內(nèi)存復(fù)用）：

prev, curr = curr, [0] * (n + 1)

3. 性能分析圖與最耗時(shí)函數(shù)

• 工具：Visual Studio 2017 / SnakeViz

• 視圖：Functions / Call Tree（按 Inclusive Time 排序）

• 最耗時(shí)函數(shù)（示例）：

  • Top-1：algos.lcs_length —— Inclusive （百分比）
  • Top-2：io_utils.load_text —— Inclusive （百分比）

---

五、最終性能對(duì)比

指標(biāo)	優(yōu)化前（基線）	優(yōu)化后	提升幅度
時(shí)間（秒）	2.31	1.48	35.9% （= (2.31-1.48)/2.31）
內(nèi)存（MB）	120	54	55%↓

---

六、源碼展示

algos.py

from __future__ import annotations

def lcs_length(a: str, b: str) -> int:
    """LCS 長(zhǎng)度（滾動(dòng)數(shù)組，O(min(n,m)) 空間）"""
    m, n = len(a), len(b)
    if m == 0 or n == 0:
        return 0
    # 讓 b 成更短的一邊，減少列數(shù)
    if n > m:
        a, b = b, a
        m, n = n, m

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        ai = a[i - 1]
        for j in range(1, n + 1):
            if ai == b[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                left = curr[j - 1]
                up   = prev[j]
                curr[j] = left if left >= up else up
        prev, curr = curr, [0] * (n + 1)
    return prev[n]

def lcs_similarity_pct(original: str, copied: str) -> float:
    """返回 LCS 相似度百分比（以“抄襲文本長(zhǎng)度”為分母）。copied 為空則 0.0。"""
    if not copied:
        return 0.0
    return (lcs_length(original, copied) / len(copied)) * 100.0

def safe_lcs_length(a: str, b: str) -> int:
    """超長(zhǎng)觸發(fā) MemoryError 時(shí)返回 0（穩(wěn)健性演示）"""
    try:
        return lcs_length(a, b)
    except MemoryError:
        return 0

io_utils.py

from __future__ import annotations
from pathlib import Path

def load_text(path: str) -> str:
    """UTF-8 優(yōu)先讀取；失敗回退 GBK（忽略錯(cuò)誤）；失敗返回空串，不拋異常。"""
    p = Path(path)
    try:
        return p.read_text(encoding="utf-8")
    except UnicodeDecodeError:
        try:
            return p.read_text(encoding="gbk", errors="ignore")
        except Exception:
            return ""
    except Exception:
        return ""

def save_line_append(path: str, line: str) -> None:
    """追加寫(xiě)入一行；自動(dòng)建父目錄。"""
    p = Path(path)
    p.parent.mkdir(parents=True, exist_ok=True)
    with p.open("a", encoding="utf-8") as f:
        f.write(line + ("\n" if not line.endswith("\n") else ""))

def only_name(path: str) -> str:
    """返回純文件名"""
    return Path(path).name

runner.py

from __future__ import annotations
import sys
import argparse
from algos import lcs_similarity_pct
from io_utils import load_text, save_line_append, only_name

def parse_args(argv: list[str]) -> argparse.Namespace:
    p = argparse.ArgumentParser(description="基于 LCS 的字符級(jí)相似度檢測(cè)")
    p.add_argument("original", help="原文文件路徑")
    p.add_argument("copied",   help="抄襲版文件路徑")
    p.add_argument("output",   help="答案文件路徑（結(jié)果將追加寫(xiě)入）")
    return p.parse_args(argv[1:])

def format_result_line(orig_path: str, copy_path: str, sim_pct: float) -> str:
    return (
        f"The similarity rate between document {only_name(orig_path)} "
        f"and ducument {only_name(copy_path)} is {sim_pct:.2f}%"
    )

def run_once(original_path: str, copied_path: str, output_path: str) -> float:
    s1 = load_text(original_path)
    s2 = load_text(copied_path)
    if not s1 or not s2:
        save_line_append(
            output_path,
            f"{only_name(original_path)}文件與{only_name(copied_path)}文件的重復(fù)率為0.00%（檢測(cè)到空文件）",
        )
        return 0.0

    sim = lcs_similarity_pct(s1, s2)
    save_line_append(output_path, format_result_line(original_path, copied_path, sim))
    return sim

def main(argv: list[str]) -> int:
    args = parse_args(argv)
    try:
        _ = run_once(args.original, args.copied, args.output)
        return 0
    except Exception:
        return 2

if __name__ == "__main__":
    sys.exit(main(sys.argv))

io_utils.py

generate_samples.py
import random, os
def generate_sentence():
    subjects = ["我","你","他","小明","老師","學(xué)生"]
    verbs = ["喜歡","討厭","學(xué)習(xí)","研究","使用","編寫(xiě)"]
    objects = ["人工智能","機(jī)器學(xué)習(xí)","Python","C++","論文","算法"]
    return random.choice(subjects)+random.choice(verbs)+random.choice(objects)+"。"

def make_copied_version(text: str) -> str:
    replacements = {"喜歡":"熱愛(ài)","討厭":"不喜歡","學(xué)習(xí)":"研究","研究":"學(xué)習(xí)","使用":"利用","編寫(xiě)":"撰寫(xiě)",
                    "人工智能":"AI","機(jī)器學(xué)習(xí)":"Machine Learning","論文":"文章","算法":"方法"}
    copied = text
    for k,v in replacements.items():
        if k in copied and random.random() < 0.5:
            copied = copied.replace(k, v, 1)
    return copied

def generate_dataset(num_pairs=5, output_dir="data"):
    os.makedirs(output_dir, exist_ok=True)
    for i in range(1, num_pairs+1):
        orig_file = os.path.join(output_dir, f"orig_{i}.txt")
        copy_file = os.path.join(output_dir, f"copy_{i}.txt")
        orig_text = "\n".join(generate_sentence() for _ in range(5))
        copy_text = "\n".join(make_copied_version(s) for s in orig_text.splitlines())
        open(orig_file, "w", encoding="utf-8").write(orig_text)
        open(copy_file, "w", encoding="utf-8").write(copy_text)
        print(f"生成: {orig_file}, {copy_file}")
    print("\n示例：python main.py data/orig_1.txt data/copy_1.txt result.txt")

if __name__ == "__main__":
    generate_dataset()

七、測(cè)試數(shù)據(jù)的構(gòu)造思路

1. 基礎(chǔ)功能測(cè)試

完全相同的文本

• 原文：今天天氣晴朗，適合戶(hù)外運(yùn)動(dòng)。
• 抄襲版：今天天氣晴朗，適合戶(hù)外運(yùn)動(dòng)。
• 預(yù)期相似度：100%

部分修改的文本

• 原文：深度學(xué)習(xí)需要大量計(jì)算資源。
• 抄襲版：機(jī)器學(xué)習(xí)需要大量 GPU 資源。
• 預(yù)期相似度：約 50%（同義替換與結(jié)構(gòu)變化導(dǎo)致 LCS 長(zhǎng)度下降）

完全不同的文本

• 原文：春天是萬(wàn)物復(fù)蘇的季節(jié)。
• 抄襲版：量子物理研究微觀粒子。
• 預(yù)期相似度：0%（LCS 極短，約等于 0）

注：本項(xiàng)目相似度定義為 LCS(original,copied) / len(copied) * 100%，為字符級(jí)度量，天然支持中文。

2. 邊界情況測(cè)試

空文件

• 原文：(空)
• 抄襲版：這是一個(gè)測(cè)試句子。
• 預(yù)期相似度：0%（任意一邊為空，直接按 0 處理并輸出固定格式文本）

單字符文件

• 原文：A
• 抄襲版：A
• 預(yù)期相似度：100%

超長(zhǎng)文本（約 1 萬(wàn)字符）

• 用于考察時(shí)間/內(nèi)存與穩(wěn)健性。

• 生成方法（任選其一）：

  # 方式 A：Python 一行流
  python - <<'PY'
  

from pathlib import Path
s = "人工智能讓世界更美好。" * 500 # 單行~1萬(wàn)字符
Path("longlong.txt").write_text(s, encoding="utf-8")
print("OK")
PY

方式 B：隨機(jī)生成兩份

python generate_samples.py # 自動(dòng)在 data/ 下生成 orig_X/copy_X

## 3. 中文處理測(cè)試

**標(biāo)點(diǎn)/語(yǔ)氣差異（相似但非 100%）**
- 原文：“你好，”她說(shuō)，“今天天氣不錯(cuò)。”  
- 抄襲版：“你好！”他說(shuō)，“今天天氣很好。”  
- 預(yù)期相似度：**約 70%～80%**（示例：~76%）

**多音字/同形字（語(yǔ)義近，字符不同）**
- 原文：銀行行長(zhǎng)在銀行門(mén)口行走。  
- 抄襲版：銀行行長(zhǎng)在銀行前行路。  
- 預(yù)期相似度：**約 70%～80%**（示例：~78%）

> 精確百分比與輸入長(zhǎng)度相關(guān)，可用腳本實(shí)際跑一遍記錄。

## 4. 文件路徑與異常

- **含空格路徑**：確保能正常讀寫(xiě)（Windows 常見(jiàn)）  
- **特殊字符路徑**：如 `測(cè)試#樣例/文檔@1.txt`  
- **文件不存在**：應(yīng)輸出 0.00% 的固定提示行，而不是拋異常

---

## 八、計(jì)算模塊異常處理說(shuō)明（含單元測(cè)試樣例）

> 下列示例與本項(xiàng)目結(jié)構(gòu)匹配：`algos.py / io_utils.py / runner.py / main.py`

## 1. 文件讀取失敗異常

**設(shè)計(jì)目標(biāo)**：路徑無(wú)效/權(quán)限不足時(shí)不崩潰。  
**處理邏輯**（`io_utils.load_text` 已實(shí)現(xiàn) UTF-8 優(yōu)先、GBK 回退，失敗返回空串）：
```python
# io_utils.load_text 要點(diǎn)：失敗返回 ""，主流程輸出 0.00%

單元測(cè)試樣例：

def test_file_not_exist(tmp_path):
    import subprocess, sys
    result_file = tmp_path / "result.txt"
    # 原文文件不存在
    r = subprocess.run(
        [sys.executable, "main.py", "not_exists.txt", "copy.txt", str(result_file)],
        capture_output=True
    )
    # 程序應(yīng)正常退出，并在結(jié)果中寫(xiě)入 0.00%
    assert result_file.exists()
    content = result_file.read_text(encoding="utf-8")
    assert "0.00%" in content

2. 內(nèi)存分配失敗異常

設(shè)計(jì)目標(biāo)：超大文本下出現(xiàn) MemoryError 時(shí)也不崩潰。
處理邏輯：algos.safe_lcs_length 捕獲 MemoryError 返回 0。

# algos.safe_lcs_length
# try: return lcs_length(a, b)
# except MemoryError: return 0

單元測(cè)試樣例（模擬 MemoryError）：

import pytest

def test_memory_error(monkeypatch):
    import algos
    def fake_lcs_length(a, b): raise MemoryError
    monkeypatch.setattr(algos, "lcs_length", fake_lcs_length)
    assert algos.safe_lcs_length("abc", "abc") == 0

3. 輸入?yún)?shù)無(wú)效異常

設(shè)計(jì)目標(biāo)：參數(shù)不足時(shí)給出清晰提示并返回非 0。
處理邏輯：runner.parse_args + runner.main 負(fù)責(zé)校驗(yàn)。

單元測(cè)試樣例：

def test_invalid_arguments():
    import subprocess, sys
    r = subprocess.run([sys.executable, "main.py"], capture_output=True)
    assert r.returncode != 0
    # argparse 輸出中包含 "usage" 或錯(cuò)誤提示
    assert b"usage" in r.stderr or r.stdout

4. 編碼轉(zhuǎn)換異常

設(shè)計(jì)目標(biāo)：處理非 UTF-8 文件，不因解碼報(bào)錯(cuò)中斷。
處理邏輯：io_utils.load_text 先 UTF-8，失敗回退 GBK(忽略錯(cuò)誤)，仍失敗則 ""。

單元測(cè)試樣例：

def test_utf8_decode_error(tmp_path):
    from io_utils import load_text
    bad = tmp_path / "gbk.txt"
    bad.write_bytes("中文".encode("gbk"))  # 構(gòu)造非 UTF-8 文件
    # load_text 讀取失敗會(huì)回退，若仍異常返回空串
    _ = load_text(str(bad))  # 不拋異常即可

---

覆蓋率運(yùn)行命令（用于截圖與報(bào)告）

# 確保 tests/conftest.py 把工程根加入 sys.path
# 內(nèi)容：
# import sys, os
# sys.path.insert(0, os.path.abspath(os.path.join(os.path.dirname(__file__), "..")))

pytest --cov=. --cov-report=term-missing --cov-report=html --cov-report=xml
# 打開(kāi) htmlcov/index.html 截圖

---

性能復(fù)現(xiàn)實(shí)驗(yàn)命令（用于截圖）

# 固定輸入（可用 generate_samples.py 生成）
python generate_samples.py  # data/orig_1.txt, data/copy_1.txt

# 生成性能畫(huà)像
python -m cProfile -o prof.out main.py data/orig_1.txt data/copy_1.txt result.txt

# 可視化（任選其一）
snakeviz prof.out                       # 瀏覽器火焰圖/旭日?qǐng)D
# 或 VS2017：Debug > Performance Profiler（Alt+F2）
# 勾 CPU Usage（可選 Memory），Start external program 指向 python.exe，
# Arguments: main.py data/orig_1.txt data/copy_1.txt result.txt
# 取 Functions / Call Tree / Hot Path 截圖

---

九、結(jié)論與改進(jìn)計(jì)劃

結(jié)論：通過(guò)結(jié)構(gòu)化改造（算法/I-O/CLI 解耦）、滾動(dòng)數(shù)組與列長(zhǎng)度優(yōu)化，定位并緩解了 lcs_length 的熱點(diǎn)，穩(wěn)定性與可維護(hù)性顯著提升。

改進(jìn)計(jì)劃：

• 批量文件并行比對(duì)（多進(jìn)程）
• 更快的近似相似度（指紋/LSH）
• 結(jié)果解釋增強(qiáng)（輸出 LCS 對(duì)齊片段）
• 完善異常類(lèi)與日志設(shè)施，覆蓋率目標(biāo) ≥ 85%

---

附：復(fù)現(xiàn)實(shí)驗(yàn)命令

# 性能畫(huà)像
python -m cProfile -o prof.out main.py data/orig_1.txt data/copy_1.txt result.txt
snakeviz prof.out    # 截圖

# 計(jì)時(shí)（Windows）
Measure-Command { python main.py data/orig_1.txt data/copy_1.txt result.txt }

# 單元測(cè)試與覆蓋率
pytest --cov=. --cov-report=term-missing --cov-report=html
# 打開(kāi) htmlcov/index.html

---