ARST打卡第266周

2024-06-09 1878 words 4 minutes

Contents

lc3040_相同分数的最大操作数目II USENIX ATC ‘23 - RubbleDB：CPU-Efficient Replication with NVMe-oF 链抽象/互操作性/全链 raft_apply慢导致业务不可用的情况分析

Algorithm

lc3040_相同分数的最大操作数目II

思路:

这里把删除看成左右双指针移动。

然后最开始有3种操作选择导致有3种值，选择了值之后，后面的操作都根据值来选定记忆回溯即可。

 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


// // Define a custom hash function for pair<int, int>
// struct pair_hash {
//     template <class T1, class T2>
//     std::size_t operator() (const std::pair<T1, T2> &pair) const {
//         return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
//     }
// };

const int N = 2e3 + 2;
class Solution {
    // unordered_map<pair<int, int>, int, pair_hash> cache;
    int memo[N][N];
public:
    int dfs(vector<int>& nums, int l, int r, int sum) {
        // if (cache.find({l,r}) != cache.end()) {
        //     return cache[{l,r}];
        // }
        if (memo[l][r] != -1) {
            return memo[l][r];
        }

        // size 不够的终止
        if (r - l + 1 < 2) {
            // cache[{l,r}] = 0;
            memo[l][r] = 0;
            return 0;
        }
        // size 只有一种可能
        if (r - l + 1 == 2) {
            // 先设置为0，如果匹配则1.
            // cache[{l,r}] = 0;
            // if (nums[l] + nums[r] == sum) {
            //     cache[{l,r}] = 1;
            // }
            // return cache[{l,r}];
            memo[l][r] = 0;
            if (nums[l] + nums[r] == sum) {
                memo[l][r] = 1;
            }
            return memo[l][r];
        }
        // // 都不可能的终止
        // if (nums[l] + nums[l + 1] != sum &&
        //     nums[r - 1] + nums[r] != sum &&
        //     nums[l] + nums[r] != sum) {
        //     cache[{l,r}] = 0;
        //     return cache[{l,r}];                
        // }

        int ans = 0;
        // 每一种可能都需要探索，不能 if `else if`.
        if (nums[l] + nums[l + 1] == sum) {
            ans = max(ans, 1 + dfs(nums, l + 2, r, sum));
        } 
        if (nums[r - 1] + nums[r] == sum) {
            ans = max(ans, 1 + dfs(nums, l, r - 2, sum));
        }
        if (nums[l] + nums[r] == sum) {
            ans = max(ans, 1 + dfs(nums, l + 1, r - 1, sum));
        }
        // cache[{l,r}] = ans;
        memo[l][r] = ans;
        return ans;
    }
    int maxOperations(vector<int>& nums) {
        int sz = nums.size();
        int ans = 1;
        if (sz <= 3) {
            return ans;
        }
        // cache.clear();
        memset(memo, -1, sizeof(memo));
        int x = nums[0] + nums[1];
        ans += dfs(nums, 2, sz - 1, x);

        // cache.clear();
        memset(memo, -1, sizeof(memo));
        x = nums[sz - 2] + nums[sz - 1];
        ans = max(ans, 1 + dfs(nums, 0, sz - 3, x));

        // cache.clear();
        memset(memo, -1, sizeof(memo));
        x = nums[0] + nums[sz - 1];
        ans = max(ans, 1 + dfs(nums, 1, sz - 2, x));
        
        return ans;
    }
};

其中一开始报错:

Line 2: Char 40: note: default constructor of ‘Solution’ is implicitly deleted because field ‘cache’ has a deleted default constructor 2 | unordered_map<pair<int, int>, int> cache;

问GPT4o:

The error you’re encountering arises because the default constructor of unordered_map cannot handle the pair<int, int> type directly as a key without a custom hash function. This issue can be resolved by defining a custom hash function for the pair<int, int>.

Here’s how you can resolve this:

Define a custom hash function for pair<int, int>.

Specify this custom hash function in the unordered_map.

Here’s an example of how you can do it:
 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
#include <iostream>
#include <unordered_map>
#include <utility>  // For std::pair
#include <functional>  // For std::hash

// Define a custom hash function for pair<int, int>
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

class Solution {
public:
    std::unordered_map<std::pair<int, int>, int, pair_hash> cache;

    Solution() = default;

    // Other member functions...
};

int main() {
    Solution sol;
    // Example usage
    sol.cache[std::make_pair(1, 2)] = 42;
    std::cout << sol.cache[std::make_pair(1, 2)] << std::endl;
    return 0;
}
In this example, pair_hash is defined to hash a std::pair<int, int>. This hash function is then used in the unordered_map declaration in the Solution class. This way, the unordered_map can properly handle pair<int, int> keys, and the default constructor of Solution will work correctly.

Explanation:

pair_hash: A custom hash function struct that uses the std::hash functions for the elements of the pair and combines them with XOR.

cache: Declared as an unordered_map with std::pair<int, int> as the key type and int as the value type, using pair_hash for hashing.

Solution() = default: Explicitly defaulted constructor for Solution class.

By applying this custom hash function, you enable the unordered_map to handle std::pair<int, int> keys properly, resolving the compilation error.

后面 TLE 了… 全是 1000.. 确实没有考虑到这种 corner case.

超出时间限制 : 520 / 549 个通过的测试用例

最后执行的输入: nums = [1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,

感觉这个 cornor case 在提醒我，是不是可以服用一下缓存？

先试一下不严谨的假设所有的 l,r 的 key 都是相同的 sum.

不行，还是 TLE 在这里，所以不用尝试 l,r,sum 的 key 的 cache 了。

看了答案，发现差不了太多，所以再剪枝试试。

吐血，因为用容器导致卡 TLE 了，然后用数组就能过…基本和题解一样，但还是学习一下题解写法

 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


class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        int memo[n][n];

        auto helper = [&](int i, int j, int target) -> int {
            memset(memo, -1, sizeof(memo));
            function<int(int, int)> dfs = [&](int i, int j) -> int {
                if (i >= j) {
                    return 0;
                }
                if (memo[i][j] != -1) {
                    return memo[i][j];
                }
                int ans = 0;
                if (nums[i] + nums[i + 1] == target) {
                    ans = max(ans, 1 + dfs(i + 2, j));
                }
                if (nums[j - 1] + nums[j] == target) {
                    ans = max(ans, 1 + dfs(i, j - 2));
                }
                if (nums[i] + nums[j] == target) {
                    ans = max(ans, 1 + dfs(i + 1, j - 1));
                }
                memo[i][j] = ans;
                return ans;
            };
            return dfs(i, j);
        };

        int res = 0;
        res = max(res, helper(0, n - 1, nums[0] + nums[n - 1]));
        res = max(res, helper(0, n - 1, nums[0] + nums[1]));
        res = max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));
        return res;
    }
};

Review

USENIX ATC ‘23 - RubbleDB：CPU-Efficient Replication with NVMe-oF

通过 Nvme-oF 远程复制其他副本的 rocksdb 的 compaction 完成的 SST 来节约 CPU 和 CPU-IO.

也就是通过更复杂的管理程序+网络IO来换取 CPU 和 CPU-IO.

在 CPU 限制的复制集群是有效的。

但是在 IO 限制的集群，可能效果不是那么明显。

而且个人认为对于 Raft + Rocksdb 3副本的场景。这种虽然有点像 Install Snapshot，但是又好像需要和 Rocksdb 内部状态进行耦合，导致了更复杂的管理问题。并且让三副本的独立性变得关联起来了，对网络故障的抗风险能力估计又得重新评估了。

因此个人决定性能提升不是很大，以及CPU不是瓶颈的话，还是不建议采用这种方案。但是这种方案的探索，用网络IO换取CPU和CPU-IO的行为和思路还是值得肯定和学习的。

Tips

链抽象/互操作性/全链

其实本质还是统一平台。

raft apply慢导致业务不可用的情况分析

如果 raft 中 leader 因为一些因素导致程序运行很慢，可能 apply 比 follower 慢（follower，leader 一起异步 apply ），导致业务写超时。

但是这种情况又不会产生 leader 转换，因此需要及时排查其他卡慢因素(cpu被其他程序占用等)，防止因 leader apply 慢而出现的业务不可用的现象。

Contents

ARST打卡第266周

Algorithm

Review

Tips

Share