Algorithm

本周选择的算法题是：Climbing Stairs

规则如下：

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution

class Solution:
    # 解法一: x = f(x-1) + f(x-2)
    def climbStairs(self, n: int) -> int:
        if n <= 1: return 1
        return self.climbStairs(n-1) + self.climbStairs(n-2)

class Solution:
    # 解法二: 备忘录
    def climbStairs(self, n: int) -> int:
        dp = {}
        dp[0], dp[1], dp[2] = 1, 1, 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

class Solution:
    # 解法三: 根据前两结果顺序递推
    def climbStairs(self, n: int) -> int:
        pre1, pre2 = 0, 1
        for _ in range(1, n):
            pre1, pre2 = pre2, pre1 + pre2

        return pre1 + pre2

Review

Whole-Module Optimization in Swift 3 可以从这篇文章看看编译器在优化的过程是如何思考的。

就 Whole-Module 本身而言，它采取的策略是既然目前的方式存在“盲区”，无法在单个文件编译时获取更为全面的信息（类型、调用上下文等），那将整体模块看为一个整体，以全局的视野来优化。

Whole-Module 的特点：

Whole-Module 工作于 SIL 这一层
将 Module 内的所有 Swift 文件视为一个整体，从而可以得到更多的上下文信息
虽然官方团队说 Whole-Module 支持增量编译，但实际上的效果是微乎其微的

我想，苹果的编译器团队在以整个模块为单位考察编译时长时，发现还存在优化空间，于是致力于去解决它。所以要做好性能优化，全面的测量/检测能力是不可或缺的，它能帮助我们发现系统的瓶颈，以及为我们的改善目标提供数据支撑。

Tip

将大文件拆分成多个小文件:

split -b 10m /path/to/source.file /dest/path/xxx

做了一张 IP 协议的思维导图，以 IPv4 为主：

xmind

Algorithm

Solution

Review

Tip

Share