ARTS #183

Algorithm

规则

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

The absolute difference of two numbers is the absolute value of their difference.
The average of n elements is the sum of the n elements divided (integer division) by n.
The average of 0 elements is considered to be 0.

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 105

Solution

impl Solution {
    pub fn minimum_average_difference(nums: Vec<i32>) -> i32 {
        let (mut ans, mut min_diff) = (0, i64::MAX);
        let total_sum = nums.iter().map(|&x| x as i64).sum::<i64>();
        
        let mut prefix_sum: i64 = 0;
        for i in 0..nums.len() {
            prefix_sum += nums[i] as i64;
            let prefix_avg = prefix_sum / (i + 1) as i64;
            
            let mut suffix_avg = total_sum - prefix_sum;
            if i != nums.len() - 1 {
                suffix_avg /= (nums.len() - i - 1) as i64;
            }

            let diff = (prefix_avg - suffix_avg).abs();
            if diff < min_diff {
                ans = i as i32;
                min_diff = diff;
            }
        }
        ans
    }
}

Review

From Zero to 50 Million Uploads per Day: Scaling Media at Canva

文章介绍了 Canva 从 MySQL 迁移到 Dynamodb 的心路历程，从注意到 MySQL DDL 性能下降开始，到迁移技术选型，到最终选择了 Dynamodb 的过程。

虽然没有透露完成这件事用了多少人、花了多少时间，但要将一个关系型数据库平顺迁移到非关系型数据库肯定不会太简单，不过为了迁移后的数据库性能提升也是值得的。

最后 Canva 团队站在今天思考如果重新遇到当初的问题，给了新的建议：

If we were facing the same problem today, we’d once again strongly consider mature hosted “NewSQL” products such as Spanner or CockroachDB.

Tip

一个支持很多语言的通用插件系统: Extism。

用 CRDT 同步目录树的常见策略

文件系统目录树的冲突一般分为以下四种：

add(a) remove(b) 冲突
name 冲突
add(a) remove(a) 冲突
update(a) remove(b) 冲突

冲突类型的命名参考自 File system on CRDT.pdf

首先是 “add(a)

remove(b) 冲突”，它表示向 Toco 目录添加文件 prog.c 的同时删除了目录 Toto：

然后是 “name 冲突”，它表示向同一个目录增加同名文件：

然后是 “add(a)

remove(a) 冲突”，同时添加一个文件，然后其中一个节点删除文件：

最后是 ”update(a)

remove(b) 冲突“，一个更新文件/目录内容，一个删除文件/目录：

这些都是很常见的冲突。

你可能注意到了，我们更多是在描述文件目录的变化同步，因为文件本身很难被描述为 CRDT 数据结构（Map/Set/Array/…），无法描述，自然就无法应用 CRDT 了。

延伸一下，业界关于文件冲突的做法差不多，比如坚果云：

Office：

Dropbox：

文件冲突发生在三种情况下：

两个用户同时编辑同个文件
有人在离线状态下编辑了文件，其他人也编辑了
文件在另一个设备上处于打开状态，在未产生实质性修改的情况下 Dropbox 收到了更新指令 — 有些应用程序提供了自动保存功能，因此这种情况发生的频率也很高

因为任何文件都会产生冲突，最有效的做法是让用户手动处理、合并它们，比如一个 Word 文件，可以参考微软官方的帮助文档来处理：Compare and merge two versions of a document。

Dropbox 对此类场景的官方建议是：不要实时协作，避免冲突的最佳做法是把你的文件移到 Dropbox 外面去，确保没有其他人可以访问到它，然后完成你的工作后再移回 Dropbox。

业界在这件事上保持了高度一致，保留最先同步的文件，然后将后保留的文件自动重命名，是典型的 [First Writer Wins](https://en.wikipedia.org/wiki/Eventual_consistency#:~:text=Some people use “first writer,a read finds an inconsistency) 策略。

回到目录树同步问题上，用 CRDT 解决分为几种不同的数据类型：

G-Set
2P-Set
LWW-Set
C-Set
OR-Set

它们决定了同步的行为。

G-Set：

全称是 “Grow Only Set”，它只有添加操作、没有删除操作，属于 state-based CRDT 的一种，特点是无论 update 还是 merge 均能保证单调递增。

2P-Set：

全称是 “Two Phases Set”，它的内部使用了两个 G-Set，当从 Set A 中删除元素时，并不实际删除，而是将被删除的元素添加进 Set R：

最终 query 状态时，如果元素在 Set A 且不在 Set R，则表示元素存在。

LWW-Set：

全称是 “Last Writer Wins Set”，每个操作关联一个时间戳和一个可见性标记，当两个操作同时发生时，时间戳更大的那个被执行：

C-Set：

全称是 “Counter Set”，该结构带有一个记数器，对应两种操作方法 inc() 和 dec()，

只当：

counter <= 0 且 counter 被置为 1 时添加元素
counter > 0 且 counter 被置为 0 时移除元素

OR-Set：

全称是 “Observed Remove Set”，它是一个 “添加优先” 的 set，每个节点关联一个唯一的 tag，执行添加操作时创建并关联 tag，只当 tag 全部被移除时才执行删除：

对应的，也有 Remove Win Set，它是 “删除优先”。

OR-Set 相对来说是一种较实用的结构，但它在实现上要考虑：

反复 add 和 remove 的场景下会产生大量的 tag，空间资源占用大
如何省空间又生成全局唯一的 tag
需要定期进行垃圾回收

回顾一下上文提到的四种冲突类型：

add(a) remove(b) 冲突
name 冲突
add(a) remove(a) 冲突
update(a) remove(b) 冲突

通过定义文件的唯一标识符（文件路径 + 文件类型）并关联它的文件内容，以此作为 CRDT 数据结构中的元素，再选择你期望的 Set，可以解决 “add(a)

remove(a) 冲突”、“update(a)

remove(b) 冲突” 这两种冲突。

解决 “add(a)

remove(b) 冲突” 会麻烦一些，需要做出选择：

目录仅在逻辑上存在，所有操作基于文件（只考虑叶子节点），意味着空文件夹不会被同步到其他端，这种方式可以避免冲突
第二种方法要处理所谓的 “孤儿元素”

这两种方式均采用相同的元素结构：（文件名称+文件类型+文件路径+文件内容）。

第一种方法类似 Git，每个文件都有一个从 root 开始的唯一路径，由于目录并不真实存在，其产生的删除文件动作最终会演变化文件内容冲突；第二种方法会根据 Set 不同而行为不同：

删除优先，新增加的文件被跳过
添加优先，但该目录下将只会存在这一个文件
“孤儿元素”，将该文件放到 root 目录下，比如类似 Linux 和 Unix 那样放到 lost-and-found 下
“孤儿元素”，就近原则，将文件放到离它最近的还存在的父目录下

除了 “name 冲突”，其他冲突都可自动化解决。

Algorithm

规则

Solution

Review

Tip

Share

用 CRDT 同步目录树的常见策略