ARST打卡第265周

lc2928_给小朋友们分糖果1 【TED演讲】如何同时且高效的做好多件事 美团大规模KV存储挑战与架构实践 solana合约开发文档

Algorithm

lc2928_给小朋友们分糖果1

思路:

直接暴力遍历 O(n^2). 遍历第一，二个人的糖果分配其实就是确定了三个人的糖果分配，因为n要分完。

一开始j–错写成i–导致TLE了一发，尴尬

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int distributeCandies(int n, int limit) {
        int ans = 0;
        for (int i = limit; i >= 0; i--) {
            // 适当剪枝
            int jlimit = min(n - i, limit);
            for (int j = jlimit; j >= 0; j--) {
                int k = n - i - j;
                if (0 <= k && k <= limit) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

可以看看题解 更优化的O(n) 版本的剪枝和容斥原理O(1)计算。

其中容斥原理先给一个人分limit+1，再把剩下的分给 三个人 十分精妙。

Review

【TED演讲】如何同时且高效的做好多件事

其实标题有歧义。实际演讲者表达的是人生长期可以研究不同的领域，可以相互借鉴从而激发灵感。

和大脑神经学里面的聚焦思维以及发散思维的思考其实是类似的。

不能一直做一个想不出来的事情，可以适当放松一会，或者做点别的事情，可能发散思维就让你想到了答案。

Tips

美团大规模KV存储挑战与架构实践

工作多线程的 Run-to-completion 线程模型很多好项目都有使用.

但是直接先读缓存绕过工作队列真是精妙:

针对这个问题，我们对线程队列模型又做了如上图右侧所示的改造。新的模型下，我们让网络线程直接去做读请求的处理，对于能够命中内存引擎的读请求，其处理模型就是一个 RTC（Run-to-Completion）模型。

具体来讲，当网络线程收到一个请求之后，会先判断是否为一个读请求，如果是，就会直接去读内存引擎。我们服务的内存引擎会缓存硬盘引擎上的热点数据，如果内存引擎命中的话，网络线程就可以直接返回结果给客户端。这样在网络线程内就实现了请求的闭环处理，相比原来的模型可以去除所有因请求流转造成的 CPU 资源消耗。而对于写和读未命中内存引擎的请求，仍然需要经过原来的请求处理路径，去硬盘引擎读或者写数据。

两机房容灾: 第三机房省掉了很多服务器，只留下一个见证者服务即可，大大节省成本。

以下操作类似于区块链里面的智能合约只写入最终的数值:

由复制操作改为复制变更后的数据：像 INCR 类接口，A 集群的 money T1 时刻通过 INCRBY money 20 变成了 120，然后 B 集群 T2 时刻通过 INCRBY money 30 变成了 130。A 集群收到 B 集群的复制时，因为时间戳比自己的本地值大，它会执行 INCRBY money 30 变成 150；然后 B 集群收到 A 集群的复制时，因为时间戳比自己的本地值小，它会把这个复制请求给忽略掉，就造成了数据冲突。针对这个问题，我们将所有操作的数据复制都改成了复制操作后的数据，而不是这个操作本身，来解决类似 INCRBY 这种接口的数据冲突问题。

Share

solana合约开发文档

分布式存储批处理里面的文件，流处理里面的事件，solana区块链存储里的account。 其实都是一个小型，自包含的不可变对象。

可以学习一下当前的web3合约里面的开发，看看能不能借鉴经验，融会贯通。