Parquet 文件入门 Python 读写 Parquet 文件实战 大数据存储优化：Parquet 格式解析 Python 数据分析必备：Parquet 文件处理技巧 列式存储揭秘：Parquet 文件与性能优化 使用 Python 和 PyArrow 处理嵌套 Parquet 数据 从 CSV 到 Parquet：Python 数据格式转换教程

什么是 Parquet 文件？

Parquet 是一种列式存储文件格式，优化用于大规模数据处理。它常用于 Apache Spark、Hadoop 和 Pandas 等大数据框架，以实现高效存储和快速检索表格数据。 Parquet 格式可以简单认为是CSV的转置/Transpose。不过CSV是文本的，而Parquet是二进制的。从存储方式上理解列式存储就像把行列交换，但需要注意 Parquet 是二进制、支持压缩和嵌套类型，不仅仅是“转置”。

为什么使用 Parquet？

• 列式存储：按列存储数据，提高分析任务的查询性能。
• 压缩：支持高效的压缩技术，减少存储空间。
• 兼容性：可与多种数据处理框架配合使用。
• 模式演进：支持增加或删除列而不破坏现有数据。

安装所需库

要在 Python 中使用 Parquet，需要 pandas 和 pyarrow（或 fastparquet）：

pip install pandas pyarrow

在 Python 中读取 Parquet 文件

以下示例演示如何使用 pandas 和 pyarrow 读取 Parquet 文件：

import pandas as pd
import pyarrow.parquet as pq

# Parquet 文件路径
file_path = "example.parquet"

# 读取 Parquet 文件到 DataFrame
df = pd.read_parquet(file_path)

# 显示前 5 行
print(df.head())

写入 Parquet 文件

你也可以轻松地将 DataFrame 保存为 Parquet 文件：

import pandas as pd

# 创建示例 DataFrame
data = {
    "name": ["Alice", "Bob", "Charlie"],
    "age": [25, 30, 35],
    "city": ["London", "Paris", "New York"]
}
df = pd.DataFrame(data)

# 保存为 Parquet
df.to_parquet("output.parquet", engine="pyarrow", index=False)

处理嵌套数据

Parquet 支持嵌套数据，如列表或结构体。可以使用 pyarrow 直接读取：

import pyarrow.parquet as pq
from io import BytesIO

# 直接读取 Parquet 文件
table = pq.read_table("example.parquet")
df = table.to_pandas()
print(df.head())

总结

Parquet 文件在存储和处理大规模表格数据时非常高效。使用 Python 的 pandas 和 pyarrow，你可以轻松地读取、写入并处理 Parquet 文件，用于数据分析、ETL 流程和大数据应用。 [show_file file="/var/www/wp-post-common/justyy.com/python.php"] 英文：Introduction to Parquet Files: Read & Write using Python

使用原子 TAS 指令实现自旋锁

使用原子 TAS 指令实现自旋锁 Implementing a Spinlock Using the Atomic TAS Instruction 从零实现自旋锁：基于 TAS 的最小同步原语 Building a Spinlock from Scratch with Atomic TAS 用 test-and-set 实现最简单的互斥锁 Implementing a Minimal Mutex Using Test-and-Set 自旋锁的底层原理：TAS、原子性与忙等待 Inside Spinlocks: TAS, Atomicity, and Busy Waiting 原子操作与自旋锁：用 C 语言实现线程同步 Atomic Operations and Spinlocks: Thread Synchronization in C 从原子指令到锁：全面理解 TAS 和自旋锁 From Atomic Instructions to Locks: A Complete Guide to TAS and Spinlocks 动手写一个自旋锁：tryLock / lockAcquire / lockRelease 全实现 Hands-On Spinlock Implementation: tryLock, lockAcquire, and lockRelease 你的第一个自旋锁：基于 C 语言的 TAS 实现 Your First Spinlock: A TAS-Based Implementation in C 原子交换与线程互斥：自旋锁实现指南 Atomic Exchange and Thread Mutual Exclusion: A Guide to Implementing Spinlocks

假设我们有一个 TAS（Take-And-Set）函数。该操作返回内存中原来的值，并以原子方式将其替换为新值。原子性（atomicity）意味着没有其他线程能够观察到中间状态；整个读-写操作是一体不可分的。 在 C++ 中，标准库函数 std::exchange 在逻辑上表现相同，但它不是原子操作。同步原语需要硬件级别的原子性。

int TAS(int* memory, int newVal) {
    int old = *memory;
    *memory = newVal;
    return old;
}

我们想使用这个原语来实现一个简单的自旋锁，包括：

• lockAcquire()
• lockRelease()

线程将调用这些函数来保护对共享变量的访问：

typedef struct {
    int lock;
} lockType;

typedef struct {
    int val;
} threadArgType;

void threadFunc(void* arg) {
    lockAcquire((static_cast<lockType*>arg)->lock);
    (static_cast<threadArgType*>arg)->val++;
    lockRelease((static_cast<lockType*>arg)->lock);
}

实现 tryLock

tryLock 函数尝试获取锁一次。如果锁为空（值为 0），TAS 将其设置为 1 并返回原值（0）。如果锁已被占用，TAS 返回 1。tryLock 函数是非阻塞的——它会立即返回。 因此 tryLock() 只有在 TAS 返回 0 时才会成功：

enum {
    UNLOCKED = 0,
    LOCKED = 1
}

int tryLock(lockType* lock) {
    // 如果之前已锁定返回 1，如果之前未锁定返回 0
    int old = TAS(lock->lock, LOCKED);
    return (old == UNLOCKED);   // true (1) = 成功获取锁
}

实现 lockAcquire()

普通的锁获取应当“自旋”直到 tryLock() 成功。这称为 自旋锁，因为 CPU 会忙等待。必要时可以加入短暂的 sleep。例如，sleep(0) 并不会真正暂停执行，而是让出 CPU，允许其他线程运行。 它通常用于实现跨线程的互斥自旋锁。

void lockAcquire(lockType* lock) {
    while (!tryLock(lockType* lock)) {
        // 自旋直到锁可用
    }
}

另一种实现：

void lockAcquire(lockType* lock) {
    do {
       if (tryLock(lockType* lock)) {
          break;
       }
    } while (1);
}

展开 tryLock：

void lockAcquire(lockType* lock) {
    do {
       int old = TAS(lock->lock, LOCKED);
       // 无论锁是否已被获取，锁都已设置为 LOCKED
       if (old == UNLOCKED) {
           break;
       }
    } while (1);
}

这是使用 TAS 实现的最简单方法。在实际系统中，我们可能会加入 pause 指令或退避策略，但基本思路是相同的。

实现 lockRelease()

释放锁时，持有者只需将锁变量写为 0。由于 TAS 是“设置新值并返回旧值”，它同样适用于释放锁：

void lockRelease(lockType* lock) {
    TAS(lock->lock, UNLOCKED);
}

或者使用简单的原子存储也足够，但由于 TAS 是我们唯一的工具，我们重用它。请注意，在这里重复释放锁是安全的，因为再次将其设置为 UNLOCKED=0 不会产生副作用。

总结

仅使用原子 TAS 指令，我们实现了：

• 一个 tryLock() 尝试
• 一个 lockAcquire() 自旋锁
• 一个 lockRelease() 解锁操作

这种锁的实现方式对于理解低级并发、内存顺序以及高层互斥锁库的构建方式非常基础。 [show_file file="/var/www/wp-post-common/justyy.com/cpp.php"] 英文：Implement a Lock Acquire and Release in C++

理解 Sigma 函数：因子、乘法性与公式推导

一文看懂 Sigma 函数：因子分解的终极威力！ σ(n) 完全解析：为什么求和函数能“自动”变成乘积？ 数学之美：Sigma 函数的推导、公式与 Python 实现 从几何级数到质因数：Sigma 函数的魔法公式大揭秘 搞懂 σ(n) 的那一天，我看到了数学的秩序 为什么 σ(n) = 乘积？带你走进数论的核心思想 Divisor 终极指南：Sigma 函数推导 + 代码 一篇搞定

Sigma 函数，记作 [math]\sigma(n)[/math]，表示一个整数所有正因子的和。 例如 12 的因子有 1、2、3、4、6、12，因此 [math]\sigma(12)=28[/math]。 本文解释什么是 Sigma 函数、为什么它满足乘法性、如何从质因数分解推导出通用公式，并给出高效的 Python 实现。

可除性符号

在数论中，符号 “|” 表示“整除”。 [math]d \mid a \quad \Longleftrightarrow \quad \exists k \in \mathbb{Z},\; a = dk[/math] 因此表达式 [math]\sum_{d \mid n} d[/math] 的意思是“对所有能整除 n 的 d 求和”。

质因数分解与因子的结构

任意正整数 [math]n[/math] 都可以唯一写成： [math]n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}[/math] 它的一个因子必须从每个质数的指数中“选择”一个： [math]d = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \qquad 0 \le e_i \le a_i[/math] 所有因子结构的规律都来自这个事实。

关键性质：Sigma 函数是乘法性的

当两个整数互质时，Sigma 函数满足： [math]\sigma(mn) = \sigma(m)\,\sigma(n) \qquad \text{if} \gcd(m,n)=1[/math] 原因是：若 [math]m[/math] 和 [math]n[/math] 的质因数互不相同， 那么 [math]mn[/math] 的每个因子都能唯一写成： [math]d = d_m d_n, \quad d_m \mid m, \; d_n \mid n[/math] 因此对所有因子求和可以写成二重求和： [math]\sigma(mn) = \sum_{d_m \mid m} \sum_{d_n \mid n} d_m d_n[/math] 接下来把二重求和“拆开”。固定某个 [math]d_m[/math]，则： [math]\sum_{d_n \mid n} (d_m d_n) = d_m \sum_{d_n \mid n} d_n = d_m \sigma(n)[/math] 再对所有 [math]d_m[/math] 求和： [math]\sigma(mn) = \sum_{d_m \mid m} d_m \sigma(n) = \sigma(n) \sum_{d_m \mid m} d_m = \sigma(n)\sigma(m)[/math] 这就证明了 Sigma 的乘法性。

质数幂的 Sigma 公式

利用乘法性，只需计算 [math]\sigma(p^k)[/math]。 其因子为： [math]1, p, p^2, \ldots, p^k[/math] 这是一个几何级数： [math]\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1} - 1}{p - 1}[/math] 把所有质因数幂的贡献相乘，就得到通用公式： [math]\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1}[/math] 这就是任意正整数的因子和公式。

示例：计算 σ(12)

质因数分解： [math]12 = 2^2 \cdot 3^1[/math] 分别计算： [math]\sigma(2^2) = 1 + 2 + 4 = 7[/math] [math]\sigma(3^1) = 1 + 3 = 4[/math] 相乘： [math]\sigma(12) = 7 \cdot 4 = 28[/math]

Python 实现：高效的 Sigma 函数

以下是基于质因数分解与乘法性的高效Python实现，时间复杂度约为 [math]O(\sqrt{n})[/math]。

def sigma(n: int) -> int:
    """高效计算因子和函数 σ(n)。"""
    total = 1
    x = n

    # 处理质因数 2
    count = 0
    while x % 2 == 0:
        x //= 2
        count += 1
    if count > 0:
        total *= (2 ** (count + 1) - 1) // (2 - 1)

    # 处理奇质数
    p = 3
    while p * p <= x:
        if x % p == 0:
            count = 0
            while x % p == 0:
                x //= p
                count += 1
            total *= (p ** (count + 1) - 1) // (p - 1)
        p += 2

    # 若剩下的是质数
    if x > 1:
        total *= (x**2 - 1) // (x - 1)

    return total

结语

Sigma 函数展示了因子结构的优雅与质因数分解的力量。通过理解乘法性与几何级数求和，我们得到一个漂亮的闭式公式，并能编写高效的计算程序。有了理论与代码，你就能深入探索更多数论中的算术函数了。 [show_file file="/var/www/wp-post-common/justyy.com/math.php"] 英文：Understanding the Sigma Function: Divisors, Multiplicativity, and the Formula

Amdahl 定律 vs Gustafson 定律 — 完整教程、推导、应用场景及 Python 绘图

Amdahl 定律 vs Gustafson 定律：完整教程、推导、应用场景及 Python 绘图 理解并行加速：通过代码讲解 Amdahl 定律和 Gustafson 定律 并行计算基础：Amdahl 定律、Gustafson 定律及加速建模 并行加速原理：Amdahl 和 Gustafson 定律完整指南 并行扩展解析：推导并比较 Amdahl 和 Gustafson 定律 Amdahl vs Gustafson：并行加速完整指南（含 Python 代码） 并行性能建模：Amdahl 定律、Gustafson 定律及实际应用 学习并行加速：数学、直觉、应用场景及 Python 可视化 并行计算：必须掌握的两条定律（Amdahl & Gustafson） 工程师的并行加速：Amdahl 定律、Gustafson 定律及 Python 实现 从理论到代码：用 Amdahl 和 Gustafson 建模并行加速 实用并行加速指南：Amdahl 定律、Gustafson 定律及可视化 为什么并行不是无限的：简单解释 Amdahl vs Gustafson 并行加速真相：Amdahl 限制 vs Gustafson 扩展 并行计算神话与现实：Amdahl 和 Gustafson 的教训

引言

并行计算在现代计算中至关重要：多核 CPU、GPU、分布式集群、云工作负载、LLM 训练以及 HPC 模拟。 为了分析程序在更多处理器下能加速多少，主要有两种数学模型：

• Amdahl 定律 — 固定规模工作负载的性能
• Gustafson 定律 — 可扩展规模工作负载的性能

这两条定律并不矛盾，它们回答的是 不同的问题。 本教程涵盖推导、直觉、比较、实际应用场景，以及展示两条定律的 Python 绘图脚本。

1. 什么是加速比？

加速比衡量程序在 N 个处理器上运行速度提升多少： [math]S(N) = \frac{T_1}{T_N}[/math] 如果程序在一个处理器上运行 10 秒，两处理器运行 5 秒，则加速比为： [math]S(2) = \frac{10}{5} = 2[/math] 完美线性加速为： [math]S(N) = N[/math] 但实际系统存在串行瓶颈，这正是 Amdahl 定律和 Gustafson 定律描述的内容。

2. Amdahl 定律（固定工作量）

2.1 直觉

Amdahl 假设：

• 总工作量保持 不变
• 部分工作是串行的，无法并行化

设：

• f = 串行比例
• 1 - f = 可并行比例

2.2 推导

一个处理器的运行时间： [math]T_1 = T_s + T_p[/math] 定义： [math]f = \frac{T_s}{T_1}[/math] 因此： [math]T_s = fT_1[/math] [math]T_p = (1 - f)T_1[/math] N 个处理器的运行时间： [math]T_N = fT_1 + \frac{(1 - f)T_1}{N}[/math] 加速比： [math] S(N) = \frac{T_1}{T_N} = \frac{1}{f + \frac{1 - f}{N}} [/math] 其中 f 是串行工作比例，[math] 1-f [/math] 是可并行工作。Amdahl 公式也可以写成： [math] S(N) = \frac{T_1}{T_N} = \frac{1}{(1-p) + \frac{p}{N}} [/math] 其中 [math] p=1-f [/math]，[math] f=1-p [/math]

2.3 当 N → ∞ 时的极限

[math]S(\infty) = \frac{1}{f}[/math] 如果串行比例为 10%（f = 0.1）： [math]S_\infty = 10[/math] 即使处理器无限，也无法超过该值。

2.4 Amdahl 定律的实际应用场景

Amdahl 适合优化固定任务的 延迟：

• GPU 内核优化固定张量大小
• 单次请求推理延迟降低
• 视频编码、压缩、排序
• 加速固定批量作业
• 数据库查询加速

---

3. Gustafson 定律（可扩展工作量）

3.1 直觉

Gustafson 反过来问： “增加处理器，我能在相同时间内解决多大的问题？” 这反映了真实 HPC 工作负载：更多 CPU → 更高分辨率 → 更大模拟。

3.2 推导

假设程序在 N 个处理器上运行 1 个时间单位。 设：

• f = 串行比例（按规模测量）

可并行部分随处理器数量扩展，因此其运行时间保持与 N 成比例。 一个处理器的时间： [math]T_1 = f + N(1 - f)[/math] 加速比： [math]S(N) = f + N(1 - f)[/math] Gustafson 公式的 “N 减” 形式： [math]S(N) = N - (N - 1)f[/math] 或者，如果定义并行比例 [math]p = 1 - f[/math]，公式也可写为： [math]S(N) = f + N(1-f) = f + Np [/math] “N 减” 形式用 p 表示： [math] S(N) = N-(N-1)f = N - (N-1)(1-p) [/math]

3.3 解释

随着 N 增加，加速比趋近于： [math]S(N) \approx N(1 - f)[/math] 对于小串行比例，几乎呈线性增长。

3.4 Gustafson 定律的实际应用场景

Gustafson 适用于 吞吐量扩展 或可增加问题规模的工作负载：

• 天气和气候模拟
• 粒子模拟、CFD、有限元分析
• LLM 训练：更多 GPU → 更长序列或更大模型
• 大数据分析（Spark, Dask, Flink）
• 蒙特卡洛模拟

---

4. Amdahl 定律 vs Gustafson 定律（比较表）

项目	Amdahl	Gustafson
工作负载	固定	随 N 扩展
目标	降低延迟	增加吞吐量
加速比上限	有界: [math]1/f[/math]	近似线性: [math]N(1-f)[/math]
悲观/乐观	悲观	乐观
应用场景	优化现有任务	扩展大规模工作量

---

5. 实际应用场景（综合视角）

Amdahl（延迟优化）

• 减少单次 LLM 查询推理时间
• 加速数据库 join 操作
• 固定张量 GPU 内核优化
• 视频编码（相同视频）

Gustafson（吞吐量 / 扩展）

• LLM 训练（扩展至更多 GPU）
• 高分辨率天气模型模拟
• 大数据 ETL 扩展
• 科学 HPC 工作负载

6. Python 绘图脚本（显示两条定律）

下面代码生成 Amdahl 与 Gustafson 加速比曲线图。 可以调整 f（串行比例）和处理器数量 N。 脚本绘制两条曲线在同一张图上。 包括部分 [math]f[/math] 的值，例如串行部分： import numpy as np import matplotlib.pyplot as plt def amdahl_speedup(N, s): return 1.0 / (s + (1 - s) / N) def gustafson_speedup(N, s): return s + (1 - s) * N # Number of processors N = np.arange(1, 65) # Serial fractions to consider Serial = [0.05, 0.1, 0.2, 0.3, 0.5, 0.8, 0.9, 1.0] plt.figure(figsize=(10, 6)) for f in Serial: plt.plot(N, amdahl_speedup(N, f), linestyle='-', label=f"Amdahl Serial={f}") plt.plot(N, gustafson_speedup(N, f), linestyle='--', label=f"Gustafson Serial={f}") plt.title("Amdahl's Law") plt.xlabel("Number of Processors (N)") plt.ylabel("Speedup") plt.legend() plt.grid(True) plt.tight_layout() plt.savefig("parallel-speedup-amdahl-vs-gustafson.png") ## plt.show() 下面是 Amdahl 与 Gustafson 曲线图示。 [caption id="attachment_70445" align="alignnone" width="1000"] Amdahl 定律加速曲线[/caption] [caption id="attachment_70446" align="alignnone" width="1000"] Amdahl vs Gustafson 加速曲线[/caption] [caption id="attachment_70447" align="alignnone" width="1000"] Gustafson 定律加速曲线[/caption]

图示解读

• Amdahl 曲线迅速趋于平缓——受串行部分限制。
• Gustafson 曲线几乎线性上升——适用于可扩展工作负载。
• 串行比例 f 越高，两种模型差距越大。

结论

Amdahl 定律展示了固定工作负载下的并行 上限，适合延迟优化。Gustafson 定律展示了随工作负载扩展的并行 潜力。

• Amdahl 定律 → 固定规模工作负载 → 收益递减
• Gustafson 定律 → 可扩展工作负载 → 近似线性加速
• 结合使用理解硬件极限与算法特性
• Python 工具使可视化直观易懂

它们共同构成现代并行系统性能分析基础，从 HPC 到 LLM 训练，再到 GPU 计算。 英文：The Truth About Parallel Speedup: Amdahl’s Limits vs Gustafson’s Scaling

组合简介（组合数学入门）

视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook 组合计数是在顺序不重要时选择项目的方式。我们从一个简单的格子行走示例出发建立直觉，介绍二项式记号，推导公式，解释递推关系 [math]C(n,m)=C(n-1,m-1)+C(n-1,m)[/math]，并把所有内容联系到帕斯卡三角。

格子行走示例 — 从左下到右上路径

想象你只能向右（R）或向上（U）移动。要从左下走到需要三次向右和两次向上的点，每一条最短路径都是由五步组成的序列，其中包含三个 R 和两个 U。 [caption id="attachment_70414" align="alignnone" width="512"] 走格子: 排列组合[/caption] 每条有效路径只是从五个位置中选择两个放 U（其余为 R）。所以这样的路径数就是“从 5 中选 2”，记作 [math]C(5,2)[/math]（等于 [math]C(5,3)[/math]）。 示例序列：

R R U R U U R R R U R U R R U R R R U U U U R R R 

二项式系数（组合）表示法

从 [math]n[/math] 个项目中选出 [math]m[/math] 个（顺序不重要）的方式数记为 [math]C(n,m)[/math] 或 [math]\binom{n}{m}[/math] 两者都表示“从 n 中选 m”。

组合公式 — 基于阶乘的推导

先计算有序选择（排列）：从 n 个不同项目中取出长度为 [math]m[/math] 的有序列表的数量为 [math] n\times(n-1)\times\cdots\times(n-m+1)=\dfrac{n!}{(n-m)!} [/math] 每一个无序的 [math] m [/math] 项集合对应 [math] m! [/math] 个有序列表（即这 m 项的排列）。除以 [math] m! [/math] 得到组合数： [math]C(n,m)=\dfrac{n!}{m!(n-m)!}.[/math]

把公式应用到格子示例

对于总步数 [math]n=5[/math] 和向上步数 [math]m=2[/math]： [math]C(5,2)=\dfrac{5!}{2!,3!}=\dfrac{120}{2\times 6}=10 [/math] 因此共有 10 条不同的最短路径。

为什么这个公式直观上合理

• 视角一 — 选择位置：从 [math]n[/math] 个位置中选择放置 U 的 [math]m[/math] 个位置；这就是 [math]C(n,m)[/math]。
• 视角二 — 用排列除以顺序：先计算 n 步的所有排列，然后除去相同步序的重排（比如相同类型步的交换）。

帕斯卡三角与递推关系

把 [math]C(n,k)[/math] 写成行可以形成帕斯卡三角：

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 

[caption id="attachment_70413" align="alignnone" width="847"] Pascal/帕斯卡三角形[/caption] 这些项满足递推关系 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] 然后，我们可以很容易的写出至顶向下的动态规划算法实现（用@cache实现记忆化式的递归搜索）：

from functools import cache

@cache
def C(n, m):
    if m == 0:
        return 1  # C(n, 0) = 1
    if m == n:
        return 1  # C(n, n) = 1
    return C(n-1, m-1) + C(n-1, m)

当然，也可以用自底向上的方式实现：

def C_bottom_up(n, m):
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1  # C(i, 0) = 1
        for j in range(1, min(i, m)+1):
            if j == i:
                dp[i][j] = 1  # C(i, i) = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp[n][m]

这个自底向上的实现直接从小问题累加到大问题，避免了递归开销，同时也很容易扩展到计算整个帕斯卡三角。 组合数的自底向上 DP 可以用 一维数组优化，利用 滚动数组 原理，因为每一行的计算只依赖上一行。重点是从 右往左更新，这样不会覆盖还没用到的数据。 下面是实现示例：

def C_one_dim(n, m):
    dp = [0] * (m+1)
    dp[0] = 1  # C(i, 0) = 1

    for i in range(1, n+1):
        # 从右往左更新，避免覆盖上一行数据
        for j in range(min(i, m), 0, -1):
            dp[j] = dp[j] + dp[j-1]
    
    return dp[m]

示例：

print(C_one_dim(5, 2))  # 输出 10

✅ 优点：

• 空间复杂度 O(m)
• 时间复杂度 O(n*m)
• 可以方便扩展计算整行或整列组合数

组合证明 — 采苹果

想要从 [math]n[/math] 个苹果中选 [math]m[/math] 个。考虑最后一个苹果（编号为 n）： 如果你选了它，那就必须从前面的 [math]n-1[/math] 个中选剩下的 [math]m-1[/math] 个：有 [math]C(n-1,m-1)[/math] 种方法。 如果你不选它，那就必须从前面的 [math]n-1[/math] 个中选出全部 [math]m[/math] 个：有 [math]C(n-1,m) [/math] 种方法。 这两个互不相交的情况覆盖了所有可能，因此 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] （该恒等式正是构造帕斯卡三角的规则。）

递推关系的格子解释

在格子上，观察到达某点的任意路径的最后一步：要么是 R，要么是 U。以 R 结尾的路径来自某个前一点，以 U 结尾的路径来自另一个前一点。把这两组路径分别计数并相加就得到相同的加法规则。

常见的小值与说明

[math]C(n,0)=1[/math]（选择零个）。 [math]C(n,1)=n[/math]（选择一个）。 [math]C(n,n)=1[/math]（选择全部）。 当 [math]n=5[/math] 时的小表：

 C(5,0)=1 C(5,1)=5 C(5,2)=10 C(5,3)=10 C(5,4)=5 C(5,5)=1 

结语

组合出现在路径计数、二项式展开（系数）、概率与选择问题中。阶乘公式提供直接计算方法，而帕斯卡三角与递推关系则提供归纳直觉和高效构造数值的方式。格子行走示例是将“选择位置”等同于“选择步序”这一组合核心思想可视化的具体方法。 英文：Teaching Kids Programming - Introduction to Combinatorial Mathematics 1

性能隐藏的引擎：数据存放在哪里决定一切

1. 性能的真正秘密：数据放在哪里决定一切 2. 决定系统快慢的不是 CPU，而是数据的距离 3. 缓存才是现代计算性能的核心 4. 忽视数据局部性，一切性能优化都是徒劳 5. 性能瓶颈不在算力，而在内存层级 6. 数据局部性：被低估的性能决定因素 7. CPU 在等你的内存：缓存层级的真实代价 8. 系统速度快的真正原因：一切都与缓存有关 9. 别再关注 CPU 速度了——数据局部性才是制胜关键 10. 为什么缓存是所有高性能系统的幕后引擎 11. 性能的关键不在于 GHz，而在于距离 12. 你的 CPU 正在等待内存：缓存不为人知的故事 13. 数据局部性：计算机领域最重要却鲜为人知的因素 14. 数据存储位置决定一切 15. 缓存主宰一切：性能指南 16. 内存层次结构：性能的隐形杀手（或救星） 17. 为什么现代性能之战是与延迟的较量，而非与计算能力的较量

我们喜欢讨论 CPU 频率，但在实际系统中，关键问题是：你的数据存放在哪里？ 现代 CPU 依赖一个分层的内存体系（寄存器 → L1 → L2 → L3 → DRAM）。L1 访问可能只需约 4 个周期；而 DRAM 访问可能需要 200+ 个周期——那是 50× 更慢。如果你的工作集能放进缓存，一切飞快；如果不能，CPU 就会阻塞等待。

为什么缓存主导一切

分组处理是一个典型例子。每个数据包都会触发表查找。如果这些表能保持在缓存中，你可以每秒处理数百万个包；一旦溢出到 DRAM，吞吐量会崩塌。

真正的设计问题： 它能放进缓存吗？

[caption id="attachment_70404" align="alignnone" width="476"] CPU寄存器/缓存/架构[/caption] 缓存不仅仅关乎数据。指令缓存未命中也会毁掉尾延迟。有些高频交易系统会让热路径持续执行，只在需要发包时才打开网卡，从而保持 指令缓存持续命中。在交易环路中，一个 I-cache 停顿就可能占据全部延迟预算。

抽象失灵的地方

“全都上云”这类高层策略常忽略底层现实。虚拟化网络功能依赖于诸如：

• 独占核亲和（core pinning） —— 保持线程在同一 CPU 上以维持缓存热度
• 中断合并（interrupt coalescing） —— 降低中断率但以延迟为代价
• NUMA 局部性 —— 跨插槽访问会严重削弱性能
• 物理网卡与虚拟网卡 行为不同

销售演示会说“可以工作”，但细则通常是：需要 3 倍硬件、3 倍许可证，性能仍然无法与裸机匹配。 一旦你依赖缓存行为、核亲和和 NUMA 局部性，平台就不再可互换。

AI 也碰到同样的问题

即便在 AI 领域，物理规律也没变。模型越来越大，但数据移动依旧主导计算。局部性仍然是王道。

• 数组优于指针密集的结构，因为内存是连续的
• 硬件预取器只有在访问可预测时才有用
• 当内存布局合理时，缓存行被更高效地利用

在机器人控制中也能看到

在多轴运动控制中，第一个轴会“预热”缓存并承担缺失惩罚；后续轴的计算因为数据已经热化而耗时减半。相同的原理：局部性 = 速度。

IBM Telum：不同量级的缓存

IBM 的 Telum 处理器把这个想法推到了极端：

• 十个 36 MB 的 L2 缓存
• 360 MB 的虚拟 L3
• 2.8 GB 的虚拟 L4

[caption id="attachment_70405" align="alignnone" width="480"] IBM Telum 处理器[/caption] 该架构可以按需将 L2 转作 L3 使用。IBM 尚未公开这些缓存层的具体访问延迟，但在如此大规模的缓存下，大小、互连距离与命中延迟之间的折衷会非常有趣。

结论

性能归根结底由数据和指令能离核心多近来决定。 为局部性而设计，你的系统会表现出色。忽视它，再多的 GHz 或再多的云抽象也救不了你。

我们经常谈论 CPU 速度，却很少关注数据存储的位置。 性能主要取决于数据存储的便利程度。寄存器、L1 缓存、L2 缓存、L3 缓存、主内存——每一步都会增加延迟并降低吞吐量。访问主内存可能需要 200 个时钟周期，比 L1 缓存慢 50 倍。 当工作集能够放入缓存时，代码运行速度极快。否则，CPU 只能等待。 在数据包处理中，这种差异决定了一切。每个数据包都会触发表查找。如果这些表保存在 缓存 中，您可以每秒处理数百万个数据包。否则，吞吐量将急剧下降。 所以，下次设计数据结构时，请问问自己： 它能放进缓存吗？ 因为在对性能要求极高的系统中，缓存不仅仅是一种优化手段，它定义了整个系统。 而且不仅是数据，指令也一样！我见过高频交易工程师讨论他们的策略，他们将热路径编程为始终处于激活状态，并且只在数据包需要离开系统时才启用网卡。这样也能保持指令缓存处于热状态。 保持指令缓存处于热状态与保持数据缓存处于热状态同样重要，尤其是在对可预测性要求很高的工作负载中。优化热路径，使 CPU 始终保持在指令缓存中至关重要，因为即使是很小的停顿也可能导致尾延迟显著增加。这很好地提醒我们，架构设计的真正目的是尽可能地将指令和数据都放在靠近核心的位置。 很多技术决策者都固守一刀切的策略：例如……万物皆可云——他们认为任何虚拟化工作负载都可以在任何虚拟化环境中运行，底层硬件和虚拟化技术都只是商品而已。但这并不适用于虚拟化网络功能，因为厂商们早就知道，独占线程核心绑定可以让执行线程独占使用 CPU 缓存。厂商们也知道，在虚拟化环境中，中断合并可以降低“CPU 使用率”，但会增加延迟。他们了解 NUMA 局部性，甚至把这些都写进了文档里。当然，销售人员来了之后，他们希望与高层战略保持一致，使用最佳优化基准测试，然后就云或虚拟机管理程序支持的问题展开另一场不加任何细节的讨论。没错，这行得通*但附注：你需要三倍的许可证/硬件，而且仍然无法获得最佳性能。人们对底层性能如此缺乏兴趣，技能差距如此之大，以至于似乎只能通过增加抽象层和厂商来掩盖责任。如果珠穆朗玛峰是检验技术领导力还是厂商责任的试金石，那么我们很想知道，究竟是哪一方会坚持到底，还是会在山脚下卖羽绒服。完全正确。一旦你依赖缓存行为、核心绑定和NUMA局部性，平台就不再具有可互换性了。底层细节远比大多数高层策略重要得多。 大多数繁重的AI工作负载仍然会遇到相同的内存层次结构限制。模型规模不断扩大，但芯片内部数据传输的物理机制并没有发生太大变化。理解局部性仍然是获得良好性能的关键。 数组能够为CPU提供它真正需要的东西：连续的内存和可预测的访问模式。这意味着预取器可以真正发挥作用，缓存行可以得到高效利用，并且避免了分散结构带来的指针追踪惩罚。这是保持缓存友好性的最简单方法之一。 机器人多轴运动控制也是如此。第一个轴预热缓存并承受缓存未命中的影响，下一个轴的计算时间缩短了一半。 IBM Telum处理器可以验证这一点，它能够按需将L2缓存转换为L3缓存，并且L4缓存可以被任何其他CPU访问。此外，该芯片的时钟频率始终保持在 5.5 GHz。它包含十个 36 MB 的二级缓存¹，以及扩展的虚拟三级缓存（360 MB）和四级缓存（2.8 GB）。 这是一款令人着迷的芯片。与大多数架构相比，其缓存容量巨大，这让我不禁好奇这会对各级缓存的访问延迟产生怎样的影响。可惜的是，我找不到任何关于 Telum 缓存的公开延迟数据，否则我很想了解 IBM 在实际应用中是如何平衡缓存容量、交换空间距离和命中延迟的。

英文：The Hidden Engine of Performance: It’s All About Where the Data Lives (Cache is the King)

[caption id="attachment_70386" align="alignnone" width="2017"] Q Learning强化学习算法(机器学习/人工智能)[/caption] 强化学习（Reinforcement Learning, RL）是一种让智能体/Agent通过与环境交互、试错学习来获得最优行为策略的机器学习方法。本文用一个简单的 Q-learning 迷宫示例，帮助你快速理解强化学习的基本原理。

强化学习入门：从试错中学习的艺术 Reinforcement Learning 101: The Art of Learning by Trial and Error 深度解析强化学习：Q-Learning算法详解 Deep Dive into Reinforcement Learning: Understanding the Q-Learning Algorithm 机器如何学会自己做决定？强化学习告诉你答案 How Do Machines Learn to Make Their Own Decisions? Reinforcement Learning Explained 从奖励中学习：人工智能的“试错智慧” Learning from Rewards: The Trial-and-Error Intelligence Behind AI

一、什么是强化学习？

强化学习的世界中包含五个关键要素：

• Agent（智能体）：做决策、执行动作的主体
• Environment（环境）：智能体所处的世界
• State（状态）：当前环境的描述
• Action（动作）：智能体可采取的操作
• Reward（奖励）：环境反馈，用来衡量动作的好坏

智能体的目标是学习一个策略 π(a|s)，让它在每个状态下选择最优动作，从而获得最大的累积奖励。 [math]J(\pi) = \mathbb{E}\pi \left[ \sum{t=0}^{\infty} \gamma^t r_t \right][/math] 其中 [math]\gamma[/math]（0 ≤ [math]\gamma[/math] ≤ 1）是折扣因子，用于衡量未来奖励相对于即时奖励的重要程度。

二、Q-Learning 原理

Q-learning 是最经典的强化学习算法之一。它通过学习一个 Q 表（Q-table）来记录每个“状态-动作”对的价值。 更新公式如下： [math] Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s,a)] [/math] 其中：

• [math] \alpha [/math]：学习率（Learning Rate）
• [math] \gamma [/math]：折扣因子（Discount Factor）
• [math] r [/math]：奖励（Reward）
• [math] s' [/math]：下一状态（Next State）

三、迷宫环境设计

定义一个 3×5 的迷宫：

• 0：空地
• -1：墙
• 1：出口（目标）

四、完整 Python 实现代码

import numpy as np
import random

# 1️⃣ 定义迷宫
maze = np.array([
    [0,  0,  0, -1,  1],
    [0, -1,  0, -1,  0],
    [0,  0,  0,  0,  0]
])

n_rows, n_cols = maze.shape
actions = ['up', 'down', 'left', 'right']
Q = np.zeros((n_rows, n_cols, len(actions)))

# 2️⃣ 超参数
alpha = 0.1
gamma = 0.9
epsilon = 0.1
episodes = 500

# 3️⃣ 辅助函数
def is_valid(state):
    r, c = state
    return 0 <= r < n_rows and 0 <= c < n_cols and maze[r, c] != -1

def next_state(state, action):
    r, c = state
    if action == 'up': r -= 1
    elif action == 'down': r += 1
    elif action == 'left': c -= 1
    elif action == 'right': c += 1
    return (r, c)

def get_reward(state):
    r, c = state
    if maze[r, c] == 1: return 10
    elif maze[r, c] == -1: return -1
    return -0.1

# 4️⃣ 训练循环
for episode in range(episodes):
    state = (2, 0)
    done = False

    while not done:
        if random.uniform(0, 1) < epsilon:
            action_idx = random.randint(0, len(actions)-1)
        else:
            action_idx = np.argmax(Q[state[0], state[1]])

        action = actions[action_idx]
        next_s = next_state(state, action)

        if not is_valid(next_s):
            reward = -1
            next_s = state
        else:
            reward = get_reward(next_s)

        Q[state[0], state[1], action_idx] += alpha * (
            reward + gamma * np.max(Q[next_s[0], next_s[1]]) - Q[state[0], state[1], action_idx]
        )

        state = next_s
        if maze[state[0], state[1]] == 1:
            done = True

print("✅ 训练完成！")

# 5️⃣ 查看学到的路径
state = (2, 0)
path = [state]

while maze[state[0], state[1]] != 1:
    action_idx = np.argmax(Q[state[0], state[1]])
    next_s = next_state(state, actions[action_idx])
    if not is_valid(next_s) or next_s in path:
        break
    state = next_s
    path.append(state)

print("🗺️ 学到的路径:", path)

五、运行结果

运行上面的代码后，你会看到类似输出： ✅ 训练完成！ 🗺️ 学到的路径: [(2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4)] 这说明智能体成功学会了走出迷宫 🎯

六、总结

强化学习使机器能够通过反馈学习最优策略，这类似于人类通过经验学习的方式。 Q-Learning 是许多现代强化学习算法的基础，包括深度 Q 网络（Deep Q-Networks, DQN）。 这个简单的示例展示了完整的强化学习循环：探索 → 反馈 → 改进。

• Q 表：保存每个状态-动作的价值
• ε-greedy 策略：平衡探索与利用
• 奖励函数设计：引导智能体形成目标导向行为
• 强化学习思想：通过试错和奖励反馈不断改进策略

强化学习的魅力在于，它不需要显式答案，而是让机器自己“摸索”出最优策略。你可以在此基础上继续扩展，比如加入 matplotlib 动画可视化 或使用 神经网络（Deep Q-Learning） 解决更复杂的任务。 英文：How Do Machines Learn to Make Their Own Decisions? Reinforcement Learning Explained

视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook

如何证明 √2 是无理数 — 两种方法（反证法与几何无限下降）

“√2 是无理数”这一说法的意思是不存在整数 [math]a[/math] 和 [math]b\neq 0[/math] 且 [math]\gcd(a,b)=1[/math]，使得 [math]\sqrt{2}=\dfrac{a}{b}[/math]。

方法一 — 反证法

假设相反，认为 [math]\sqrt{2}[/math] 是有理数。则存在整数 [math]a[/math] 和 [math]b[/math]，满足 [math]b\neq 0[/math] 且 [math]\gcd(a,b)=1[/math]，使得 [math]\sqrt{2}=\dfrac{a}{b}.[/math] 两边平方得： [math]2=\dfrac{a^2}{b^2}\quad\Rightarrow\quad a^2 = 2b^2.[/math] 由 [math]a^2 = 2b^2[/math] 可知 [math]a^2[/math] 为偶数，因此 [math]a[/math] 必为偶数。设 [math]a=2k[/math]，其中 [math]k[/math] 为某整数。 代回去： [math] ^2 = 2b^2 \quad\Rightarrow\quad 4k^2 = 2b^2 \quad\Rightarrow\quad b^2 = 2k^2.[/math] 因此 [math]b^2[/math] 为偶数，故 [math]b[/math] 亦为偶数。 于是 [math]a[/math] 和 [math]b[/math] 都为偶数，这与我们假设的 [math]\gcd(a,b)=1[/math] 矛盾（它们至少有公因子 2）。该矛盾说明原假设错误；因此 [math]\sqrt{2}[/math] 为无理数。

方法二 — 几何无限下降（等腰直角三角形中线构造）

[caption id="attachment_70110" align="alignnone" width="575"] 等腰直角三角形边向斜边作垂线证明根号2不是有理数[/caption] 设一个等腰直角三角形 [math]\triangle ABC[/math]，其中直角在 [math]C[/math]，两条直角边 [math]AC=BC=b[/math]，斜边 [math]AB=a[/math]，因此有 [math]a^2=b^2+b^2=2b^2[/math]。 取 [math]BC[/math] 的中点 [math]E[/math]，从 [math]E[/math] 向斜边 [math]AB[/math] 作垂线，垂足为 [math]D[/math]。 则 [math]\triangle BDE[/math] 也是一个等腰直角三角形，并且与原三角形 [math]\triangle ABC[/math] 相似。记小三角形的斜边和直角边分别为 [math]a'=BE[/math] 与 [math]b'=BD[/math]。 有 [math]a'^2=2b'^2[/math]，从而验证了 [math]\triangle BDE\sim\triangle ABC[/math]。 关键点在于相似（固定比例缩放），小三角形的尺寸是原三角形的一定比例。 从 [math]BC[/math] 取中点 [math]E[/math]，向斜边 [math]AB[/math] 作垂线，交于 [math]D[/math]。 于是 [math]\triangle BDE[/math] 与 [math]\triangle ACB[/math] 相似。我们可以通过“重复减法”来表达边长关系： 因为 [math]\triangle ACE = \triangle ADE[/math]，所以 [math]AC = AD[/math]，因此 [math]AB - AC = AB - AD = BD[/math]。 进一步有 [math]AC - BD = BC - BD = BC - DE = BC - CE = BE[/math]。 因此 [math]AB - AC [/math] 辗转相减 [math] BE - BD[/math]，即 [math]a - b \quad\Rightarrow\quad a' - b'[/math]，其中 [math]a' = BE[/math]，[math]b' = BD[/math]。 由于 [math]\triangle BED \sim \triangle ABC[/math]，我们可以无限次重复这一构造过程。 每次重复相同的操作（取直角边的中点并作垂线到斜边），都会得到一个与原三角形相似的新等腰直角三角形，其边长都按某个固定比例 [math]r[/math] 缩小。 因此，斜边和直角边都会在每一步以几何级数的方式缩小。 这在整数情况下导致“无限下降”矛盾：

• 如果假设存在整数边长满足 [math]a^2=2b^2[/math]，则这种几何构造（或等价的、保持整数关系的中点构造）会产生一个更小的正整数解。
• 无限重复下去会得到一个严格递减的正整数序列，这显然不可能。

因此，不存在这样的整数解，即 [math]\sqrt{2}[/math] 是无理数。 两种方法均证明了 [math]\sqrt{2}[/math] 不能写成两个整数之比。

• 方法一（反证法）利用奇偶性，说明若假设分数为最简形式则会导致分子和分母都为偶数，从而矛盾。
• 方法二（几何无限下降）通过在等腰直角三角形中作中线并利用相似性得到更小的整数解，从而与最小性矛盾。

任一方法都给出清晰而严谨的证明，表明 [math]\sqrt{2}[/math] 是无理数。 [show_file file="/var/www/wp-post-common/justyy.com/math.php"] 英文：Teaching Kids Programming - Two Ways to Prove Square Root of Two is Irrational (proof by contradiction and geometric infinite descent)

Dart 是一种面向对象的编程语言，支持类和基于混入（Mixin）的继承机制。在 Dart 中除 Null 以外的所有类都继承自 Object 类。

1. 基本用法

Dart 中类的基本用法和大部分面向对象语言差不多，这里不作详细介绍，直接从一个简单的示例开始：

// 导入依赖库
import 'dart:math';

class Point {
  // 成员变量
  double? x;    // 默认值初始值为null
  double y = 0; // 初始值为0

  // 构造函数
  Point(double x, double y) {
    this.x = x;
    this.y = y;
  }

  //成员方法
  double distanceTo(Point other) {
    double dx = (this.x ?? 0) - (other.x ?? 0);
    var dy = this.y - other.y;
    return sqrt(dx * dx + dy * dy);
  }

  // 静态方法
  static double distanceBetween(Point a, Point b) {
    return a.distanceTo(b);
  }

  // 重写toString方法
  @override
  String toString() {
    return 'Point($x, $y)';
  }
}

调用也很简单，代码如下：

void main() {
  Point p1 = new Point(0, 0); 
  Point p2 = new Point(3, 4);
  print(p1.distanceTo(p2));             // 5.0
  print(Point.distanceBetween(p1, p2)); // 5.0
  print(p1);                            // Point(0.0, 0.0)
  print(p2);                            // Point(3.0, 4.0)
  print(p2.y);                          // 4.0
}

单看上述代码，几乎分不清究竟是 JavaScript、Java, 还是 Dart，下文主要介绍一些 Dart 相对独特的地方。

[...]

下面是一个简单的函数示例：

bool isNoble(int atomicNumber) {
  return _nobleGases[atomicNumber] != null;
}

虽然 返回值类型 和 参数类型 都可以省略，但建议加上，省略后的代码如下：

isNoble(atomicNumber) {
  return _nobleGases[atomicNumber] != null;
}

如果函数体 只有一条语句，也可以使用 箭头函数：

bool isNoble(int atomicNumber) => _nobleGases[atomicNumber] != null;

其中，=> expr; 语法就是 { return expr; } 的简写形式，与其它语言不同，如果函数体有多条语句，就不能使用这种语法了。

[...]

1. 注释

• 单行注释：以两个斜杠（//）开头，持续到行尾。
• 多行注释：以 /* 开头，以 */ 结尾，可以跨越多行。
• 文档注释：以 /// 或 /** 开头，用于为代码生成文档，在文档注释中使用[](如 [Food]、[feed])，生成文档时，会转换为指向类、方法、变量等的超链接。

2. 变量

以下是变量声明和初始化的示例：

var name = 'Bob';

Dart 是强类型语言，示例中，name 变量的类型会在编译时被推断为 String，也可在声明时显式指定类型，对于局部变量，建议使用 var。如果对象不限于单一类型，可以在声明时指定为 Object 或 dynamic 类型。

[...]

Dart 介绍

Dart 是一种由 Google 开发的开源编程语言，于 2011 年首次发布，目前稳定版本为 Dart 3.x，曾经号称要取代 JavaScript，但过去的几年中一直不温不火，真正使其声名大噪并得到广泛应用的原因是其与 Flutter 框架的完美结合。

如今，Flutter 已成为构建高性能、高质量跨平台应用（Android、IOS、Web、桌面）的首选技术方案之一，尤其是针对希望快速实现跨平台应用的中小团队或个人开发者，Flutter 更是不二之选，而学习 Flutter 的第一步就是先学习其官方编程语言 --- Dart。

边学边记，这篇文章先把 Dart 的开发环境搭建起来！

[...]

近期一直在研究毕业设计，在其中，我涉及到了PaddleYOLO的训练和部署，在网上的教程较少，经过不断努力，我也算是跑出来了，所以在这里分享出来做个记录，防止下次使用又忘记了怎么搞。