题目 Problem 1 (1) 设每次合成仙丹为一次尝试。 在每次尝试中： 合成成功：概率为 $ p $。 产生 $ 1 $ 份仙丹。 消耗 $ 2 $ 份仙果。 合成失败：概率为 $ 1-p $。 产生 $ 0 $ 份仙丹。 消耗 $ 1 $ 份仙果。 我们关注的是平均每份仙果可以得到多少仙丹。这可以理解为仙丹产出的期望值与仙果消耗的期望值之比。 每次尝试中，获得的仙丹数量的期望值 $ \mathbb{E}[\text{仙丹}] $ 为： $$ \mathbb{E}[\text{仙丹}] = 1 \cdot p + 0 \cdot (1-p) = p $$ 每次尝试中，消耗的仙果数量的期望值 $ \mathbb{E}[\text{仙果}] $ 为： $$ \mathbb{E}[\text{仙果}] = 2 \cdot p + 1 \cdot (1-p) = 2p + 1 - p = p + 1 $$ ...
题目 Problem 1.1 设 $ \mathcal{F} $ 是一个有限的 $ \sigma $-代数。定义其中“最小"的元素为其包含于 $ \mathcal{F} $ 中的子集仅为自身和空集，形式化地描述，若 $ A\in \mathcal{F} $ 为“最小”的元素，那么如果 $ B\in \mathcal{F} $ 并且 $ B\subseteq A $，那么一定有 $ B\in \{ \emptyset,A \} $。 可以证明这样的元素存在并且有限：如果不存在，那么我们每次任取一个 $ \mathcal{F} $ 中的元素，都能找到属于它的一个更小的元素，但 $ \mathcal{F} $ 是有限集，所以这样的过程不可能一直重复下去，因此“最小”元素必然存在并且有限。 我们设所有这些不同的“最小”元素为 $ S=\{ A_{1},A_{2},\dots,A_{n} \} $。我们先证明这构成了全空间的一个分划： 首先这些元素肯定两两不相交，否则不满足“最小”的定义。假设 $ A_{i}\cap A_{j}= C\neq\emptyset $，根据“最小”，非空的 $ C $ 是 $ A_{i} $ 的子集，一定有 $ C=A_{i} $，同样也有 $ C=A_{j} $，这就推出了 $ A_{i}=A_{j} $，从而矛盾。 ...
Introduction 条件概率指一个事件在另一个事件发生的条件下发生的概率，用记号 $ \mathbb{P}(A|B) $ 表示，仅在 $ \mathbb{P}(B)>0 $ 时有定义： $$ \mathbb{P}(A|B) = \dfrac{\mathbb{P}(A \cap B)}{P(B)} $$ 可以写成 $$ \mathbb{P}(A \cap B) = \mathbb{P}(B)\cdot \mathbb{P}(A|B) $$ 对于 $ n $ 个事件，连续使用上式，即可得到 $$ \mathbb{P}\left( \bigcap_{i=1}^{n}A_{i} \right) = \prod_{k=1}^{n} \mathbb{P}\left( A_{k}\bigg|\bigcap_{i=1}^{k-1}A_{i} \right) $$ 这个式子被称为 链式法则。 Independence 对于事件 $ A,B $，如果 $ \mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B) $，或者等价地 $ \mathbb{P}(A|B)=\mathbb{P}(A) $，那么我们称 $ A $ 和 $ B $ 是独立的。这表明 $ A $ 或 $ B $ 自己是否发生对对方是否发生没有影响。 ...
Motivation 例题：在圆上“随机”选一段弧，问弧长大于圆周的 $ \frac{1}{3} $ 的概率？（Bertrand paradox） 至少三种自然的“均匀化”模型会给出不同答案： 对弧长参数均匀（在 $ [0, 2\pi) $ 上均匀取长度，再随机起点）。 对端点在圆上独立均匀（等价于随机两点确定弧，需指定取较短或较长弧）。 对中心角或几何构造的中间量均匀（如均匀选角度后裁剪）。 核心问题：如何定义“随机”？不同“随机化”方案导致不同答案。 讨论概率问题必须先明确概率空间（样本空间、事件族与概率测度），否则“概率”无从谈起。 Probability Space 一个概率空间由三元组 $ (\Omega, \mathcal{F}, \mathbb{P}) $ 构成： $ \Omega $：样本空间（一次随机试验所有可能结果）。 $ \mathcal{F} \subseteq 2^{\Omega} $：事件族（允许讨论与运算的集合）。 $ \mathbb{P} : \mathcal{F} \to [0,1] $：概率测度（赋予事件概率）。 记号说明： $ \Omega $：样本空间。 $ 2^{\Omega} $：$ \Omega $ 的幂集（所有子集的集合）。 为什么 $ \mathbb{P} $ 要定义在 $ \mathcal{F} $ 上而非直接在 $ \Omega $ 上？ 离散可数时，取 $ \mathcal{F} = 2^{\Omega} $ 可行，且对单点赋值即可确定所有事件的概率。 连续时不同：单点的概率通常为 $ 0 $，但不可数并可有正概率；且 $ 2^{\Omega} $ 中存在不可测集合，无法一致赋值（见下文 Vitali set 与 Axiom of Choice）。因此需选择一个足够大又可控的 $ \sigma $- 代数作为事件族。 Sigma-Algebra 要求 $ \mathcal{F} $ 构成一个 $ \sigma $- 代数（域）： ...
课程讲义 在这门课里，我们会专注于所谓的 科尔莫哥洛夫（Kolmogorov）的公理体系，它使得我们能够使用数学分析的工具来研究概率。 St. Petersburg Paradox 圣彼得堡悖论。假设一个基于抛硬币赌博的游戏，庄家会一直扔硬币直到结果是正面，如果扔了 $ k $ 次，那么就会给玩家 $ 2^{k} $ 元的奖金。现在的问题是你愿意花多少钱来购买一次玩这个游戏的机会。 一个很自然的想法是计算游戏的期望，那么我们很容易发现期望收益是 $$ \sum_{k \geq 1} 2^{k}\cdot 2^{-k} = 1 + 1 + \dots = +\infty $$ 这说明平均每一轮我们的收益是无穷大，然而在现实生活中你真的愿意花大价钱去玩这个游戏吗？或者可以写一个简单的程序模拟一下就会发现，在比如门票定为 $ 100 $ 元，玩几百局，还是会轻易地输掉几万块钱。我们生活中一个常见的直觉是如果重复一个随机过程足够多次，平均收益就会逐渐趋近于期望收益，这在概率论中叫做大数定律（Law of large numbers），但是在现实生活中我们并没有能力重复足够多游戏轮数去达到这个期望值。那么现在的问题就是如果定价用 $ a\cdot n $ 元来购买 $ n $ 次游戏机会，$ a $ 定为多少是合理的？ 用这门课中后续会学习到的数学工具，我们可以得到答案为 $ \log n $ （这个结果也符合我们实际的直觉）。 随机游走 对二维随机游走问题的一个简化的建模是在 $ \mathbb{Z}^{2} $ 的网格上随机游走，从原点 $ (0,0) $ 出发，每次以 $ \dfrac{1}{4} $ 的概率往上下左右四个方向移动。我们现在询问，这个随机游走的路径是否会无数次回到原点？用 $ T $ 来表示第一次回到原点的时间，那么可以证明无数次回到原点等价于 $ \mathbb{P}[T < \infty] = 1 $ ，也就是 $ T $ 以 $ 1 $ 的概率是有限的，当然目前只能从直觉上去理解，这个写法需要在后续的课程中去严格定义。 ...
Problem 1 证明存在常数 $ c > 1 $ 和 $ N > 0 $，使得当 $ n > N $ 时， $ [n] $ 上树的同构类数量至少为 $ c^n $ 。 证 我们需要的同构类的数量则可以看成 $ n $ 个点无标号的树的数量。需要证明这个数量增长的足够快。 首先根据 Cayley 公式，$ n $ 个点的有标号的树的数量为 $ n^{n-2} $。显然所有无标号的树的数量大于 $ \dfrac{n^{n-2}}{n!} $，因为这里直接假设所有点都是对称的，但是实际上一棵有标号的树并不会对应 $ n! $ 颗无标号的树。我们直接取 $ c=2 $，于是就只需要证明存在 $ N>0 $ 满足在 $ n>N $ 时有 $$ \dfrac{n^{n-2}}{n!} > 2^{n} $$ 我们使用斯特林公式，在 $ n $ 足够大时有 $$ n! \approx \sqrt{ 2\pi n }\left( \dfrac{n}{e} \right)^{n} $$ 带入下界，得到 $$ \dfrac{n^{n-2}}{n!} \approx \dfrac{e^{n}}{\sqrt{ 2\pi}\cdot n^{5 / 2}} $$ 所以只需要证明在 $ n>N $ 时有 $$ (\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n} < \dfrac{e}{2} $$ 对于左式，显然有 $$ \lim_{ n \to \infty } [(\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n}] = 1 < \dfrac{e}{2} $$ 根据极限的定义，我们总能找到一个 $ N $ 满足条件。因此得证！ ...
Problem 1 证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1 对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$ ...
Principle of Inclusion and Exclusion 对于任意有限集合 $ A_1, A_2, \dots, A_n $，容斥原理如下： $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} \left| A_i \right| - \sum_{1\leq i< j\leq n} \left| A_i \cap A_j \right| + \dots + (-1)^{n} \left| \bigcap_{i=1}^{n} A_i \right| $$ 可更紧凑地表示为 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq [n], |S|=k} \left| \bigcap_{i \in S} A_i \right| $$ 或 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| $$ ...
Problem 1 用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。 解： 设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$ ...
考虑上一节引入的二项式定理 $$ (1+x)^{n} = \sum_{k=0}^{n} \binom{ n }{ k } x^{k} $$ 这可以理解成我们把二项系数转换成了一个函数，这使得我们能更有效地操作和分析序列，这个工具被成为生成函数。 Ordinary Generating Functions 给定序列 $ \{ a_{n} \}_{n\geq 0} $，由 $ \{ a_{n} \} $ 定义的普通生成函数 (OGF) 为： $$ G(x) = \sum_{n\geq 0} a_{n}x^{n} $$ 虽然看起来 OGF 并没有被很好的定义，对于和某些数列，这个形式不会收敛，但是实际上生成函数并不能被看成一个真正的函数，它是一个形式幂级数，并且不被要求收敛。 以下是一些生成函数的基础例子： $$ G(x) = 1+x+x^{2}+x^{3} +\dots = \dfrac{1}{1-x} $$ $$ G(x) = 1+ax+a^{2}x^{2} + a^{3}x^{3} + \dots = \dfrac{1}{1-ax} $$ 给定一个序列，写出他的生成函数是很容易的。尽管找到他的闭合形式不容易，但是我们一般不需要这样做。相反，我们需要考虑给定一个闭合形式，需要如何知道其对应的序列。 我们约定 $ [x^{n}]G(x) $ 表示生成函数中 $ x^{n} $ 的系数。 ...
Problem 1 (1) 求 $$ \sum_{k=0}^{n} \binom{ 2n }{ 2k } $$ 解 $$ \begin{align*} & \sum_{k=0}^{n} (-1)^{k}\binom{ n }{ k } = 0 \\ \implies & \sum_{k=0}^{2n} (-1)^{k}\binom{ 2n }{ k } =0 \\ \implies & \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } \end{align*} $$ 同时由于 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } + \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } = \sum_{k=0}^{2n} \binom{ 2n }{ k } = 2^{2n} $$ 得到 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = 2^{2n-1} $$ ...
Product and Sum Principles 加法原理（分类计数） 若一个任务可分解为若干个互斥的子类，第 $ i $ 类有 $ a_i $ 种方案，则总数为 $ \sum_i a_i $。 解释：互斥保证不重不漏，求和即“或”的计数。 乘法原理（分步计数） 若一个任务分为若干个有序步骤，步骤 $ i $ 有 $ b_i $ 种选择且相互独立，则总数为 $ \prod_i b_i $。 解释：有序步骤逐个做决定，“且”的计数对应乘法。 Constructing Maps 有些组合证明可以依赖于构造映射： 单射：不同原像映到不同像，用于证明下界或“可嵌入性”。 满射：像覆盖全体，用于证明上界可达或构造覆盖。 双射：建立集合 $ A $ 与 $ B $ 的一一对应，从而数 $ |A|=|B| $；这是“数某一个量 ⇒ 构造双射”的核心思想。 Twelvefoldway 将 $ n $ 个球放入 $ m $ 个盒子，球与盒子可“可区分/不可区分”，以及盒子容量约束“任意/至多 1/至少 1”。 $ n $ $ m $ 任意 $ \leq 1 $ $ \geq 1 $ 不同 不同 $ m^{n} $ $ m^{\underline{n}} $ $ m!\left\{ {n \atop m} \right\} $ 同 不同 $ \binom{ n+m-1 }{ m-1 } $ $ \binom{ m }{ n } $ $ \binom{ n-1 }{ m-1 } $ 不同 同 $ \sum_{k=0}^{\min(n,m)} \left\{ {n \atop k} \right\} $ $ [n \leq m] $ $ \left\{ {n \atop m} \right\} $ 同 同 $ p_{\leq m}(n) $ $ [n \leq m] $ $ p(n,m) $ “把 $ n $ 个不同球分成 $ k $ 个非空无序盒”对应第二类斯特林数 $ \left\{ {n \atop k} \right\} $。 ...
Exercise 1 首先初等行变换保持了行向量之间的线性关系，因此保证了矩阵的行空间不会改变，从而它的行秩自然也不便。同时对于列秩，这等价于左乘一个一个初等矩阵，此时显然 $ Ax=0 $ 与 $ EAx=0 $ 等价，说明两者有相同的零空间，因此列秩也不边。 对于列变换，和行变换完全同理，也可以证明行秩和列秩都不变。 下面证明矩阵 $ A $ 可以通过初等操作化为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。设 $ \mathrm{rank}(A)=r $，那么我们先通过初等行变换将 $ A $ 化成阶梯矩阵的形式，得到 $ \begin{pmatrix}I_{r} & R \\ 0 & 0\end{pmatrix} $。再对这个结果进行初等列变换，可以直接消除掉 $ R $ 部分中的所有非零元素，并且不影响其他部分。最终就可以化简为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。 Exercise 2 我们需要证明通过任意执行步骤的高斯消元得到的行阶梯矩阵，其主元数量是相同的，从而说明矩阵的秩是一个唯一的值，和消元过程无关。 由于高斯消元本质上就是一系列初等矩阵变换操作，根据第一问我们已经证明了这些操作不会改变矩阵的秩，因此最后得到的阶梯矩阵的秩也不变，最终主元数量就是秩的数量必然相同，等于原来的秩。 Exercise 3 若 $ c=0 $，那么显然有 $$ A\cdot \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \mathbf{0} $$ 说明 $ \text{rank}(A)\neq n $，因此 $ A $ 不可逆，矛盾，所以 $ c\neq 0 $。 ...
Exercise 1 Let $ A $ be an $ n \times n $ matrix. Prove the equivalence between: (i) There is a $ B $ with $ AB = I $. (ii) There is a $ C $ with $ CA = I $. Proof: We show both conditions are equivalent to $ \operatorname{rank}(A) = n $. If there exists $ B $ with $ AB = I $, then $ A $ is surjective, so $ \operatorname{rank}(A) = n $. ...
Exercise 1 Let $ S \subseteq V $ be a subset of vectors in a vector space $ V $. A finite subset $ S' \subseteq S $ is maximally linearly independent in $ S $ if $ S' $ is linearly independent, and for any $ v \in S \setminus S' $ the set $ S' \cup \{v\} $ is not linearly independent. Prove that: (i) $ S' $ is maximally linearly independent in $ S $ if and only if $ S' $ (viewed as a sequence of vectors) is a basis for $ \operatorname{span}(S) $. ...
Exercise 1 Give a basis for the vector space $ M_{m\times n}(\mathbb{R}) $ consisting of all $ m \times n $ matrices. A basis consists of the matrices $ E_{ij} $ for $ 1 \leq i \leq m $ and $ 1 \leq j \leq n $, where $ E_{ij} $ has a 1 in the $ (i,j) $-th position and 0 elsewhere. Exercise 2 Give a basis for $ V = \mathbb{R}^+ = \{x \mid x \in \mathbb{R} \text{ with } x > 0\} $ with $ x \oplus x' = x \times x' $ and $ c \otimes x = x^c $. ...
Exercise 1 (Multiplication of block matrices). Consider two block matrices $$ A = \begin{pmatrix} A_{11} & \cdots & A_{1t} \\ \vdots & \ddots & \vdots \\ A_{p1} & \cdots & A_{pt} \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} B_{11} & \cdots & B_{1q} \\ \vdots & \ddots & \vdots \\ B_{t1} & \cdots & B_{tq} \end{pmatrix} $$ Moreover, for every $ i \in [p] $, $ j \in [t] $, and $ l \in [q] $ the number of columns of $ A_{ij} $ is equal to the number of rows of $ B_{jl} $. In particular, $ A_{ij} \cdot B_{jl} $ is defined. Prove that $$ A \cdot B = \begin{pmatrix} C_{11} & \cdots & C_{1q} \\ \vdots & \ddots & \vdots \\ C_{p1} & \cdots & C_{pq} \end{pmatrix} $$ with $$ C_{il} = \sum_{j \in [t]} A_{ij} B_{jl} $$ for any $ i \in [p] $ and $ l \in [q] $. ...
Exercise 1 What rows or columns or matrices do you multiply to find the second column of $ AB $ ? the first row of $ AB $ ? the entry in row $ 3 $, column $ 5 $ of $ AB $ ? the entry in row $ 1 $, column $ 1 $ of $ CDE $ ? To find the second column of $ AB $, we multiply matrix $ A $ by the second column of matrix $ B $. ...
Exercise 1 Let $ f:\mathbb{R}\to\mathbb{R} $ be a function. Prove that the following are equivalent: (i) There is a constant $ a\in\mathbb{R} $ such that for every$ x\in\mathbb{R} $ we have$ f(x)=ax $. (ii) For all $ x_1,x_2,c,x\in\mathbb{R} $ we have $ f(x_1+x_2)=f(x_1)+f(x_2) $ and $ f(cx)=c\,f(x) $. (i ⇒ ii) Assume there exists $ a\in\mathbb{R} $ such that $ f(x)=a x $ for all $ x\in\mathbb{R} $ . Then for any $ x_1,x_2,c,x\in\mathbb{R} $ , ...
File Allocation Table 要设计并实现一个文件系统，我们首先需要关注并解决存储媒介带来的两大核心挑战： 读写放大 (Read/Write Amplification)：现代存储设备（无论是机械硬盘还是固态硬盘）的物理特性决定了，它们最高效的读写方式是操作连续的大块数据区域，我们称之为一个块 (Block)。如果需要修改一个块中哪怕一个字节的数据，也必须将整个块读入内存、修改、再完整写回。这种“操作少量数据却导致整块数据被读写”的现象就是读写放大，它会严重影响性能。 局部性 (Locality)：程序的内存访问行为通常具有局部性原理 (Principle of Locality)，即在一段时间内，访问的地址会集中在某个区域。文件系统可以通过合理的数据排布，让物理上相邻的数据块在逻辑上也相关联（例如，属于同一个文件），从而在读取一块数据时，可以利用预读机制将后续可能被访问的数据也加载到内存缓存中，提高效率。 在软盘上实现文件系统 我们的需求是为一个存储容量很小的设备（如软盘）设计一个文件系统。在这种场景下，使用复杂的树形数据结构（如 B+ 树）会因为元数据本身占用过多空间而显得浪费。因此，一个简单的链式结构是更合适的选择。 目录的实现 在简单的文件系统中，目录本身可以被实现为一个普通的文件。这个文件的特殊之处在于，它的内容遵循一种固定格式，即一个目录项数组。 1 2 3 4 5 6 // 一个简单的目录项 (dentry) 结构 struct dentry { char filename[256]; // 文件名 unsigned int start_block; // 文件数据起始块的编号 unsigned int size; // 文件大小 (以字节为单位) }; 当我们需要打开一个目录时，文件系统只需读取这个文件的内容，并将其解析为一个 struct dentry 数组即可。 文件数据的存储 用链表来组织一个文件的所有数据块，主要有两种实现思路。 方法一：在每个数据块后放置指针 这种方法非常直观。每个数据块的末尾都留出一小块空间，用于存放下一个数据块的地址或编号。 优点：实现简单，逻辑清晰。 缺点： 极差的随机访问性能：要访问文件的第 N 个数据块，必须从第一个块开始，依次读入前 N-1 个块来找到第 N 块的指针。这需要 N-1 次磁盘 I/O，对于大文件而言是毁灭性的。 空间浪费：每个数据块都不能被 100% 用来存储文件内容，必须牺牲一部分空间给指针。 方法二：将指针集中存放在文件系统的某个区域 为了解决上述问题，我们可以将所有数据块的“链表指针”抽离出来，集中存放在一个被称为文件分配表 (File Allocation Table, FAT) 的核心数据结构中。 FAT 本质上是一个大数组。数组的下标与磁盘上的数据块编号一一对应。数组中存储的值则是该文件链表中的下一个数据块的编号。 ...
目录树 文件的抽象 操作系统将物理存储设备（如磁盘）的复杂性隐藏起来，提供了一个简单、统一的抽象——文件 文件可以看作是一个虚拟的磁盘，即一个命名的、一维的字节序列，支持 read, write, lseek 等操作 这种抽象使得上层应用无需关心数据在物理磁盘上的具体位置和存储方式 目录的引入 当文件数量增多时，需要一种方式来组织和管理它们 操作系统引入了目录 (Directory) 的概念，它是一种特殊的文件，其内容是其他文件或目录的列表 通过将文件和目录组织成一个层次化的树状结构，即目录树，可以方便地对文件进行分类、查找和管理 多数类 Unix 系统遵循 FHS (Filesystem Hierarchy Standard) 的目录结构约定，为软件和用户预测文件位置提供了便利 目录操作 API 操作系统提供了一系列系统调用来操作目录树，核心操作围绕“增删改查” mkdir: 创建一个新的目录 rmdir: 删除一个空的目录 getdents: 读取目录中的条目 (directory entries) link / unlink: 创建或删除文件的链接 链接 链接是文件系统的一个重要特性，它允许一个文件拥有多个名字或存在于目录树的多个位置 链接主要分为两种类型：硬链接和软链接（符号链接） 硬链接 Hard Link 定义：硬链接是让多个目录条目（文件名）直接指向磁盘上同一个文件索引节点 (inode) 每个文件在文件系统中都有一个唯一的 inode，它包含了文件的元数据（如权限、大小、数据块位置等）和数据本身 创建一个硬链接，相当于为同一个 inode 增加了一个新的入口点（文件名） 特性： 所有指向同一个 inode 的硬链接地位平等，没有主次之分 inode 内部维护一个链接计数 (reference count), 只有当这个计数减到 0 时，文件系统才会真正删除该 inode 和对应的数据块，这也是 unlink 系统调用的由来 限制： 不能为目录创建硬链接，以防止在目录树中产生循环 不能跨越不同的文件系统（因为 inode 号只在当前文件系统内唯一） 软链接 Symbolic Link 定义：软链接，也称符号链接 (symlink)，是一个特殊的文件，它的内容是另一个文件或目录的路径 ...
科普性质，简单记录一下 1-Bit 的存储：磁铁 要实现“持久化”存储，核心是要找到一个能反复改写的状态，很容易想到能够利用磁的特性，这就有了磁带的初步想法： 一个长条的带子上面均匀有磁性物质 定位到特定位置之后通过放大感应电流读取 用电磁铁改变磁化方向来写入数据 为了提高存储密度，可以把这样的带子给卷起来，于是就得到了磁带 这样的存储方式主要缺点是几乎不能随机读写（比如磁带收音机需要倒带），一般用于冷数据的存档和备份 为了解决这个缺点，可以想到用旋转的二维平面来替代卷起来的带子，这样读写延迟就不会超过旋转的周期，这就得到了磁鼓： 再在磁鼓的基础上进一步内卷，把用圆盘代替柱面，从而可以堆叠起来，进一步提高了存储密度，这就得到了磁盘： 磁盘作为存储设备的随机读写性能虽然相比磁带有了很大的改善，但是还是需要等待定位到正确的位置，性能仍然不够优秀，为了读写定位到一个扇区通常需要花费几个毫秒的时间，这一点可以通过缓存和调度算法来缓解，让数据尽可能连续存储 当我们在磁盘的基础上把读写头和盘片本体分开，我们就实现了数据的移动，这也就得到了软盘，这是上个数据数据发行的主要方式，虽然性能和可靠性都比较低，但是胜在了便捷、可移动 1-Bit 的存储：挖坑 古人实现持久化存储的方式是在石头上刻字，也就是通过挖坑来存储信息，这种方式可以跨越非常长的时间 而现代工业使我们可以挖出更加精细的坑，从而可以存储更高密度的信息 为了读取这样的信息，我们可以从光学的角度考虑：在反射平面上挖粗糙坑，激光扫过表面，在平面会反射回来，在坑里会发生漫反射，于是我们只要检测是否收到反射光就可以识别是坑还是表面，这也就是光盘 光盘最有趣的特性是容易复制，我们要制造光盘可以先仔细地制造一张反转的盘片，坑的位置对应其表面的突起，之后只需要直接用这个盘片压制加热的塑料再镀上反射膜就可以得到一张光盘，这种方式可以达到极高的写入速度 当然这种挖坑方式的一个重要特性就是不能修改已经写入的内容的，很难填上一个已经挖了的坑（当然通过特殊的制造材料和工艺也是可以做到的），这也就是说里面存储的数据是 append only 的，想要修改之前的内容可以采用可持久化二叉树的结构 光盘作为存储设备，价格低的同时容量和可靠性都比较高，同时顺序读性能一般，随机读性能低并且很难写入，一个重要的应用常见就是数字时代的内容分发 现代这种挖坑的存储方式还有一种应用方式是回归古人石碑的形式，把信息刻在很稳定的材料上来做到永久存储 1-Bit 的存储：电荷 前两种存储介质都存在比较大的缺陷： 磁：依赖机械部件，从而无法避免 ms 级别的延迟 坑（光）：挖坑效率低，同时填坑很困难 而电荷则是一种非常理想的存储介质：电子的密度极高，并且电路的速度极快（还天然并行） 在电路中实现 1-bit 的持久存储，一个想法是我们可以挖一个坑，两种状态分别是： 在坑里填入电子 从坑里放跑电子 而这就得到了闪存 (Flash Memory) ： 其作为存储设备，价格低，容量和可靠性高，而且读写性能极高（由于电路天然并行，所以容量越大，速度越快） 然而，闪存的物理原理也带来了其固有的缺陷，即会磨损 (wear out) 每次放电 (erase) 操作都无法 100% 将电子放干净，这会对存储单元造成微小的、不可逆的损伤 在经历数千或数万次擦写循环后，一些存储单元会因为累积的损伤而失效，无法再可靠地存储数据，这被称为 “死单元 (Dead Cell)” 为了解决闪存的磨损问题，并将其更好地呈现给操作系统，现代固态存储设备（如 SSD、U 盘、SD 卡）内部实际上都集成了一个微型计算机系统 这个系统运行着一层被称为 FTL (Flash Translation Layer) 的固件，它的核心功能之一是 磨损均衡 (Wear Leveling) ...
输入输出设备 Everything is a File 在 Unix-like 系统中，与外部设备交互的核心思想是 Everything is a File 文件描述符 (File Descriptor)：操作系统为上层软件提供了一个统一的抽象，即文件描述符，它是一个指向内核中任何 I/O 对象的“指针”或句柄 统一接口：无论是普通文件、硬件设备（如终端、磁盘）、还是网络连接，都可以通过 open 获得一个文件描述符，然后使用相同的 read/write 等系统调用来进行操作，这极大地简化了应用程序的编写 设备控制器与 MMIO “文件”这个美好的抽象背后，是具体的硬件工作原理 设备控制器 (Device Controller)：每个 I/O 设备都有一个控制器，它是一个包含 CPU、内存和寄存器的微型计算机，作为 CPU 和物理设备之间的桥梁 设备寄存器：控制器通过一组寄存器与 CPU 通信，通常包括： 状态寄存器：用于表示设备当前是否繁忙、是否准备好等 指令寄存器：CPU 写入指令，告诉设备要做什么 数据寄存器：用于在 CPU 和设备之间传输数据 内存映射 I/O (MMIO)：为了让 CPU 能访问这些寄存器，现代系统普遍采用 MMIO (Memory-Mapped I/O)，操作系统会将设备的寄存器映射到物理内存地址空间中的特定区域，这样一来，CPU 就可以像访问普通内存一样，使用标准的 load/store 指令来读写设备寄存器，从而实现对设备的控制 GPIO GPIO (General-Purpose Input/Output) 是理解 I/O 设备原理最直观的例子，GPIO 就是一个物理引脚，可以通过编程设置为输入或输出模式 通过 MMIO，一个 GPIO 引脚的电平状态被映射到一个特定的内存地址，当 CPU 向这个地址写入 1 时，引脚就变为高电平；写入 0 时，则变为低电平，这个过程将一条内存写指令直接转化为了一个物理世界的动作（比如点亮一个 LED） ...
CPU 内的并行编程 CPU 的功耗 $ P=C\cdot V^{2}\cdot f $ 导致纵使有更大的电路，热功耗限制了性能上限，从而有一堵“功耗墙”限制了 CPU 的性能，为此需要考虑如何在降低 $ V $ 和 $ f $ 的同时用面积换性能 有两个思路： 让一条指令能处理更多的数据：SIMD (Single Instruction, Multiple Data) “一条指令” 浪费的能量大致是定数 处理的数据越多，浪费越少 用更多更简单的处理器：多处理器系统、异构多处理器 同等面积，处理器越简单，数量越多 异构计算：最经典的例子是大小核架构（如 Apple M1） SIMD SIMD 的核心思想是在硬件层面实现数据级并行，它通过引入专门的硬件单元来达成这个目标： 宽位寄存器 (Wide Registers)：CPU 内部增加了比通用寄存器宽很多的专用寄存器 Intel 的 SSE 指令集引入了 128 位的 XMM 寄存器，而最新的 AVX-512 拥有 512 位的 ZMM 寄存器 这些宽位寄存器可以一次性装入多个数据元素，比如一个 128 位的寄存器可以同时容纳 4 个 32 位的浮点数，或者 16 个 8 位的整数 这些被打包在一起的数据被称为 Vector 向量处理单元 (Vector ALU)：CPU 内部也配备了能够对整个向量进行并行计算的 ALU ...
并发编程的核心抽象是实现一个计算图，计算发生在节点上，边表示节点之间的依赖关系，同时计算图在运行时可能是动态变化的 使用条件变量、锁、信号量等 api 去实现计算图并不是一个优雅的实现方式，因为这样会在代码中引入众多干扰代码，也可能导致一些问题 为此可以增加一些功能受限的语法，可以在同样描述计算图的功能下减少了许多潜在的问题 高性能计算中的并行编程 在高性能计算中，计算图通常易于静态切分，尤其适用于物理模拟的网格划分，为此 HPC 发展出多种高效的并行编程模型，具体学习可以参考 SJTU HPC 学习手册 MPI: 分布式内存并行 每个 MPI 进程有独立的内存空间，进程间通过显式消息传递（发送/接收）交换数据 OpenMP: 共享内存并行 多个线程在同一地址空间中并行执行，所有线程可以直接访问相同的数据，使用 #pragma omp 指令实现并行化 对非计算机专业来说非常友好，只需要在正常的代码上面加上编译指令即可，能轻松实现高效的并行优化 CUDA: GPU 异构并行 CPU 调度，GPU 执行大规模并行计算 概念： 核函数 (Kernel) ：在 GPU 上并行执行的函数 线程层次：线程 (threadIdx) 组成线程块 (blockIdx)，线程块组成网格 (gridDim) 内存层次：寄存器、共享内存（块内高速）、全局内存（所有线程可访问） 我们身边的并发编程 从 Web 1.0 到 Web 2.0 在 Web 时代用的最广泛的是 Javascript Asynchronous JavaScript and XML (Ajax; ~1999) 允许网页实现“后台刷新” jQuery $ (2006): A DOM Query Language (编程抽象) Web 2.0 时代的并发编程 线程开销大，并且大多数 Web 开发者难以进行并发编程 ...
数据竞争 大多并发 bug 最后都会体现为数据竞争 (Data Race) 对于顺序程序而言，函数 f() 返回之后就已经完成了所有的状态修改，对于其他部分而言这个修改是立即生效的；如果对于并发程序而言模式的切换也在瞬间完成，那就不会导致并发的问题 然而实际上模式的切换需要时间，执行的操作在未来一段时间之后才会就绪，但是我们在实际编程时总是容易有“立即生效”的肌肉记忆，这就导致了并发问题的可能性 不过对于函数式编程而言，操作不存在对外状态的修改，没有副作用（只会操作局部变量），这就不会导致并发问题 Data Race 发生的实质是不同的线程同时访问同一内存，并且至少有一个是写，形象的理解就是不同的内存访问在“赛跑”，跑赢的操作先执行 Not that easy: 虽然我们将数据竞争形象地比喻为“赛跑”，但实际上，哪一个操作能“跑赢”并没有想象中那么简单和确定，其复杂性主要体现在以下几个方面 弱内存模型 (Weak memory model)：在现代处理器架构中，为了提升性能，处理器可能会对内存操作进行重排序。这意味着，不同的线程或“观察者”在不同时间点看到共享内存的状态可能是不一致的。一个线程对内存的写入操作，可能不会立即对所有其他线程可见，导致不同线程观察到不同的结果。这种内存模型的一致性问题使得确定哪个操作“先发生”变得非常困难且不确定。 未定义行为 (Undefined Behavior)：从 C++11 标准开始，数据竞争被明确规定为未定义行为。这意味着，如果你的程序发生了数据竞争，编译器可以自由地产生任何行为，无论是崩溃、产生错误结果，还是看似正常运行但结果不可预测。这使得数据竞争成为非常危险且难以调试的并发错误，因为它的表现可能是不确定、不稳定的。 多线程与多内存的复杂交互：在实际的并发程序中，通常会有多个线程同时访问多个共享内存位置。这些线程和内存之间存在复杂的读（R）写（W）交互。一个线程对一个内存位置的写入可能影响到其他多个线程对该位置的读取，同时，多个内存位置之间也可能存在复杂的依赖关系和缓存一致性问题。这种错综复杂的交互网络进一步加剧了数据竞争的不可预测性。 为了消灭数据竞争，我们需要保证程序的 serializability ，可能竞争的内存访问要么互斥，要么同步 实际编程中遇到的数据竞争 bug 大多属于上错了锁和忘记上锁两种情况的变种 Case 1: 上错了锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { spin_lock(&B); sum++; spin_unlock(&B); } Case 2: 忘记上锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { sum++; } 但是实际系统面临的情况比这复杂的多，因为 内存可以是地址空间的任何内存，比如全局变量、堆内存分配的变量、程序的栈…… 访问可以发生在任何代码，比如自己的代码、框架代码、一行没读到的汇编指令、某条 ret 指令 “一行没读到的汇编指令”造成的访问的情况有编译器优化造成的指令重排、硬件层面弱内存模型的内存访问重排、还有一些高层语言操作的隐式内存访问 实际系统中虽然难以避免，但是会尽可能保证底层的结构对上层尽可能封闭来防止这种错误 死锁 死锁 (Deadlock) 是指一个群体中的每个成员都在等待其他成员（包括自身）采取行动的状态 死锁有两种： AA-Deadlock: 自己等待自己 1 2 3 4 5 6 7 lock(&lk); // lk->locked == ✅; proceed ... // Possibly in interrupt handler lock(&lk); // while (lk->locked == ❌) ; 这样的错误虽然看起来很傻，但是在真实程序复杂的控制流中是可能出现的 ...
信号量 互斥锁在某种意义上也可以认为实现了 “happens-before” 的依赖关系—— release 必然发生在 acquire 之前。我们可以试着利用这种依赖关系来实现计算图的调度：为每条边分配一个互斥锁，代表数据或前置任务的完成；一个节点必须获得所有入边对应的互斥锁才能开始计算，计算完成后，就释放所有出边对应的互斥锁，通知下游节点输出就绪（但是这种直接使用互斥锁作为边状态信号的方式是 undefined behavior，因为互斥锁主要用于保护临界区，其释放通常要求由持有它的线程完成，若释放未曾获取的锁，则行为未定义） 我们可以从这种想法中抽象出其本质，也就是用一个“信号”去获取资源的许可，类似餐厅的取号吃饭 这种信号的思想很适合用来管理计数类型的同类资源，比如停车场的空位，为了实现这种 producer-customer 的问题，用 条件变量 可以轻易解决，进入的条件就是存在空位 count < capacity ，那我们从减少变量的角度出发，这实际上也就是剩余空位的数量大于零，我们停车相当于消耗了一个车位，离开相当于创造了一个车位，这也就得到了所谓“信号量”的机制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void P(sem_t *sem) { // Prolaag - try + decrease/down/wait/acquire mutex_lock(&sem->lk); while (!(sem->count > 0)) { cond_wait(&sem->cv, &sem->lk); } sem->count--; // 消耗一个信号 (车位) mutex_unlock(&sem->lk); } void V(sem_t *sem) { // Verhoog - increase/up/post/signal/release mutex_lock(&sem->lk); sem->count++; // 创建一个信号 (车位) cond_broadcast(&sem->cv); mutex_unlock(&sem->lk); } 根据这个一路推出信号量的思路，或许可以认为这是互斥锁的扩展 ...
同步和条件变量 互斥实现了原子性，但是无法实现确定性，也就是无法正确实现 “happens-before” 的关系 因此需要引入条件变量来实现线程的同步，形成受控制的并发事件的发生顺序（可以用乐团指挥来类比），把一系列不确定的状态在某一个时间点同步到了一个确定的状态，将发散的并发程序状态 “收束” 实现同步 实现 $ A\to B $： 1 2 3 4 5 6 7 A; can_proceed = true; (signal) while(!can_proceed); B // B: wait until the condition is satisfied 这样的思路大致正确，但是自选的循环有很大的性能问题，因此需要一个更加底层的机制来帮助实现这一点 最理想的 API 是 wait_until(cond) ，但是过去为了简化设计，变成了 条件不满足时等待：wait - 直接睡眠等待 条件满足时继续：signal/broadcast - 唤醒所有线程 （小时候的 scratch 编程其实已经有了这样的思想😂） 在 c++ 代码中我们可以把条件放到 $ \lambda $ 表达式中： 1 2 3 4 5 6 7 8 9 10 11 12 std::mutex mtx; std::condition_variable cv; void T_player() { std::unique_lock lk(mtx); cv.wait(lk, []{ return can_proceed; } ); cv.notify_all(); lk.unlock(); } 注意条件变量在等待时需要带着一把锁（需要确保检查和等待是原子操作） ...
本文简要介绍通用矩阵乘（GEMM，General Matrix Multiplication）优化的基本概念和方法。GEMM 是 HPC 领域中最基础且计算密集型的工作负载之一。在人工智能、科学模拟和图像处理等领域，它的性能直接影响着整个应用程序的效率。虽然其数学概念简单，但高效的 GEMM 实现却需要对计算机体系结构有深刻的理解，包括缓存、SIMD 指令集和并行化技术。 Naive GEMM GEMM 通常定义为 $ C = A \times B $，对于矩阵 $ A \in \mathbb{R}^{M \times K} $，矩阵 $ B \in \mathbb{R}^{K \times N} $，其乘积矩阵 $ C\in \mathbb{R}^{M \times N} $ 可以表示为 $$ C_{i,j} = \sum_{k=0}^{K-1} A_{i,k}\times B_{k,j} $$ 对应的朴素代码通常如下（默认行主序存储）： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 void gemm_naive(int M, int N, int K, const float* A, const float* B, float* C) { for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { C[i][j] = 0.0f; // 初始化 C[i][j] } } for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { for (int k = 0; k < K; ++k) { C[i][j] += A[i][k] * B[k][j]; } } } } 分析： ...
如何更好更快地访问内存是 HPC 中最大的瓶颈之一，仅仅了解 SIMD 或并行编程接口是不足够的，本文将梳理计算机的内存层次结构、缓存友好编程、内存墙现象、NUMA 架构以及预取技术。 Understanding Memory Hierarchy 为了充分利用现代 CPU 的性能，我们必须理解数据是如何在不同层级的内存组件之间流动的。 Registers, Caches, and Main Memory 寄存器 (Registers)： CPU 内置的、容量最小但速度最快的数据存储单元，用于存储正在被 CPU 活跃操作的数据。CPU 直接在寄存器上执行大部分计算。 缓存 (Cache)： 位于 CPU 和主内存之间的小容量、高速存储区域。它们的目的是通过存储最可能被 CPU 再次访问的数据来减少对主内存的访问延迟。 L1 缓存 (Level 1 Cache)：最小、最快，通常分为数据缓存 (L1d) 和指令缓存 (L1i)，每个 CPU 核心独有。其访问速度与 CPU 核心时钟周期相近。 L2 缓存 (Level 2 Cache)：比 L1 大且慢，每个 CPU 核心独有或由几个核心共享。 L3 缓存 (Level 3 Cache)：最大、最慢的缓存，通常由同一 CPU 插槽上的所有核心共享。 主内存 (Main Memory/RAM)： 容量远大于缓存，但访问速度慢得多。当数据不在任何缓存中时，CPU 必须从主内存中获取。 TLB (Translation Lookaside Buffer)： TLB 是一个专用的高性能缓存，用于存储虚拟地址到物理地址的转换映射。当 CPU 访问一个虚拟地址时，它首先检查 TLB。如果找到对应的物理地址（TLB 命中），则可以快速进行内存访问；如果未找到（TLB 未命中），则需要查询页表，这将导致显著的延迟。理解 TLB 对于优化内存页访问模式，尤其是在处理大型数据集时至关重要。 ...
1. What is SIMD? SIMD，即 Single Instruction Multiple Data ，是一种并行计算的模式。传统的单指令单数据模型，也就是一条指令 CPU 只能处理一份数据，这在科学计算和图像渲染等大量数据密集的任务中是非常低效的。 SIMD 的核心思想是用一条指令同时对多个数据进行操作，现代的 CPU 为此设计了特殊的硬件单元，包括宽位（比如 128、256 或 512 位）的向量寄存器 (Vector Registers) 和能够操作这些寄存器的向量指令 (Vector Instructions)。一个向量操作可以同时完成多个标量操作，从而实现数据并行 (Data Parallelism)，提高效率。假设一个 256 位的向量寄存器可以容纳 8 个 32 位浮点数，一条向量加法指令就可以一次性完成 8 个浮点数的加法，理论上将这部分计算的吞吐量提升至原来的 8 倍；并且相比于执行 8 条独立的标量加法指令，CPU 只需要获取并解码一条向量加法指令，这降低了指令流水线的压力。 2. How SIMD Works 要理解 SIMD 的工作原理，需要了解两个核心概念：向量寄存器和向量指令。 2.1. Vector Registers 向量寄存器是 CPU 内部的特殊存储单元，其宽度远大于通用寄存器。不同的 Instruction Set Architecture (ISA, 指令集架构) 提供了不同宽度和名称的向量寄存器。 SSE (Streaming SIMD Extensions)：提供了 128 位的 XMM 寄存器。 AVX (Advanced Vector Extensions)：提供了 256 位的 YMM 寄存器。 ...
1. Why Memory Performance Matters in HPC? 在 HPC 领域，我们常常关注 CPU 的浮点运算能力 (FLOPS)，但真正的性能瓶颈往往不在于计算本身，而在于数据访问。现代 CPU 的计算速度远超于内存的访问速度，这种差距被称为内存墙 (Memory Wall)。程序的大部分时间可能都消耗在等待数据从内存加载到 CPU 寄存器的过程中。因此，优化内存访问模式，最大限度地利用 Cache，是提升 C/C++ 程序性能至关重要的一环。 2. Memory Alignment 内存对齐是指一个数据对象的内存地址是其自身大小或特定字节数（通常是 2 的幂）的整数倍。例如一个 4 字节的 int 类型变量，如果其内存地址是 4 的倍数（如 0x...00, 0x...04, 0x...08），那么它就是内存对齐的。 2.2 Why is Alignment Important? CPU 并不是逐字节地从内存中读取数据，而是以块（通常是缓存行 (Cache Line)，例如 64 字节）为单位进行读取。 性能提升：如果一个数据跨越了两个缓存行，CPU 就需要执行两次内存读取操作才能获取这一个数据，这会浪费一倍的时间。如果数据是对齐的，就可以保证它完整地落在一个缓存行内，CPU 只需一次读取操作。 硬件要求：许多现代 CPU 指令集，尤其是用于并行计算的 SIMD 指令强制要求操作的数据必须是内存对齐的，对未对齐的数据执行这些指令可能会导致程序崩溃或性能急剧下降。 2.3 How to Achieve Alignment in C/C++? C++11 alignas：这是 Modern C++ 的标准方式，可以指定变量或类型的对齐要求。 1 2 3 4 5 6 7 8 // 声明一个按 64 字节对齐的数组 alignas(64) float aligned_array[1024]; // 定义一个结构体，使其每个实例都按 32 字节对齐 struct alignas(32) MyData { float a; int b; }; GCC/Clang __attribute__((aligned(N)))：特定于编译器的扩展。 1 2 // 声明一个按 64 字节对齐的数组 float aligned_array[1024] __attribute__((aligned(64))); 动态内存对齐：标准的 malloc 不保证特定的对齐方式（通常只保证基本类型的对齐）。需要使用专用函数。 1 2 3 4 5 6 #include <stdlib.h> // C11 标准 // 分配 1024 个 float，并按 64 字节对齐 float* dynamic_array = (float*)aligned_alloc(64, 1024 * sizeof(float)); free(dynamic_array); // 必须用 free 释放 3. Data Locality 数据局部性是缓存工作的基本原理，也是性能优化的核心。描述了 CPU 访问内存地址的集中程度。 ...
HPC 领域中，除了基于共享内存的 OpenMP, 还有一种更广泛应用于分布式内存系统的并行编程范式——消息传递接口 (MPI)。MPI 不依赖于共享内存，而是通过进程间的显式消息传递来实现数据交换和同步，从而能支持更大规模的集群计算，是构建大规模 HPC 集群不可或缺的工具。 1. What is MPI? MPI (Message Passing Interface) 是一种用于分布式内存系统并行编程的标准化通信协议和库函数规范。它定义了一套可移植的函数接口，允许在并行计算环境中独立运行的进程之间进行消息传递，从而实现数据交换和协同工作。MPI 不指定如何启动进程，也不要求所有进程在同一台机器上，这使得它非常适合用于集群或多节点环境中的大规模并行计算。 2. The MPI Programming Model 分布式内存模型 在分布式内存模型中，各个处理节点可以独立运行自己的进程，使用自己的本地内存来存储和处理数据。每个进程的内存是私有的，其他进程无法直接访问它们。如果一个进程需要访问另一个进程的数据，就必须通过显式的消息传递机制将数据从一个进程发送到另一个进程。同一个节点（服务器）内部需要借助高速数据总线等硬件实现，而跨节点的通信通常由网络连接来实现，比如通过高速以太网、IB（InfiniBand）等。 核心概念 进程 (Process)：一个 MPI 程序由一个或多个独立的进程组成。这些进程通过调用 MPI 库函数来进行通信。 通信子 (Communicator)：一个通信子（MPI_Comm）定义了一个可以互相通信的进程组。最常用的通信子是 MPI_COMM_WORLD，它包含了程序启动时的所有进程。 秩 (Rank)：在同一个通信子内，每个进程都被赋予一个唯一的整数标识，称为秩。秩的范围是从 0 到 进程总数 - 1。 消息传递 (Message Passing)：进程间通信的核心机制，分为两大类： 点对点通信 (Point-to-Point)：在两个指定的进程之间进行。 集体通信 (Collective)：在一个通信子内的所有进程共同参与的通信。 通信协议：MPI 提供了多种通信协议，如阻塞通信（Blocking）、非阻塞通信（Non-blocking）、同步通信（Synchronous）等。 3. Basic Functions and Concepts 一个基础的 MPI 程序总是包含初始化、执行并行代码和结束这几个部分。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <mpi.h> #include <stdio.h> int main(int argc, char** argv) { // 1. 初始化 MPI 环境 MPI_Init(&argc, &argv); int world_size; int world_rank; char processor_name[MPI_MAX_PROCESSOR_NAME]; int name_len; // 2. 获取通信子信息 MPI_Comm_size(MPI_COMM_WORLD, &world_size); // 获取总进程数 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank); // 获取当前进程的秩 // 获取处理器名称 (可选) MPI_Get_processor_name(processor_name, &name_len); // 3. 基于秩执行不同的代码 printf("Hello world from processor %s, rank %d out of %d processors\n", processor_name, world_rank, world_size); // 4. 结束 MPI 环境 MPI_Finalize(); return 0; } MPI_Init()：初始化 MPI 执行环境，必须是第一个被调用的 MPI 函数。 MPI_Comm_size()：获取指定通信子（这里是 MPI_COMM_WORLD）中的总进程数。 MPI_Comm_rank()：获取当前进程在指定通信子中的秩。 MPI_Finalize()：清理并结束 MPI 环境，必须是最后一个被调用的 MPI 函数。 4. Point-to-Point Communication 点对点通信是 MPI 中最基本的通信模式，用于在一个进程向另一个进程发送数据。核心操作是 Send 和 Recv。 ...
由于高性能计算场景下的并行编程任务的特性，OpenMP 可以通过简单受限的语法极大地化简了并行编程的复杂性，在普通的串行代码中添加一些指令就能够实现高效并行化。 1. What is OpenMP? OpenMP (Open Multi-Processing) 是一种用于共享内存多处理器系统并行编程的 API。它通过在 C, C++, 或 Fortran 代码中添加 #pragma 的方式，让开发者可以轻松地将串行代码并行化，而无需手动管理复杂的线程创建、同步和销毁过程。 2. The OpenMP Programming Model 共享内存模型：所有线程在同一个地址空间中共享数据。这意味着不同线程可以访问相同的内存位置，并且可以共享变量的值。 共享变量：在并行区域中，默认情况下，大多数变量是共享的，即所有线程都可以访问和修改这些变量的值。 私有变量：某些情况下，我们可能希望每个线程拥有变量的私有副本，这样不同线程之间不会相互干扰。OpenMP 通过 private 指令指定这些变量。 数据竞争（Race Condition）：由于多个线程同时访问和修改共享变量，可能会导致数据竞争问题。为了避免这种情况，OpenMP 提供了同步机制，如 critical 和 atomic 等。 并行区域（Parallel Region）：是 OpenMP 编程的核心概念。它是由编译器指令 #pragma omp parallel 指定的一段代码，告诉 OpenMP 在这段代码中创建多个线程并行执行。 Fork-Join 执行模型：从单线程开始执行，进入并行区域开始并行执行，在并行区域结尾进行同步和结束线程。 3. Core Directives and Constructs OpenMP 的功能主要是通过编译指令（Directives）和相关的子句（Clauses）来实现的。 parallel：用于创建一个并行区域。 1 2 3 4 5 #pragma omp parallel { // 这部分代码将由多个线程同时执行 printf("Hello from thread %d\n", omp_get_thread_num()); } for：用于并行化 for 循环，必须与 parallel 结合使用。它会自动将循环迭代分配给不同的线程，这是 OpenMP 最常用、最高效的指令之一。 1 2 3 4 #pragma omp parallel for for (int i = 0; i < n; i++) { // 循环的 n 次迭代会被分配给不同线程 } sections：用于将不同的、独立的任务代码块分配给不同线程。适用于任务并行而不是数据并行。 1 2 3 4 5 6 7 #pragma omp parallel sections { #pragma omp section { /* task A */ } #pragma omp section { /* task B */ } } 4. Data Scoping 数据作用域定义了并行区域中变量如何被线程共享或者私有，OpenMP 通过子句 clauses 来控制变量属性。 ...
推理效率对于 llm 是一个至关重要的问题。当模型生成文本时，尤其是以自回归方式逐词生成时，效率瓶颈会变得非常明显。KV Cache 就是为了解决这一问题而诞生的技术。 1. What is KV Cache? KV Cache，全称 Key-Value Cache，是一种优化技术，用于加速 Transformer 架构在自回归生成过程中的推理速度。它的核心思想是缓存并重用在注意力机制中计算得到的 Key (K) 和 Value (V) 向量。 2. Transformer Attention Mechanism Review 要理解 KV Cache，首先需要对 Transformer 架构中的自注意力机制有一个基本认识。自注意力机制允许模型在处理序列中的某个词时，考虑序列中所有其他词的重要性。 每个输入 token（词或子词）在进入注意力层时，都会被转换成三个不同的向量： Q 向量：代表当前 token 的“查询”信息 K 向量：代表所有 token 的“键”信息，用于与 Query 进行匹配 V 向量：代表所有 token 的“值”信息，用于加权求和，得到最终的输出 自注意力机制的计算过程为以下步骤： 计算 Query 与所有 Key 的点积，得到注意力分数 将注意力分数进行缩放，除以 $ \sqrt{d_k} $（$ d_k $ 是 Key 向量的维度) 对缩放后的分数进行 Softmax，将其转换为注意力权重，表示每个 token 对当前 token 的重要性 将注意力权重与 Value 向量进行加权求和，得到当前 token 的注意力输出 公式为： $$ \text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V $$ 其中矩阵 $ Q,K,V \in \mathbb{R}^{L \times d} $ ，$ L $ 为当前上下文长度 ...
去年超算队招新唯一没有解决的一道题，今在 Gemini 老师的帮助下成功解决，决定重写一份题解报告。 Description 题目传送门 题目要求参赛者优化一个 C 语言函数 rotate_the_bit_vector，函数功能是对一个 bit vector 中的一个指定子区间进行循环旋转操作。 具体而言，题目给的 bit_vector 是一种内存紧凑的数据结构，将 8 个 bit 打包存储到一个字节中。参赛者需要在只修改 submit_func.c 一个文件的前提下重写其中的 rotate_the_bit_vector 函数，使其在大规模数据时尽可能快。 最后评分程序会通过三个不同的 benchmark (-s, -m, -l) 来衡量，每个测试中的数据规模会随着层数的增加而几何级增长，最终的得分取决于规定时间内能到达的“层数”，层数越高。说明性能越好，最终分数也越高。 Analysis Three-Reversal Algorithm 假设要移动的区间长度为 $ n $ ，需要移动 $ k $ 位；由于向右旋转 $ k $ 位可以等效于向左旋转 $ n-k $ 位，因此只讨论向左的移动。 题目提供了一个初始的性能极差的实现，通过逐位移动 $ k $ 次来实现 $ k $ 位循环旋转，复杂度为 $ O(n^{2}) $。根据这个原始实现很容易想到一个初步的优化方案： 问题的核心是把数组 [A|B] 变成 [B|A] ，一个经典的算法是三步翻转法：如果我们把翻转操作记为 ' ，A' 表示数组 A 前后反转，那么可以发现原问题的操作实际上等价于三次翻转操作：[A'|B']' = [B|A] ，复杂度为 $ O(n) $ ，代码如下： ...
Abstract 现有 TTA 方法在处理图数据时，对节点属性偏移有效，但是对图结构偏移（同质性、节点度的变化）效果很差。原因是结构偏移会严重破坏节点表示的质量，使不同类别的节点在特征空间中混在一起。为此论文提出了 Matcha 框架，通过在测试的时候自适应地调整 GNN 的“跳数聚合参数 (hop-aggregation parameters)”，并且引入了新的预测感知的聚类损失函数来表示恢复节点表示的质量，从而有效应对结构偏移，并能和现有 TTA 方法相结合，进一步提高性能。 Introduction GNN 的脆弱性：GNNs 在各类图任务上的表现依赖于训练数据和测试数据分布相同的假设，然而在现实世界中，图的分布常常会发生变化（分布偏移），分为： 属性偏移 (Attribute Shift)：节点的特征发生变化。例如不同社交平台，即使用户一样，其账号的内容也会因为平台差异而不同。 结构偏移 (Structure Shift)：节点的连接方式发生变化。比如工作平台用户倾向于连接同事，生活平台用户倾向于连接家人朋友。这种连接模式的变化就是结构偏移，具体表现为同质性 (Homophily) 和 节点度 (Degree) 的变化。 TTA 的局限性：TTA 允许一个预训练好的模型在不访问原始训练数据的情况下，利用无标签的测试数据进行自适应调整 。目前 TTA 在计算机视觉领域处理图像损坏、风格变化等属性偏移问题上很成功 。然而为图像处理设计的 TTA 方法直接应用到图上时，其在处理图结构偏移时的性能提升非常有限，几乎失效。 Analysis 两种偏移方式对 GNN 的影响存在本质不同。 Perliminaries 论文聚焦于 GTTA 任务。一个 GNN 模型可以被看成两个部分的组合，一个特征提取器 $ f_{S} $ ，一个分类器 $ g_{S} $ ，通常是一个线性层。 两种偏移的正式定义： 属性偏移：源图和目标图中，节点的条件概率分布不同 $ \mathbb{P}^{S}_{x | y} \neq \mathbb{P}^{T}_{x | y} $ 。 结构偏移：图的邻接矩阵和标签的联合分布不同，即 $ \mathbb{P}^{S}_{A \times Y} \neq \mathbb{P}^{T}_{A \times Y} $ 。论文主要关注两种具体的结构偏移： 度偏移：源图和目标图的平均节点度数不同。 同质性偏移：源图和目标图的同质性水平不同。其中图的所有节点同质性的平均值 $ h(\mathcal{G}) = \dfrac{1}{N}\sum_{i}h_{i} $ ，单个节点 $ v_{i} $ 的同质性计算公式为： $$ h_{i} = \dfrac{\left| \{ v_{j} \in \mathbb{N}(v_{i}): y_{j} = y_{i} \} \right|}{d_{i}} $$ 其中 $ y $ 表示节点标签，$ d $ 表示节点度数。 Impact of Distribution Shifts 通过数学建模来显示两种偏移的不同影响机制。 ...
Abstract 问题：现有 EEG 情绪识别方法对长期上下文信息关注不足，导致跨被试泛化能力减弱 方案：提出 Emotion Transformer (EmT) ，为 Graph-Transformer 混和架构 核心模块： TGC：将 EEG 信号转换为时序图序列 RMPG：使用残差多视图金字塔 GCN，学习动态、多尺度的空间连接模式，生成 token（核心） TCT：使用任务自适应的 Transformer，学习 token 序列上下文（核心） TSO：输出分类/回归结果 成果：在多个公开数据集的广义跨被试任务上面超过了 baseline Introduction & Related Work 为什么 EEG 难以使用跨被试 (cross-subject) 的场景？ 个体差异：不同被试生理结构和认知策略差异，导致 EEG 模式不同 低信噪比：EEG 信号容易受到外源噪声干扰（肌电、眼电……） 目标是学习一种跨被试共享、具有泛化能力的情绪表征 Gpaph Neural Networks 核心思想：EEG 数据具有非欧图结构，适合使用 GNN 来处理 代表工作： ChebyNet：使用切比雪夫多项式近似光谱滤波，EmT 模型中采用其作为 GCN 层 GCN：通过局部一阶聚合近似光谱滤波 DGCNN / RGNN：使用 GNNs 提取 EEG 空间信息；依赖单一的邻接矩阵，忽略时序上下文，具有局限性；而 EmT 通过多视图可学习邻接矩阵和时序图来弥补 Temporal Context Learning 核心理念：情绪是连续认知过程，EEG 信号中嵌入时序上下文信息 代表工作： LSTM / TCN / TESANet / Conformer / AMDET 局限性：这些方法通常从扁平化的 EEG 特征向量学习，可能未能有效学习空间关系；EmT 则通过并行 GCN 和 STA 层更有效地捕捉时空信息 EEG Emotion Recognition 核心理念：EEG 情绪识别面临个体差异大、信噪比低等挑战，需提取光谱、空间、时序特征 代表工作： GCB-Net / TSception 局限性：没有关注长时序上下文信息 Method EmT 是一个端到端的框架，包含四大模块： ...
Introduction TTA 在回归任务上的局限：为分类任务设计，一般基于熵最小化和特征对齐；熵最小化不适用，回归模型产生单一值，不产生概率分布；简单特征对齐对回归模型效果不佳，可能反而会稀释需要学习的特征 Problem Setting 考虑一个回归模型 $ f_\theta: \mathcal{X} \to \mathbb{R} $，可以进一步分解为特征提取器 $ g_\phi: \mathcal{X} \to \mathbb{R}^D $（从输入 $ \mathcal{X} $ 提取 $ D $ 维特征 $ z $）和线性回归器 $ h_\psi(z) = w^T z + b $（或者 $ h_{\psi}(z)=Wz+b $） $ f_\theta $ 首先在一个有标签的源数据集 $ S = \{(x_i, y_i)\}_{i=1}^{N_s} $ 上进行预训练，数据从源域分布 $ p_s $ 中采样 目标是使用一个无标签的目标数据集 $ T = \{x_j\}_{j=1}^{N_t} $ 来适应预训练好的模型 $ f_\theta $ 到目标域 我们假设存在 covariate shift ，这意味着： ...
Method Problem Set EEG 数据 $ \{ X_{s,l}^{i},y_{s,l}^{i} \}_{i=1}^{n_{s,l}} $ ，进行无监督在线 K 分类 Source Model Training 对源数据做 Euclidean alignment (EA) 数据对齐，减少不同个体 EEG 信号差异 EA 计算每个个体所有 EEG 试次协方差矩阵的算术平均值 $$ R_{s,l} = \dfrac{1}{n}\sum_{i=1}^{n} X_{i}(X_{i})^{T} \implies \bar{X}_{i} = R_{s,l}^{-1/2}X_{i} $$ 之后再整合经过对齐的受试者数据，形成“源域” 在整合后的数据上独立训练 $ M $ 个模型 Incremental EA on Target Data 对新数据增量式更新协方差矩阵，再用新的矩阵更新所有测试数据 Target Label Prediction 用训练好的 $ M $ 模型初始化用于适应目标域的 $ M $ 个 TTA 模型 $ f_{m} $ 新的 $ X_{a} $ 经过 IEA 被变换为 $ X_{a}' $ 后被输入到每个模型 $ f_{m} $ 中进行分类，输出概率向量 $ f_{m}(X_{a}') $ ...
Setting Fully Test-Time Adaptation 是一种独特的模型适应设定。在此设定下，模型 $ f_\theta(x) $ 在训练阶段已通过源数据 $ x^s $ 和标签 $ y^s $ 完成训练，获得参数 $ \theta $。但在测试阶段，模型将遇到与源数据分布不同的无标签目标数据 $ x^t $。 FTT-Adaptation 与以下方法不同： Fine-tuning：需要目标标签进行重新训练。 Domain Adaptation：需要源数据和目标数据进行联合训练。 Test-Time Training (TTT)：需要修改训练过程并共同优化有监督及自监督损失。 相比之下，FTT-Adaptation 仅能利用预训练模型 $ f_\theta $ 和无标签目标数据 $ x^t $ 进行适应，不依赖源数据或额外的监督信息。 Method 论文的核心贡献是提出了 Tent 方法，其核心思想是通过最小化测试熵（Test Entropy Minimization）来适应模型预测，旨在使模型对测试数据的预测结果更“有信心”。 Entropy Objective Tent 的测试时目标函数是最小化模型预测 $ \hat{y} = f_\theta(x^t) $ 的熵 $ H(\hat{y}) $。论文中使用的香农熵计算公式如下： $$ H(\hat{y}) = - \sum_c p(\hat{y}_c) \log p(\hat{y}_c) $$ 其中， $ p(\hat{y}_c) $ 表示模型预测目标数据 $ x^t $ 属于类别 $ c $ 的概率。 ...
Setting Continual Test-Time Domain Adaptation 是一种更具挑战性的模型适应设定。在此设定下，一个在源数据上预训练好的模型，在测试时会遇到一个非平稳且持续变化的目标环境 。 CoTTA 与以下方法不同： Standard Domain Adaptation：需要同时访问源数据和（静态的）目标数据进行训练。 Standard Test-Time Adaptation / Fully Test-Time Adaptation：通常假设目标域是固定的或静态的，而 CoTTA 关注的是持续变化的目标域。 Test-Time Training (TTT)：需要修改源模型的训练过程以加入辅助任务，因此无法使用任意的“开箱即用”预训练模型。 相比之下，CoTTA 专门解决在无源数据的条件下，模型如何在线适应一个持续变化的数据流，同时克服现有方法中常见的错误累积和灾难性遗忘问题。 Method 论文的核心贡献是提出了CoTTA (Continual Test-Time Adaptation) 方法，旨在通过减少错误累积和避免灾难性遗忘，实现模型在非平稳环境下的长期稳定适应，主要有两个关键部分。 1. 减少错误累积 (Reducing Error Accumulation) 为了生成更可靠的自训练信号，CoTTA 采用了平均化的伪标签策略，该策略结合了权重平均和数据增强平均。 权重平均伪标签 (Weight-Averaged Pseudo-Labels) 该方法采用一个教师 - 学生 (teacher-student) 框架。学生模型 (student model) 在线进行学习和更新。 教师模型 (teacher model) 的权重是学生模型权重的指数移动平均 (Exponential Moving Average, EMA)。 由于教师模型的更新更平滑，其预测结果通常比学生模型更准确，因此用它来生成伪标签，可以有效减少错误累积。学生模型通过最小化与教师伪标签的一致性损失 (consistency loss) 来进行更新。 数据增强平均伪标签 (Augmentation-Averaged Pseudo-Labels) 为了进一步提升伪标签在遇到较大域偏移时的质量，CoTTA 会有条件地使用数据增强。 它首先使用原始预训练模型评估当前测试数据的预测置信度，以此来近似域差异的大小。 条件性应用： 如果置信度高（域差异小），则直接使用教师模型的预测作为伪标签。 如果置信度低（域差异大），则对输入数据进行 N 次随机增强，并将教师模型对这些增强样本的平均预测结果作为伪标签。这可以进一步提高伪标签的鲁棒性。 2. 避免灾难性遗忘 (Avoiding Catastrophic Forgetting) 为了在长期适应过程中保留从源域学到的知识，CoTTA 引入了随机恢复 (Stochastic Restoration) 机制。 ...
Introduction 类似 GAN 的对抗训练思想 Domain Adaptation 给定源域 $ D_{S} $ （有标签）和目标域 $ D_{T} $ （无标签），目标是训练一个分类器 $ \eta: X\to Y $ 使其在目标域上的目标风险 $$ R_{D_{T}}(\eta) = \underset{(\mathbf{x},y)\sim D_{T}}{\mathrm{Pr}}(\eta(\mathbf{x}) \neq y) $$ 最小 Domain Divergence 需要量化两个领域的“相似度”，从而引出了 H- 散度 的概念： $$ d_{\mathcal{H}}(D_S, D_T) = 2 \sup_{\eta \in \mathcal{H}} \left| \Pr_{x \sim D_S}[\eta(x) = 1] - \Pr_{x \sim D_T}[\eta(x) = 1] \right| $$ 含义是最优的分类器将目标域和源域判定为 1 的可能性之差，当 H- 散度非常小时，说明两个领域很难被区分，也就说明学习的特征实现了领域不变性的效果 由于理论 H 散度是理想数据分布上的定义，实际中只有有限的样本集 $ S $ 和 $ T $ ，因此需要一定的近似，于是需要经验 H- 散度 $$ \hat{d}_{\mathcal{H}}(S, T) = 2 \left(1 - \min_{\eta \in \mathcal{H}} \left[ \dfrac{1}{n}\sum_{i=1}^n \mathcal{I}[\eta(x_i) = 0] + \dfrac{1}{n'}\sum_{i=n+1}^N \mathcal{I}[\eta(x_i) = 1] \right] \right) $$ 其中 $ \mathcal{I}[\cdot] $ 表示条件为真时为 1，否则为 0 ...
A General Paradigm of Test-Time Adaptation 根据测试数据接收方式和适应过程，TTA 分为三种主要范式： Test-Time Batch Adaptation (TTBA) 测试时间批次适应： 数据以小批次形式到达。模型会针对每个到来的小批次进行适应，并立即提供预测。 Online Test-Time Adaptation (OTTA) 在线测试时间适应： 数据以序列化的方式（小批次）到达。模型进行增量更新，并且过去的适应经验会影响未来的预测。 Test-Time Domain Adaptation (TTDA) 测试时间域适应： 整个目标域的数据（所有测试数据）可在预测前一次性用于适应。 Datasets for Evaluation 论文使用了两种不同类型的分布偏移数据集进行评估： Corruption Datasets 损坏数据集： 原始数据集（CIFAR-10，ImageNet）经过人为损坏处理后得到的，通过添加不同类型的噪声、模糊等，模拟不同严重程度的分布偏移。 Natural-shift Datasets 自然偏移数据集： 这些数据集代表数据分布中自然发生的变化，收集自不同的真实世界来源或条件（Office-Home，DomainNet，其中图像可能是不同风格的艺术作品、剪贴画、真实世界照片或草图）。 Results on Natural Shift Datasets TTA 方法在自然偏移数据集上的表现与在损坏数据集上的表现有所不同。 PredBN 在损坏数据集上有效，但在自然偏移数据集上表现不佳，有时甚至比源模型更差。这可能是因为自然偏移对数据分布的影响与人工损坏不同。 T3A 在 OTTA 范式下的自然偏移数据集上表现优于其他 OTTA 算法。这归因于其特征生成方式及其分类器优化能力。 对于自然偏移数据集，TTDA 算法 持续取得了最高的性能。一些 OTTA 方法的多轮次也能达到可比的成果。
针对 CUMCM-2025 开始学习 COPT 求解器的使用，学习如何应用 COPT 的 Python API (coptpy) 来建模并求解数学建模中常见的离散优化问题。 Basic API 本节将介绍 COPT 求解器 Python API (coptpy) 的核心组件和常用方法。 Envr Class Envr 类用于创建一个 COPT 环境。它是所有模型操作的起点。 Creating Environment and Model: 1 2 3 4 5 import coptpy as cp from coptpy import COPT env = cp.Envr() # 创建一个 COPT 环境实例 model = env.createModel(name='YourModelName') # 在环境中创建一个模型 name：模型的名称，此为可选参数。 Model Class Properties and Methods Model 类是 COPT 的核心，代表了优化模型，包含了所有变量、约束和目标函数。 Basic Properties 在模型求解后，可以通过以下属性获取其基本信息： model.status：模型解的状态。此属性指示模型是否找到了最优解、无可行解等。例如，COPT.OPTIMAL 表示已找到最优解。 model.objval：目标函数值。此属性存储模型的最优目标函数值。 Adding Variables 可以通过 addVar() 和 addVars() 方法向模型中添加决策变量。 Adding a Single Variable: ...