轉(zhuǎn)自我的 blog: 通過 LeetCode 最簡單的一道題探究 Swift 源碼
今天下午閑來無事欺栗，突然想到一直都沒有完成的刷爆 LeetCode 的成就壳快，于是就又躍躍欲試了。
之前通過 Java 和 Python 刷過十幾道題，然后就不了了之了√萜。現(xiàn)在 LeetCode 也支持 Swift 了，所以就想用 Swift 解鎖成就七婴。
我是個(gè)算法渣察滑，在這方面從來沒有過自信，「算法導(dǎo)論」中那些面試經(jīng)常提到的算法看了三四遍也始終無法牢牢把握户盯，前幾天又入手了據(jù)說更適合實(shí)際應(yīng)用的「算法」，心想一定要償還這部分的技術(shù)負(fù)債吗伤。
打開 LeetCode 網(wǎng)站硫眨，直接按難易度排序，先從最簡單的開始巧号。
第一道題姥闭，Reverse String泣栈，反轉(zhuǎn)字符串。沒什么特別復(fù)雜的南片，就是純逐個(gè)字符反轉(zhuǎn)疼进，并不是反轉(zhuǎn)單詞。
第一想法非常簡單伞广，就是創(chuàng)建一個(gè)空字符串，遍歷給定的字符串减拭，挨個(gè)字符插入到新字符串的第一位置区丑，這樣遍歷結(jié)束后新的字符串就是反轉(zhuǎn)后的結(jié)果沧侥，so easy！
打開 Playground宴杀，分分鐘就寫好了下面的代碼：
class Solution {
func reverseString(s: String) -> String {
var ret: String = ""
for c in s.characters {
ret.insert(c, atIndex: ret.startIndex)
}
return ret
}
}
復(fù)制到 LeetCode 中旺罢，先是猛擊 Run Code绢记，沒毛病荣暮，然后就猛擊 Submit Solution 了。果不其然护赊，Time Limit Exceeded……敗在了一個(gè)無比長的字符串手里砾跃。
于是就順其自然地想到了第二個(gè)解決方案：交換字符位置。Swift 的 String判耕，所有的字符都是放在 characters 這個(gè)屬性里的（看命名是個(gè)集合翘骂，其實(shí)真正的類型是 String.CharacterView，這個(gè)類封裝了對于字符集合的各種操作）草丧，所以操作這個(gè) characters 的索引莹桅，應(yīng)該就可以達(dá)到交換字符的目的。正當(dāng)我準(zhǔn)備動(dòng)手的時(shí)候懂拾，Xcode 的自動(dòng)補(bǔ)全蹦出個(gè) reverse() 方法铐达，原來 Swift 已經(jīng)提供了反轉(zhuǎn)功能娶桦，這下子可方便多了，一句代碼的事衷畦，這個(gè) solution 也通過了：
func reverseString(s: String) -> String {
return String(s.characters.reverse())
}
這里值得一提的是：在 Dash 的文檔里祈争，這個(gè) reverse() 是 Swift 3 之前的 API角寸，返回的是一個(gè) [Character]忿墅，復(fù)雜度是 O(N)沮峡。到了 Swift 3邢疙，這個(gè)方法改為了 reversed()，復(fù)雜度也變成了 O(1)疟游，返回的是 ReversedCollection<String.CharacterView>颁虐。對于這兩種返回值，String 都可以直接作為參數(shù)來初始化另绩。
不知道為什么笋籽，在 Xcode 7.3.1 中這個(gè)
reverse()自動(dòng)補(bǔ)全會有兩個(gè):
reverse_autocomplete.png
但 option+click 顯示的是：
reverse_xcode.png
返回ReversedCollection<String.CharacterView>應(yīng)該是 Swift 3 才有的干签，但是 cmd+click 進(jìn)去發(fā)現(xiàn)這個(gè)方法聲明在CollectionType的一個(gè) extension 中，在2.2的源代碼中也發(fā)現(xiàn)了：
reverse_source.png
從這段代碼里也可以看出這個(gè)方法的復(fù)雜度是 O(1)喘沿，而且在 Swift 3 中也要改名為reversed()竭贩。
~~奇怪留量，文檔中明明寫的是 O(N) 的版本，但是 Playground 卻顯示的是這個(gè)楼熄，不知道 Swift 是如何動(dòng)態(tài)選擇到這個(gè)方法的可岂。這個(gè)ReversedCollection我看了初始化方法的實(shí)現(xiàn)過程，也沒有發(fā)現(xiàn)有實(shí)現(xiàn)反轉(zhuǎn)的代碼稚茅，也搞不清楚是如何做到 O(1)的。
所以下面的分析都是針對 O(N) 版本的reverse().~~~
很榮幸得到了喵神的指點(diǎn)咽块，這里引述一下他的評論：
實(shí)際上你提交的確實(shí)是返回
ReversedCollection的 O(1) 版本欺税，它也不是 Swift 3 才有的。Swift 在多個(gè)方法滿足簽名的時(shí)候峭竣，會幫你選擇最具體的那個(gè)方法晃虫，也就是約束最強(qiáng)的方法。這里String的reverse同時(shí)可以匹配到SequenceType和CollectionType的Index滿足BidirectionalIndexType的兩個(gè)版本扛吞。因?yàn)楹笳呦啾扔谇罢叩募s束更多 (也就是說滿足后者的話一定是滿足前者的)荆责，因此 Swift 將更有機(jī)會使用經(jīng)過優(yōu)化的代碼。String.characters 的索引滿足 BidirectionalIndexType 雙向索引盲泛，所以在reverse的時(shí)候只需要返回一個(gè)交換了 startIndex 和 endIndex 的結(jié)構(gòu)體 (ReversedCollection) 就可以了键耕。
所以可能是文檔和實(shí)際代碼出現(xiàn)了出入，導(dǎo)致我以為我用的是 O(N) 的方法村视。下面就是針對 O(N) 版的分析酒奶。
一句代碼就解決了這個(gè)問題，成就感不是很大啊杠氢，于是我就想看看 Swift 是如何實(shí)現(xiàn)這個(gè)方法的另伍。通過查文檔（Swift 2.2），發(fā)現(xiàn)這個(gè) String.CharacterView 采納（沿用了 The Swift Programming Language 中文版里的翻譯）的協(xié)議有 RangeReplaceableCollectionType, CollectionType, SequenceType ：
這個(gè)方法最后發(fā)現(xiàn)是在 SequenceType 這個(gè)協(xié)議中聲明的：
但是在源碼中的 SequenceType.swift 這個(gè)文件中并沒有找到關(guān)于這個(gè)方法的任何聲明，通過對源碼的全局搜索中贝，找到這個(gè)方法的實(shí)現(xiàn)是寫在 SequenceAlgorithms.swift.gyb 這個(gè)文件中（關(guān)于 gyb 文件是什么臼朗，請點(diǎn)擊這里)：
//===----------------------------------------------------------------------===//
// reverse()
//===----------------------------------------------------------------------===//
extension SequenceType {
/// Returns an `Array` containing the elements of `self` in reverse
/// order.
///
/// Complexity: O(N), where N is the length of `self`.
@swift3_migration(renamed="reversed")
@warn_unused_result
public func reverse() -> [${GElement}] {
// FIXME(performance): optimize to 1 pass? But Array(self) can be
// optimized to a memcpy() sometimes. Those cases are usually collections,
// though.
var result = Array(self)
let count = result.count
for i in 0..<count/2 {
swap(&result[i], &result[count - i - 1])
}
return result
}
}
這段代碼寫的很明白了视哑，就是不斷向數(shù)組的中間靠近，交換首尾的元素蒜撮。還有值得挖的就是 swap 的實(shí)現(xiàn)了跪呈，這個(gè)方法是在 Sort.swift.gyb 中：
/// Exchange the values of `a` and `b`.
///
/// - Requires: `a` and `b` do not alias each other.
public func swap<T>(inout a : T, inout _ b : T) {
// Semantically equivalent to (a, b) = (b, a).
// Microoptimized to avoid retain/release traffic.
let p1 = Builtin.addressof(&a)
let p2 = Builtin.addressof(&b)
_debugPrecondition(
p1 != p2,
"swapping a location with itself is not supported")
// Take from P1.
let tmp : T = Builtin.take(p1)
// Transfer P2 into P1.
Builtin.initialize(Builtin.take(p2) as T, p1)
// Initialize P2.
Builtin.initialize(tmp, p2)
}
這段代碼也是交換的基本操作了，顯示比較兩個(gè)元素的地址苹支，如果地址相同就不做交換误阻，然后就是通過中間變量來交換兩個(gè)元素的值究反。
