ARST打卡第215周[215/521]

发表于 2023-06-16 分类于 ARST 阅读次数：

lc1494_并行课程II 【TED演讲】你不完美，你注定要奋斗，但你值得爱和归属 Rocksdb dynamic-level-bytes测试简单记录 wsl2中docker内部网络的ip转发

Algorithm

lc1494_并行课程II

思路: 像有依赖的背包贪心，感觉要模拟这个有向无环图__但是不知道咋写–看题解学习一下

震惊发现windows chrome未登录状态下还有两个英文版的tips，而mac chrome就没有tips

看了题解，发现子集和前置条件的逻辑还是挺烧脑子的，尽量结合示例来看

class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
        vector<int> dp(1 << n, INT_MAX);
        vector<int> need(1 << n, 0);
        for (auto& edge : relations) {
            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1);
        }
        dp[0] = 0;
        for (int i = 1; i < (1 << n); ++i) {
            need[i] = need[i & (i - 1)] | need[i & (-i)];
            if ((need[i] | i) != i) { // i 中有任意一门课程的前置课程没有完成学习
                continue;
            }
            // 下面已经是把前置课程都完成了，所以可以减去前置课程
            int valid = i ^ need[i]; // 当前学期可以进行学习的课程集合
            if (__builtin_popcount(valid) <= k) { // 如果个数小于 k，则可以全部学习，不再枚举子集
                dp[i] = min(dp[i], dp[i ^ valid] + 1);
            } else { // 否则枚举当前学期需要进行学习的课程集合
                for (int sub = valid; sub; sub = (sub - 1) & valid) {
                    if (__builtin_popcount(sub) <= k) {
                        dp[i] = min(dp[i], dp[i ^ sub] + 1);
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};
// 链接：https://leetcode.cn/problems/parallel-courses-ii/solutions/2306009/bing-xing-ke-cheng-ii-by-leetcode-soluti-l0mo/

答案太精妙了，建议可以反复学习，锻炼脑子

Review

【TED演讲】你不完美，你注定要奋斗，但你值得爱和归属

这篇文章真的超级适合当听力练习，我居然能不看字幕听懂大部分

无论你怎么追求完美，到最终，你都会发现有些事情你无法搞定。

当你预期太高，而有时候没有达成自己的预期的时候，你就会感到巨大的脆弱感。

因此，唯一能做的就是:
接纳脆弱，接纳自己的不完美，注定要继续努力奋斗，但是我们已经尽力而为了，去爱他人去自我实现了，所以不后悔，所以我们值得爱和归属

Tips

Rocksdb dynamic-level-bytes测试简单记录

这篇文章的测试数据很好的说明了展现了 dynamic-level-bytes 能有效降低写放大

不过其中说到数据要到最后一层才能被清理也不太理解–并不是，具体看下文

不过通过读文章知道删除更快是因为有叠加bottom compaction辅助删除
里面说是第五层数据减少，而不是第六层，是因为数据compaction到第6层，然后在第6层删除，所以第6层有增有减，大体不变，而第五层就compaction下去了，就减少较为明显

LSM架构下所有更新都是以追加一条新记录写入内存表中，delete记录也是写一条新的记录，只不过是type标记为delete。而具体delete的这条记录何时被彻底删除取决于它对应的value记录所在的位置(memtable/L0/L1..)以及flush/compaction的时间，flush将内存中的数据刷到磁盘中并且过程中会做多版本行的处理包含delete与其相应记录的消除(对应记录在memtable的情况)，记录如果被snapshot引用则不能消除，需要等compaction。如果value记录在0/1/2..层，也就是磁盘上了，需要等待compaction，compaction会将未被snapshot引用的多版本行也包括delete记录消除，新写的sst中将不包含这条delete及相应的value记录，旧的sst文件在没有引用之后由回收线程进行释放。

上面引自: Rocksdb删除一个key会经历哪些流程？

指南

wsl 默认为内部网络，外部无法访问，通过配置 nat 转发可以直接访问 docker 的内部网络，无需其他复杂的配置。

首先需要知道 wsl2 的内部 ip 地址和 docker 内部的网络地址。例如我的网络是这样的系统 Ubuntu

wsl2 的 ip 地址

inet 192.168.119.0/20 brd 192.168.127.255 scope global eth0

docker 内部的 ip 地址

inet 172.17.0.1/16 brd 172.17.255.255 scope global docker0

进入 Ubuntu

#允许路由转发
sudo iptables -P FORWARD ACCEPT

以管理员身份运行 cmd

#启用路由转发服务任务管理器 -> 服务 -> 打开服务 -> Routing and Remote Access 或者执行下面的命令
sc start RemoteAccess
#添加路由表
#注意，这里 172.17.0.1 不行，必须的172.17.0.0
route add -P 172.17.0.0 mask 255.255.0.0 192.168.119.0
#ping docker 内部网关就可以 ping 通了
ping 172.17.0.1

然后就可以直接在 windows 下 ping wsl2 中 docker 的内部网络了方便调试

实操

wsl2 内的 docker

root@69033e222523:/# ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
5: eth0@if6: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
    link/ether 02:42:ac:13:00:03 brd ff:ff:ff:ff:ff:ff link-netnsid 0
    inet 172.19.0.3/16 brd 172.19.255.255 scope global eth0
       valid_lft forever preferred_lft forever

wsl2

 ⚡ 06/14|10:25:19  ~  ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000
    link/ether 00:15:5d:ed:bb:c1 brd ff:ff:ff:ff:ff:ff
    inet 172.18.170.161/20 brd 172.18.175.255 scope global eth0
       valid_lft forever preferred_lft forever
    inet6 fe80::215:5dff:feed:bbc1/64 scope link
       valid_lft forever preferred_lft forever
3: docker0: <NO-CARRIER,BROADCAST,MULTICAST,UP> mtu 1500 qdisc noqueue state DOWN group default
    link/ether 02:42:c8:6b:eb:52 brd ff:ff:ff:ff:ff:ff
    inet 172.17.0.1/16 brd 172.17.255.255 scope global docker0
       valid_lft forever preferred_lft forever
4: br-7358ad5430e2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
    link/ether 02:42:6f:37:ea:f3 brd ff:ff:ff:ff:ff:ff
    inet 172.19.0.1/16 brd 172.19.255.255 scope global br-7358ad5430e2
       valid_lft forever preferred_lft forever
    inet6 fe80::42:6fff:fe37:eaf3/64 scope link
       valid_lft forever preferred_lft forever
6: veth0545bc9@if5: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue master br-7358ad5430e2 state UP group default
    link/ether 6e:6e:aa:ee:87:8f brd ff:ff:ff:ff:ff:ff link-netnsid 0
    inet6 fe80::6c6e:aaff:feee:878f/64 scope link
       valid_lft forever preferred_lft forever
 ⚡ 06/14|10:43:06  ~  iptables -P FORWARD ACCEPT

管理员 PowerShell

PS D:\Users\lm> sc start RemoteAccess
PS D:\Users\lm> route add -P 172.19.0.1 mask 255.255.0.0 172.18.170.161
 操作完成!
PS D:\Users\lm> ping 172.19.0.3

正在 Ping 172.19.0.3 具有 32 字节的数据:
请求超时。
请求超时。

172.19.0.3 的 Ping 统计信息:
    数据包: 已发送 = 2，已接收 = 0，丢失 = 2 (100% 丢失)，
Control-C
PS D:\Users\lm> route add -P 172.19.0.0 mask 255.255.0.0 172.18.170.161
 操作完成!
PS D:\Users\lm> ping 172.19.0.3

正在 Ping 172.19.0.3 具有 32 字节的数据:
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63

172.19.0.3 的 Ping 统计信息:
    数据包: 已发送 = 3，已接收 = 3，丢失 = 0 (0% 丢失)，
往返行程的估计时间(以毫秒为单位):
    最短 = 0ms，最长 = 0ms，平均 = 0ms
Control-C
PS D:\Users\lm>

Algorithm

Review

Tips

Share-wsl2中docker内部网络的ip转发

指南

实操