第五章 优化程序性能(摘要与注解)

我错了,我明天一定把这一篇补完

我对了,我今天把这一篇补完了

感觉是本书最难理解和应用的一章, 所以得多花点功夫尽可能深入理解了然后写的好一点

影响优化的细节

第六章 存储器层次结构(摘要与注解)

这一章也很好理解, 重点解释一些不太好理解或者书上介绍不是很清楚的地方, 然后列大纲用于以后复习看。

存储器分类

当前存储技术主要可以做以下分类:

1. RAM 随机访问储存器, 断电后数据会消失
   1. SRAM, 静态随机范围储存器, 例如 CPU 的 L1/L2/L3 缓存, 每个单元是六晶体管电路
   2. DRAM, 动态随机范围存储器, 每个单元是一晶体管电路。我们常用的主存一般是双倍数据速率同步的 DRAM (Double Data-Rate DRAM), 这是 DDR 内存的实际传输情况一般要频率乘 2 (有的会用 MT/s 作单位, 除以 2 就是频率)
2. ROM, 名字不重要, 一般可以读也可以写, 非易失性的
   1. PROM, 可编程 ROM, 只能被编程一次
   2. EPROM, 可擦写可编程 ROM
   3. EEPROM, 电子可擦写可编程 ROM, 一般每个单元会在编程 \(10^5\) 次后失效
   4. 闪存, 基于 EEPROM, 我们用的固态硬盘中的颗粒就是这个
3. 旋转磁盘

链接(第七章 ALL)

这章内容很短, 就是书中和 15213 都有意隐去了很多细节, 自己去理解思考这些细节会很麻烦

另外 section 的翻译易引起歧义, 这里不作翻译

静态链接:

静态链接包括两个阶段, 符号解析和重定位:

在做 Codeforces Educational Round 169 D Colored Portals 时，需要找到 i 前面距离 i 最近的颜色不完全相同但也不完全不同的 j，我随手写了个

1
2
3
4
5
6
7
8
9
10
11
12
13

const vector<string> type = {"BG", "BR", "BY", "GR", "GY", "RY"};
map<string, int> m;
vector<int> lc(n, -1), rc(n, -1);

for (int i = 0; i < n; i++) {
    auto condi = m | filter([&](const auto &p) { return p.first != in[i] && has_same(p.first, in[i]); });
    if (auto lci = ranges::max_element(
                condi, [](const auto &a, const auto &b) { return a.second < b.second; });
            lci != ranges::end(condi)) {
            lc[i] = lci->second;
    }
    m[in[i]] = i;
}

然后吐槽了下 C++ 没有 .iter().filter() 或者 .iter().map() 这种写法

于是我就建了个 D.rs 写了个 Rust 版本的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::HashMap;

fn has_same(a: &[char; 2], b: &[char; 2]) -> bool {
    (a[0] == b[0] || a[0] == b[1]) || (a[1] == b[0] || a[1] == b[1])
}
fn main() {

    let n : usize = 4;
    let inv : Vec<[char; 2]> = vec![['B', 'R'], ['B', 'R'], ['G', 'Y'], ['G', 'R']]; // simple

    let mut map : HashMap<[char; 2], i32> = HashMap::new();
    let mut lc = vec![-1; n];

    for i in 0usize..n {
        if let Some(lci) = map.iter()
            .filter(|(key, _)| *key != &inv[i] && has_same(key, &inv[i]))
            .max_by(|a, b| a.1.cmp(&b.1)) {
            lc[i] = *lci.1;
        }
        map.insert(inv[i].clone(), i as i32);
    }

    println!("{:?}", lc);
}

整数的运算(第二章 Part2)

无符号数加法溢出

无符号的数的加法溢出规则很简单, 单纯截取后 \(w\) 位, 或称对 \(2^w\) 取模。因此:

\[ x\ +_w^u\ y = \begin{cases} x + y, & x + y < 2^w, \\ x + y - 2^w, & 2^w \leq x + y < 2^{w+1}. \end{cases} \]

(\(+_w^u\) 表示最多 \(w\) 位下的二进制无符号数加法。下文\(+_w^t\) 即 \(w\) 位补码加法)

整数的表示(第二章 Part1)

博客还没装 Mathjax 插件，所以下面的 \(\LaTeX\) 应该都是乱的 已修

整数表示

这一段如果没有目的和顺序地硬看会觉得关系很多很复杂，但其实只要按照一定的目的和顺序结构就会很清晰。

以设计者的视角思考如何设计