CodingTour —
ARTS #4

Algorithm

本周选择的算法题是：Sum Root to Leaf Numbers

规则如下：

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution

我实现的方案：

解法一：递归

Runtime：28 ms，快过 99.66%。

Memory：13.3 MB，低于 23.25%。

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        return self.sumNumbers2(root, 0)

    def sumNumbers2(self, root: TreeNode, cumulator: int) -> int:
        if root is None:
            return 0

        cumulator = cumulator * 10 + root.val
        if root.left is None and root.right is None:
            return cumulator
        else:
            return self.sumNumbers2(root.left, cumulator) + self.sumNumbers2(root.right, cumulator)

解法二：栈

Runtime：36 ms，快过 88.28%。

Memory：13.3 MB，低于 21.86%。

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        if root.left is None and root.right is None:
            return root.val

        cumulator = 0
        nodes = [root]
        while len(nodes) > 0:
            node = nodes.pop(0)

            if node.left is None and node.right is None:
                cumulator += node.val

            if node.left is not None:
                node.left.val += node.val * 10
                nodes.append(node.left)

            if node.right is not None:
                node.right.val += node.val * 10
                nodes.append(node.right)

        return cumulator

这个解法不太优雅，因为修改了原始的 TreeNode。

可以把 nodes 集合的元素类型变更为元组，存 node 的同时把高位也一并存起来。

解法三：栈，使用元组

Runtime：40 ms，快过 66.63%。

Memory：13.3 MB，低于 25.81%。

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0

        if root.left is None and root.right is None:
            return root.val

        cumulator = 0
        nodes = [(root, 0)]
        while len(nodes) > 0:
            node, high = nodes.pop(0)

            carry = high + node.val
            if node.left is None and node.right is None:
                cumulator += carry
                continue

            if node.left is not None:
                nodes.append((node.left, carry * 10))

            if node.right is not None:
                nodes.append((node.right, carry * 10))

        return cumulator

Review

Method dispatch in Swift
看完这篇才对 Swift 的方法派发有了一个初步的印象，做个简单的总结：

  • 静态派发，和 C 一样，在编译时确定函数调用地址，也称直接派发，是速度最快的派发方式
  • 动态派发，程序不知道如何调用一个函数，直到运行时才确定，静态派发虽然好，但也限制了灵活性，无法满足多态这样的场景。在 OOP 语言中，动态派发得到了广泛的应用，值得一提的是，Swift 提供了2种方式实现动态派发：函数表派发和消息派发
  • 函数表派发，这是编译期语言最普遍采用的派发方式，基本上，一个对象对应了一张像 virtual table 或 witness table 的表，表中包含了一组函数指针指向实际的方法实现，这张表在编译期构建，只提供两种基本的指令：读和跳转，这也是一种相当快的派发方式
  • 消息派发，OC 的派发方式，每一次调用 OC 的方法时，将通过 objc_msgSend 进行查询，从技术上来讲，这是一种从给定的类到整个类的继承关系的遍历，并在遍历中提取出实现。与函数表派发不同的是，消息派发表可以在运行时修改，我们可以通过它在运行时调整对象的行为，比如 Method Swizzling 这种流行的技术就是最好的证明。这是最动态的派发方式，当然也是查询性能最差的方式

Swift 支持静态派发、函数表派发和消息派发，可以通过 SIL 判断具体的派发策略：

  • 如果一个方法使用函数表派发，那么你会看到 vtable(or witness_table for protocols)的字眼：

  • sil_vtable Animal {
#Animal.makeSound!1: (Animal) -> () -> () : main.Animal.makeSound() -> ()	// Animal.makeSound()
......
}

  • 如果一个方法是通过消息派发，那么你会看到 volatile 的字眼，你也会看到两个标记：foreign 和 objc_method，这表示是通过 OC 运行时调用的方法：

  • %14 = class_method [volatile] %13 : $Dog, #Dog.beWild!1.foreign : (Dog) -> () -> (), $@convention(objc_method) (Dog) -> () // user: %15
  • 如果不是以上两种情况，则是静态派发

从数据类型和修饰符来看：

  • 所有的值类型和 Struct 都是静态派发，因为它们都不可被重写
  • 明确执行的：
    • final 修饰的方法也是静态派发
    • dynamic 修饰的方法是消息派发
  • 普通的 extensions(没有 final、dynamic 和 @objc 修饰符的)都是直接派发

从 Swift 的原则上来看：

  • 静态派发是优先级最高的

  • 如果需要覆盖(override)，则函数表是候选的派发方式

  • 如果既需要覆盖，又要对 OC 可见，那就选择消息派发

如果你不确定 Swift 会用哪种派发方式，或者担心未来 Swift 的默认行为会变，那么可以用一些显示的方法(比如给 extensions 加上 @objc)来消除这种不确定性。


I never understood JavaScript closuers
绝对不是标题党！总结得非常好，看完感觉对 JS 的理解又加深了一些 :)

总结下：

  • Local execution context，局部执行上下文

  • Global execution context，全局执行上下文

  • Function = definition + closure，作者用的背包比喻很恰当，函数作用域内被捕获的变量存放到了一个背包中，这个背包和函数定义是绑定在一起的，JS 寻找变量时，按以下顺序寻找：

    • 背包 -> Local execution context -> Global execution context

    其中 Local execution context 的生命周期自然就是函数的进栈和出栈

顺便提下 Swift 的 Closures 和 Objective-C 的 Blocks：

  • 首先它们是兼容的，这意味着你可以传递 Closures 给 OC 方法
  • 因为 Swift 的 Functions 和 Closures 是相同的类型，所以你也可以传递 Functions
  • Swift 的变量是可变而不是复制的，换句话说，OC 的 __block 在 Swift 里是默认的行为

Tip

本周学习到的一些内容：

  • Swift 虽然是自动管理内存，但是还是有可能产生内存访问冲突：

    • 至少有一个是长期写入访问（短期没有影响）
    • 访问的是同一块内存
    • 访问时间是重叠的

    什么时候会有写入访问：

    • 函数会在开始和结束时自动开启 inout 参数的写入访问（具体的，会在非 inout 参数计算完后）

    例子一：

    func modifyTwice(_ value: inout Int, by modifier: (inout Int) -> ()) {
    modifier(&value)
    modifier(&value)
}
  
func testCount() {
    var count = 1
    modifyTwice(&count) { $0 += count } // Overlapping accesses to 'count'
    print(count)
}

    例子二：

    func cumulate(_ value: inout Int, _ other: inout Int) {
    value += other
}
  
func testCumulate() {
    var count = 1
    cumulate(&count, &count) // Overlapping accesses to 'count'
    print(count)
}

    可以通过启用 T-San 编译来验证，T-San 将在运行时检测数据竞争。

Share

本周分享：

Swift 5 Will Enforce Exclusive Access to Memory
Exploring Memory Safety and Exclusive Access in Swift
关于内存访问冲突的说明，还有一些关于内存管理和线程安全的链接，值得一看，可以加深印象

10 Interview Questions Every JavaScript Developer Should Know
干货满满，做与不做 JavaScript 都可以看看