ARST打卡第272周

Linmin.Shan included in ARST

2024-07-21 913 words 2 minutes

Contents

lc1186_删除一次得到子数组最大和 RocksDB in TiKV Rocksdb 写流程,读流程,WAL文件,MANIFEST文件,ColumnFamily,Memtable,SST文件原理详解元数据存储加速Rocksdb配置项实践

Algorithm

lc1186_删除一次得到子数组最大和

思路:

这样需要实现 k-range 的 hash 函数。

感觉不用这么复杂，直接遍历，前后两段非负连续数组维护最大值即可。

有个特例就是全是负数的话要返回最大单个值。

 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


class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int sz = arr.size();
        if (sz == 1) {
            return arr[0];
        }
        int pre_sum = -1;
        int pre_end = -1;
        int cur_sum = -1;
        int cur_begin = -1;
        int cur_end = -1;
        int max_neg = -1e4-10;
        int ans = -1;
        for (int i = 0; i < sz; i++) {
            if (arr[i] >= 0) {
                if (cur_sum == -1) {
                    cur_sum = arr[i];
                    cur_begin = i;
                    // 单个正值也要这个
                    cur_end = i;
                    continue;
                }
                cur_sum += arr[i];
                cur_end = i;
            } else {
                // 这里用 cur_sum 为 -1 防止维护 ans 值，并顺便得到 max_neg.
                if (cur_sum == -1) {
                    max_neg = max(max_neg, arr[i]);
                    continue;
                }
                // 维护答案
                if (pre_sum == -1) {
                    ans = cur_sum;
                } else {
                    // 前面已经确定 pre_end != -1 
                    if (cur_begin - pre_end == 2) {
                        ans = max(ans, pre_sum + cur_sum);
                    } else {
                        ans = max(ans, cur_sum);
                    }
                }
                // 回归 cur_sum 状态
                pre_sum = cur_sum;
                pre_end = cur_end;
                cur_sum = -1;
            }
        }
        // 最后可能还要维护一次答案
        if (arr[sz - 1] >=0 ) {
            // 维护答案
            if (pre_sum == -1) {
                ans = cur_sum;
            } else {
                // 前面已经确定 pre_end != -1 
                if (cur_begin - pre_end == 2) {
                    ans = max(ans, pre_sum + cur_sum);
                } else {
                    ans = max(ans, cur_sum);
                }
            }
        }
        if (ans != -1) {
            return ans;
        }
        return max_neg;
    }
};

解答错误 20 / 36 个通过的测试用例

输入 arr = [8,-1,6,-7,-4,5,-4,7,-6]

输出 14

预期结果 17

看到这个案例，才发现自己完全想错了，还有正数负数组合的数组也能贡献正数值，所以这样算法就失效了。

看看题解怎么做.

题解是动态规划所有删除与不删的情况，精妙，学习。

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


class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int dp0 = arr[0], dp1 = 0, res = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            dp1 = max(dp0, dp1 + arr[i]);
            dp0 = max(dp0, 0) + arr[i];
            res = max(res, max(dp0, dp1));
        }
        return res;
    }
};

Review

RocksDB in TiKV

Tips

Rocksdb 写流程,读流程,WAL文件,MANIFEST文件,ColumnFamily,Memtable,SST文件原理详解

元数据存储加速Rocksdb配置项实践

设置 options.max_manifest_file_size 控制 manifest 大小，让达到大小后生成新的 manifest

看 Tikv dev最新配置也是设置的 128M, 而且在上述tips中理解了含义之后，觉得完全可以设置 128M。

max_file_opening_threads 默认是16线程，可以开到32线程。
options.skip_checking_sst_file_sizes_on_db_open = true 完全可以设置为 true，只检查需要的文件的 size 。

经过实践测试之后确实有加速效果。

参考: Speed Up DB Open

Contents

ARST打卡第272周

Algorithm

Review

Tips

Share