ARST打卡第282周

Linmin.Shan included in ARST

2024-09-28 3241 words 7 minutes

Contents

lc2286_以组为单位订音乐会的门票(线段树,前缀和) TED演讲什么是健康的经济？ TiKV PD调度策略最佳实践浅谈 leveldb 和 rocksdb 选择问题

Algorithm

lc2286_以组为单位订音乐会的门票

个人暴力前缀和TLE

思路:

其实整个过程是个贪心的过程，不过需要维护每一排的当前下标情况。

所以 new 的时候就是初始化一个 cnt[n] 记录 n 排到了什么位置了，每次和 m 长度对比。

gather 就是遍历 cnt 数组到 maxRow , 看看有没有到 m 的总长度，返回空或者能坐下的位置 [i, cnt[i]]。

scatter 就是遍历 cnt 数组到 maxRow , 贪心选择能遍历到的所有位置即可返回 true。

实现过程中，cursor竟然能提示我使用前缀和，挺好。不过主要还得自己想清楚。

遍历更新前缀和O(n^2)的方式会TLE, 但是至少能通过。

前缀和如果不遍历，不好优化，因为如果每次gather如国只更新自己当行的prefix_sum[i]，那么多次gather后再突然scatter，并无法使用简单get_sum知道哪一行更新了多少这些信息（信息丢失了），所以最终只能使用题解的线段树 O(nlogn)。

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


struct BookMyShow {
    n: i32,
    m: i64,
    row_seats: Vec<i64>,
    prefix_sum: Vec<i64>,
}

impl BookMyShow {
    fn new(n: i32, m: i32) -> Self {
        let m = m as i64;
        Self {
            n,
            m,
            row_seats: vec![0; n as usize],
            prefix_sum: vec![0; n as usize + 1],
        }
    }
    
    fn gather(&mut self, k: i32, max_row: i32) -> Vec<i32> {
        let k = k as i64;
        for i in 0..=max_row as usize {
            if self.m - self.row_seats[i] >= k {
                let seat = self.row_seats[i];
                self.row_seats[i] += k;
                // 更新前缀和
                for j in i+1..=self.n as usize {
                    self.prefix_sum[j] += k;
                }
                return vec![i as i32, seat as i32];
            }
        }
        vec![]
    }
    
    fn scatter(&mut self, k: i32, max_row: i32) -> bool {
        let k = k as i64;
        let available = (max_row as i64 + 1) * self.m - self.prefix_sum[max_row as usize + 1];
        if available < k {
            return false;
        }
        
        let mut remaining = k;
        for i in 0..=max_row as usize {
            let available_in_row = self.m - self.row_seats[i];
            if available_in_row >= remaining {
                self.row_seats[i] += remaining;
                // 更新前缀和
                for j in i+1..=self.n as usize {
                    self.prefix_sum[j] += remaining;
                }
                return true;
            }
            remaining -= available_in_row;
            // 更新前缀和
            for j in i+1..=self.n as usize {
                self.prefix_sum[j] += available_in_row;
            }
            self.row_seats[i] = self.m;
        }
        true
    }
}

// 调试过程
fn main() {
    // 初始化 BookMyShow
    // [[2,5],[4,0],[2,0],[5,1],[5,1]]
    let mut bms = BookMyShow::new(2, 5);
    println!("{:?}", bms.gather(4, 0)); // [0, 0]
    println!("{:?}", bms.gather(2, 0)); // []
    println!("{}", bms.scatter(5, 1)); // true
    println!("{}", bms.scatter(5, 1)); // false
}

题解的线段树解法

题解用线段树快速维护多排区间的最小占用值和区间使用和，于是非常方便。空间换时间。

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99


struct BookMyShow {
    n: i32,
    m: i32,
    min_tree: Vec<i32>,
    sum_tree: Vec<i64>,
}

impl BookMyShow {
    fn new(n: i32, m: i32) -> Self {
        BookMyShow {
            n,
            m,
            // 线段树通常使用4n的空间来确保有足够的节点存储所有可能的区间
            // 这是因为在最坏情况下，一个完全二叉树的节点数量可能接近4n
            // 1. 叶子节点数量为n
            // 2. 内部节点数量最多为n-1
            // 3. 为了保证树的完整性和便于索引，通常会将数组大小扩展到最接近的2的幂次方
            // 4. 再加上一些额外的空间以防万一，最终选择4n作为一个安全的上界
            min_tree: vec![0; 4 * n as usize],
            sum_tree: vec![0; 4 * n as usize],
        }
    }
    
    fn modify(&mut self, i: usize, l: i32, r: i32, index: i32, val: i32) {
        if l == r {
            self.min_tree[i] = val;
            self.sum_tree[i] = val as i64;
            return;
        }
        let mid = (l + r) / 2;
        if index <= mid {
            self.modify(i * 2, l, mid, index, val);
        } else {
            self.modify(i * 2 + 1, mid + 1, r, index, val);
        }
        self.min_tree[i] = self.min_tree[i * 2].min(self.min_tree[i * 2 + 1]);
        self.sum_tree[i] = self.sum_tree[i * 2] + self.sum_tree[i * 2 + 1];
    }

    fn query_min_row(&self, i: usize, l: i32, r: i32, val: i32) -> i32 {
        if l == r {
            if (self.min_tree[i] > val) {
                return self.n;
            }
            return l;
        }
        let mid = (l + r) / 2;
        if self.min_tree[i * 2] <= val {
            self.query_min_row(i * 2, l, mid, val)
        } else {
            self.query_min_row(i * 2 + 1, mid + 1, r, val)
        }
    }

    fn query_sum(&self, i: usize, l: i32, r: i32, l2: i32, r2: i32) -> i64 {
        if l2 <= l && r <= r2 {
            return self.sum_tree[i];
        }
        let mid = (l + r) / 2;
        let mut sum = 0;
        if mid >= l2 {
            sum += self.query_sum(i * 2, l, mid, l2, r2);
        }
        if mid + 1 <= r2 {
            sum += self.query_sum(i * 2 + 1, mid + 1, r, l2, r2);
        }
        sum
    }

    fn gather(&mut self, k: i32, max_row: i32) -> Vec<i32> {
        let i = self.query_min_row(1, 0, self.n - 1, self.m - k);
        if (i > max_row) {
            return Vec::new();
        }
        let used = self.query_sum(1, 0, self.n - 1, i as i32, i as i32);
        self.modify(1, 0, self.n - 1, i as i32, used as i32 + k);
        vec![i as i32, used as i32]
    }

    fn scatter(&mut self, k2: i32, max_row: i32) -> bool {
        let mut k: i32 = k2;
        let used_total = self.query_sum(1, 0, self.n - 1, 0, max_row);
        if ((max_row as i64) + 1) * (self.m as i64) - used_total < (k as i64) {
            return false;
        }
        let mut i = self.query_min_row(1, 0, self.n - 1, self.m - 1) as i32;
        loop {
            let used = self.query_sum(1, 0, self.n - 1, i, i) as i32;
            if self.m - (used as i32) >= k {
                self.modify(1, 0, self.n - 1, i, used + k);
                break;
            }
            k -= self.m - used;
            self.modify(1, 0, self.n - 1, i, self.m);
            i += 1;
        }
        true
    }
}

Review

TED演讲什么是健康的经济？

演讲概要

1. 甜甜圈经济模型

凯特·拉沃思提出了“甜甜圈经济”模型，旨在构建一个既满足人类基本需求又不超越地球生态界限的经济体系。这个模型由两个同心圆组成：

内圈（社会基础）：代表确保每个人都能获得基本生活所需，如食物、住房、教育、医疗等。任何经济活动都不应低于这一标准，否则将导致社会不公和人类福祉的下降。
外圈（生态界限）：代表地球的生态承载力，如气候变化、生物多样性、气体排放等。经济活动不应超过这些界限，否则将导致环境的不可逆转破坏。

2. 繁荣而非单纯增长

传统经济模式过于关注GDP的增长，忽视了社会公平和环境可持续性。甜甜圈经济模型强调在满足社会需求的同时，保护和尊重自然生态，从而实现真正的繁荣。

3. 可持续与分配式经济

凯特强调，经济发展应在可持续的基础上进行，确保资源的合理分配和利用。她呼吁各国制定政策时，考虑社会和环境的双重需求，避免因追求经济增长而牺牲其他重要价值。

4. 应用与实施

她讨论了如何将甜甜圈经济模型应用于实际，包括政策制定、城市规划和企业战略。通过具体案例，展示了这一模型在不同领域中的实践效果，推动各界共同致力于构建更加公平和可持续的经济体系。

总结

凯特·拉沃思的甜甜圈经济模型为我们提供了一个全新的视角，重新定义了经济发展的目标和路径。通过在社会需求和生态限度之间找到平衡点，甜甜圈经济不仅关注经济的繁荣，更注重社会的公平和环境的可持续，为实现更美好的未来指明了方向。

Tip

TiKV PD调度策略最佳实践

浅谈 leveldb 和 rocksdb 选择问题

之前用 leveldb，rocksdb 源码内 bench 工具测试，得到 rocksdb 在写，Compact 上性能都比 leveldb 好，读取比 leveldb 慢。

最近封装进 App 压力测试（512B 到 64KB）之后，发现在大量前台压力下，rocksdb 绝大多数场景读写性能都比 leveldb 差。

在压力均摊的场景下，才能体现出 rocksdb 的读写性能优势。写性能性能比 leveldb 好 2%-8%左右，读性能差不多（略优一点）。

但是压力均摊时，leveldb 也不会太差。:)

因此，如果前台压力极大，不一定 rocksdb 是一个好的选择。

NOTICE: 前面测试都是相同的配置，没有给 RocksDB 开太多的线程，因此rocksdb可能还有一些调优空间。

所以（仅供参考）:

如果业务场景属于前台压力较大，希望存储占用量小，对事务没有特殊要求，可以考虑使用 leveldb。
而对事务有要求，或者对很多参数有自定义的入参，或者有更多扩展功能要求，或者前台写入压力没那么大的时候则可以考虑使用 rocksdb。

更进一步，也可以考虑其他存储引擎。

可以看到 TiKV 已经对 RocksDB 有了很多的优化。甚至已经默认使用了 Titan 作为存储引擎（用更大的空间放大来降低写放大，独立存储提升大 Value 性能）。

从 v7.6.0 开始，TiDB 对 Titan 性能进行了优化，并将 Titan 作为默认的存储引擎。由于 TiKV 在 Value 较小时会直接存在 RocksDB 中，因此即便是小 Value 也可以打开 Titan。

参考

这个我当初看过一点，可以做个无责任推测：

比特币开始做的时候，LevelDB 已经是个成熟的产品（毕竟在开源之前 LevelDB 就应该在 Jeff Dean 的手里已经跑了几年），而 RocksDB 还在开发初期，不一定那么成熟

以太坊仅限于 geth 是 LevelDB，parity 记得还是 RocksDB。这里其实有个很无聊的原因：geth 是 Go 写的，而 Go 受限于 cgo 性能的原因，在这种底层库上通常都只能用 Go 写的来避免 latency。而 Go 写的话，只有这个仿 LevelDB 的库： https://github.com/syndtr/goleveldb

所以如果我的推测是正确的话，已有的 LevelDB 更多的是处于无奈和 legacy 的选择。

我觉得你说的有道理。

那本质上 RocksDB 比 LevelDB 好在哪呢？从 benchmark 上看感觉没有明显优势？

RocksDB 本身有个很明显的优势，就是传统的 LevelDB 只是单线程处理，这样有大 value 的 key 的时候，性能会有明显衰减。但是 RocksDB 添加了多线程支持，在很多场景下性能会有明显提升。

但是要注意的另一个问题是 LevelDB/RocksDB 这一系下层都是用的 Log Structured Merge Trees 这个数据结构，这个数据结构其实最开始是为解决传统的机械硬盘随机写速度很慢的场景实现的。在 SSD 时代，首先随机写不是问题，其次 LSM 在某些场景下会撞到 SSD 的一些特性，反而造成写放大导致性能损失。这个损失在 LevelDB 场景下通常还好，在某些 RocksDB 的使用模式下速度会体现出来慢很多。

当然不是说写放大的问题没有解决方案，只是说要具体做 benchmark 才能确定每个场景适合的选型。