Algorithm

本周选择的算法题是：Find All K-Distant Indices in an Array。

impl Solution {
    pub fn find_k_distant_indices(nums: Vec<i32>, key: i32, k: i32) -> Vec<i32> {
        let mut ans = Vec::new();
        for i in 0..nums.len() {
            let mut a: i32 = -1;
            for j in 0..nums.len() {
                let distant = ((i as i32) - (j as i32)).abs();
                if distant <= k && nums[j] == key {
                    a = i as i32;
                }
                if distant <= k && nums[j] == key {
                    a = i as i32;
                }
            }
            if a != -1 {
                ans.push(a);
            }
        }
        ans
    }
}

Review

An Abridged Cartoon Introduction To WebAssembly

虽然是17年的文章，但是对于 WebAssembly 的特点和相对于传统 JavaScript 的优势介绍的很全面，总体上会有以下几个优势：

Downloading - 因为文件更小、更紧凑，所以能减少下载时间
Parsing - 不需要 parsing，取而代之的是 decoding，而解码一个 WebAssembly 文件比解析一个 JavaScript 文件要快很多
Compiling & Optimizing - 只需要很少的时间做编译和优化，因为在 WebAssembly 文件上传到服务器之前就已经完成了大部分的编译和优化，而 JavaScript 在面对动态数据类型时需要编译多次
Re-optimizing - 不需要，因为在第一次编译时就有足够的信息告诉编译器生成最好的代码
Execution - 运行的更快，因为 WebAssembly 指令能按照机器的想法优化
Garbage Collection - 由于不支持 GC，所以不需要花费这个时间

附上一张 .wasm 文件的示意图：

Tip

Tango，一个快速创建带有截图操作指南的 Chrome 扩展工具，最近在使用 grafana 的时候很方便将操作方式录制下来共享给其他伙伴。

Python 的内存管理策略

通过私有堆（private heaps）维护所有的 Python 对象和数据结构，这个区域只有 Python 解释器能访问
通过内置的 memory manager 管理这个堆，它为 Python 对象进行必需的内存分配工作
使用了一个内置的 GC，用于回收内存

为什么要使用 GC？

Python 在内存管理上主要是依靠引用计数算法，引用计数的优势是即时，当对象不再需要时很容易回收内存。但是它有一个问题，就是无法解决因为循环引用而造成的内存泄漏。

GC 与循环引用有什么不同？

GC 不是实时的，而是周期性的执行，GC 执行时需要“暂停”程序的运行。

GC 是如何发现循环引用的？

类似于“标记-清除”算法，不过在标记的过程中实际做的是测试，也就是遍历所有的容器对象，并将它们对其他容器对象的引用计数全部减 1，整个过程结束后，将引用计数为 0 且没有任何活动对象指向它的对象标记为不可达。

更多信息可以参阅：

GC 在 Python 中是如何工作的？

Python 将容器对象分为了三代：

0 代，新生代对象，生命周期短
1 代，0 代对象经过一定的 GC 次数后仍然存活，晋升为1代
2 代，1 代对象经过一定的 GC 次数后仍然存活，晋升为2代

每代都有一个独立的计数器和阀值（threshold），计数器存储对象数量，当计数器超过阀值时启动 GC；如果同时有多代超出了阀值，GC 会选择最老的代，这是因为最老的代也会收集比它年轻的代。

分代的回收的好处是提升垃圾回收的效率，因为无论哪种语言，对于变量在内存中的创建/销毁总有频繁和不频繁的，比如全局变量和自动变量。引入分代回收机制可以针对频繁的 “代” 做更多的检测，不频繁的 “代” 少做，避免对全部对象做检测，以此来提高回收效率。

Python 与 OC 内存管理的差异简要

两者都是引用计数为主的策略，除此之外 Python 引入了 GC 来解决循环引用的问题
- Python 使用类似于标记-清除算法来处理循环引用：
  - 标记 - 遍历所有对象，通过对计数-1来测试它们的可达性
  - 清除 - 如果一个对象没有被标记为可达，则将其回收
- Python 为了优化 GC 效率，引入了分代回收
iOS 不支持 GC，不过早期的 OS X 系统是支持 GC 的：
- 10.5 通过 NSGarbageCollector 实现 GC，直到 10.8 被废弃
- 同 stop-the-world 不同，OC 的 GC 工作在一个低优先级的后台线程，并且它会在接收用户事件时中断，以快速响应用户的操作