lc494_目标和 2024黄仁勋加州理工毕业演讲 使用 Go 打造百亿级文件系统的实践之旅 Rocksdb快照,checkpoint,备份区分
Algorithm
lc494_目标和
思路:
先考虑暴力解法，枚举所有的正负数排列，因为长度是最大20，所以是 2^20, 1e6, 可以暴力枚举。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sz = nums.size();
int tmp = 0;
int ans = 0;
for (int i = 0; i < (1 << sz); i++) {
// 当前排列下的临时数值
tmp = 0;
for (int j = 0; j < sz; j++) {
// bit位为0是负数，为1是正数
tmp += i & (1 << j) ? nums[j] : -nums[j];
}
if (tmp == target) {
ans++;
}
}
return ans;
}
};
|
以上还是有 2e7 的复杂度，提交 TLE 了:
64 / 140 个通过的测试用例
没想出来，看了一下题解，发现题解的递归回溯竟然可以过？？?
就因为每轮数值在递归中操作的？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int count = 0;
int findTargetSumWays(vector<int>& nums, int target) {
backtrack(nums, target, 0, 0);
return count;
}
void backtrack(vector<int>& nums, int target, int index, int sum) {
if (index == nums.size()) {
if (sum == target) {
count++;
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]);
backtrack(nums, target, index + 1, sum - nums[index]);
}
}
};
// 链接：https://leetcode.cn/problems/target-sum/solutions/816361/mu-biao-he-by-leetcode-solution-o0cp/
|
确实差距就是 O(2^n * n) 的 O(n), 在这种情况下还是用递归回溯。
更高效的解法是 dp 的方式:
巧妙把正负数转换成凑一个数的dp方式，比较难想到，学习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int& num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int neg = diff / 2;
vector<int> dp(neg + 1);
dp[0] = 1;
for (int& num : nums) {
for (int j = neg; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[neg];
}
};
// 链接：https://leetcode.cn/problems/target-sum/solutions/816361/mu-biao-he-by-leetcode-solution-o0cp/
|
Review
黄仁勋加州理工演讲
没开中文字幕，也能听懂看懂，舒服。
老黄祝贺大家毕业，还讲到要祝贺那些帮助你们走到这个里程碑的家人和支持者们。视角很客观，并没有完全那种个人英雄主义。
当然老黄也是去加州理工招聘优秀大学生，哈哈，毫不避讳得说，挺好。
做优先级最高的事情，用一辈子去做，这样就有充足的时间做。–长期主义。
I hope you find a craft. 找到自己的命门，然后奉献一生做高优的事情，这样就有大把的时间做到极致。
Tips
极限挑战：使用 Go 打造百亿级文件系统的实践之旅
企业版不是用的tikv，而是自研元数据引擎，学习其中的思路，这里的知识就是金钱。
JuiceFS 企业版追求极致性能，因此采用的是第一种全内存方案，并通过不断的优化来减小文件元数据的内存占用。全内存模式通常会使用实时落盘的事务日志来保证数据的可靠性，JuiceFS 还使用了 Raft 共识算法来实现元数据的多机复制和自动故障切换。
这里感觉它的单线程无锁，其实和 raft 日志做任务分发差不多..
JuiceFS 采用了一种不同的方法，即类似于 Redis 的无锁模式。在这种模式下，所有核心数据结构的相关操作都在单个线程中执行。这种单线程方法不仅保证了每个操作的原子性（避免了操作被其他线程打断的问题），还减少了线程间的上下文切换和资源竞争，从而提高了系统的整体效率。同时，它大大降低了系统复杂度，提升了稳定性和可维护性。得益于全内存的元数据存储模式，请求都可以被非常高效地处理，CPU 不容易成为瓶颈。
因为维护了许多内存，所以自我用指针管理GC，防止Golang自带的GC的中断时间过长:
可见这些结构体都非常小，但是数量会非常庞大。Go 的 GC 不支持分代，也就是说如果将它们都交由 GC 来管理，就需要在每次进行内存回收时都将它们扫描一遍，并且标记所有被引用的对象。这个过程会非常慢，不仅使得内存无法及时回收，还可能消耗过多的 CPU 资源。
其中把申请的内存指针放在了一个大的kv的map里面，这样利用gc扫描的时候不管这个map多大都不会深入扫描map内部存储的特性，极大减小golang GC的压力。
最终再通过压缩空闲数据，以及优化数据结构的方式，大大提高了元数据的内存利用率。
Share
Rocksdb快照,checkpoint,备份区分
- Snapshot: 只快照一个版本。比如在一次 Compaction 中，先快照一个版本，然后操作完就没了。A snapshot cannot outlive the DB session that created it.
- Checkpoint: 同文件系统同磁盘，会用硬链接复制。可以用于数据库分片。
- Backup: 类似于深拷贝，主要用于一次拷贝，多次复制。一般用于云备份多处分发。
参考: [Help ] What is the difference between backup and checkpoint ? which one will be recommended if I want to do backup restore operation