ARTS 第三周

Algorithm

给定一个包含n + 1个整数的数组nums，其数字都在 1 到 n之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 :
1
2
输入: [1,3,4,2,2]
输出: 2

思路：
该算法可用二分法、二进制或快慢指针等等方法来解，本次主要记录一下快慢指针的方法。
快慢指针的方法主要借鉴了 Floyd 判圈算法，该算法主要用于检测链表是否有环。在本题中对nums建图，可将问题等价为： LeetCode142: 环形链表 II ，可分别设置快慢指针，慢指针每次走一步，快指针每次走两步，根据 Floyd 判圈算法两指针在有环的情况下一定会相遇，相遇后将慢指针放置起点，然后两个指针每次同时走一步，相遇点便是答案。

解答：

func findDuplicate(_ nums: [Int]) -> Int {
    var fast = nums[0]
    var slow = nums[0]

    repeat {
        fast = nums[nums[fast]]
        slow = nums[slow]
    } while (fast != slow)

    slow = nums[0]
    while(slow != fast) {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

Review

Swift Method Dispatching

Swift 作为一门静态语言，其在方法派发上的性能表现要强于 OC 不少，本文中主要介绍了 Swift 的方法派发机制。

在 OC 中，clang 会将方法调用翻译成对objc_msgSend这个函数的调用，传入相应的target、SEl以及参数，该方法是由汇编实现的，负责OC中的方法派发：

id objc_msgSend ( id obj, SEL op, … )
{
    Class c = object_getClass(obj);
    IMP imp = CacheLookup(c, op);
    if (!imp) {
        imp = class_getMethodImplementation(c, op);
    }
    jump imp(obj, op, …);]
}

其中，影响效率的最大因素在于找到具体的方法实现IMP，如果方法缓存命中，那么效率上基本等同于在hashMap中取值，这种情况还好，但如果未命中，则需要去沿着继承体系在类的方法列表中寻找对应的实现并加入缓存，再跳到该实现执行具体函数，这样的派发方式相对较慢。因此objc_msgSend也被称为跳板函数。

在 Swift 中，使用了 Virtual Method Table 来支持运行时的方法绑定，文章通过对 SIL 的分析发现 vtable 本质上是一个 key 为方法名，value 为方法实现的字典，而通过汇编代码可以看到 Swift 代码几乎做到了将调用方法直接映射到处理器指令，并将调用对象存入寄存器中。通过传入对象中指向 metadata 的指针找到保存其类信息的结构体，进而通过偏移量找到相应的方法。

当打开编译期优化选项后，Swift 代码执行速度可能更快，原因在于：

当编译器知道目标对象的具体类型后，non-final 方法可被直接调用
编译期会用内联的方式直接将方法实现内联至方法调用的地方，从而省去了函数调用的开销

Tip

本周依旧记录 Swift 的新特性，版本来到5.3。

Multi-pattern catch clauses

简单来说，一个catch代码块可以 handle 多种错误类型了：

enum TemperatureError: Error {
    case tooCold, tooHot
}

do {
    let result = try checkReactorOperational()
    print(“Result: \(result)”)
} catch TemperatureError.tooHot, TemperatureError.tooCold {
    print(“Shut down the reactor!”)
} catch {
    print(“An unknown error occurred.”)
}

Multiple trailing closures

多个尾随闭包也被支持了~

// Before
struct NewContentView: View {
    @State private var showOptions = false

    var body: some View {
        Button {
            self.showOptions.toggle()
        } label: {
            Image(systemName: "gear")
        }
    }
}

// After
struct NewContentView: View {
    @State private var showOptions = false

    var body: some View {
        Button {
            self.showOptions.toggle()
        } label: {
            Image(systemName: "gear")
        }
    }
}

Synthesized Comparable conformance for enums

实现Comparable的枚举可以用来比大小了，如果带有的关联值也是Comparable的话，也是可以比的哦~

enum WorldCupResult: Comparable {
    case neverWon
    case winner(stars: Int)
}

let americanMen = WorldCupResult.neverWon
let americanWomen = WorldCupResult.winner(stars: 4)
let japaneseMen = WorldCupResult.neverWon
let japaneseWomen = WorldCupResult.winner(stars: 1)

let teams = [americanMen, americanWomen, japaneseMen, japaneseWomen]
let sortedByWins = teams.sorted()
print(sortedByWins) // americanMen japaneseMen japaneseWomen americanWomen

左耳朵耗子：什么是函数式编程？

因为新公司的项目使用一些 RxSwift，而自己本身对这块只是一知半解，希望今后能利用一些时间来把函数式响应式编程以及 MVVM 做一个系统的学习和实践，就以这篇耗子叔的函数式编程作为开始吧。

本文就函数式编程做了详细的介绍并配以生动的代码示例，从其历史到特点和应用的技术，还介绍了纯函数式语言 Scheme，最后通过对比的方式讲明了何为函数式编程思维方式。读了三遍，每次都有新的感受，让人迫不及待想去动手实践。😜

Algorithm

Review

Tip

Multi-pattern catch clauses

Multiple trailing closures

Synthesized Comparable conformance for enums

Share