作者：Jacob Bandes-Storch伶氢，原文鏈接，原文日期：2015/08/05
譯者：Lou；校對：shanks呼渣；定稿：shanks
這篇博文啟發(fā)自Code Review.SE上的一個討論，同時nerd-sniped上的關(guān)于數(shù)學(xué)的有趣的學(xué)習(xí)寞埠。讓我對數(shù)學(xué)和 Swift 的結(jié)合有了興趣屁置。所以我花了一段時間來把這些知識整理成一篇博文，特別是自從我完成了對我網(wǎng)站重建的第一步以后仁连。更重要的是蓝角，我希望我能更勤勉的更新我的博客，這8年我只寫了一篇而已饭冬，希望大家能對我的博客感興趣使鹅。
這篇博文的目標(biāo)對于初學(xué)者來講，比較容易理解昌抠，同時也提供給那些已經(jīng)對這個概念熟悉的人一些有用的細(xì)節(jié)和例子患朱。希望大家能給我反饋。
假設(shè)你第一次學(xué)習(xí) Swift炊苫，你實(shí)在是太興奮了裁厅，花了一天時間反復(fù)練習(xí)，等到第二天就成了專家侨艾。于是第二天你就開始傳授課程來教別人姐直。
當(dāng)然，我很愿意成為你的第一個學(xué)生蒋畜。我也學(xué)的很快声畏，一天學(xué)下來，我也可以教別人 Swift 了。我倆繼續(xù)教別人插龄，其他的學(xué)生也學(xué)的很快愿棋，馬上跟上進(jìn)度，都可以第二天就去教別人均牢。
這是個多么讓人興奮的世界呀糠雨。但是問題來了，照這樣的進(jìn)度下去徘跪，Swift 學(xué)習(xí)者將大量涌入城市甘邀，基礎(chǔ)設(shè)施將無法支撐龐大的人口。
市長叫來最好的科學(xué)家們：“我們需要精確的數(shù)學(xué)模型垮庐！每天到底有多少人會使用 Swift松邪？什么時候這種瘋狂會終止？”
搭建數(shù)學(xué)模型
為了方便理解問題哨查，讓我們畫一副圖來表示最初幾天發(fā)生的事：
仔細(xì)觀察我們發(fā)現(xiàn)逗抑，特定的一天總的 Swifters 數(shù)量（我們用 \(S_{今天}\) 來表示）等于前一天的數(shù)量加上每個老師可以所教的學(xué)生。
$$ S_{今天} = S_{昨天} + 老師數(shù) $$
那么老師數(shù)目是多少呢寒亥？記住邮府，一個人需要花一天時間學(xué)習(xí)才能變成 Swift 專家，所以前天的每一個人都能成為老師溉奕，都可以教一個學(xué)生：\(S_{今天} = S_{昨天} + S_{前天}\)褂傀。
這下公式就簡單了！我們可以用手算了：
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
...
如果這個數(shù)列看上去有點(diǎn)熟悉加勤，那是因?yàn)檫@是斐波納契數(shù)列紊服。
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,...
不管你是否喜歡，我們的世界里處處都有斐波那契數(shù)的存在：花瓣的生長遵循斐波那契數(shù)列欺嗤，大樹的枝丫是斐波那契樹丫，當(dāng)然也有人吐槽說這不過是確認(rèn)偏誤罷了卫枝。我們發(fā)現(xiàn)煎饼，這個數(shù)列是基于非常簡單的形式的，非常容易計算：
var i = 0
var j = 1
while true {
(i, j) = (j, i + j)
print(i) // 打印1, 然后打印1, 繼續(xù)打印2, 3, 5, 8, 13, 21, 34, 55...
}
大功告成校赤！
哈哈吆玖，騙你的。我們才剛剛開始马篮。計算機(jī)美妙的地方就在于可以幫助我們快速的解決用手算很麻煩的問題沾乘。讓我們嘗試幾個例子。
42天后有多少個 Swifter浑测？
前面我們已經(jīng)差不多解決了這個問題翅阵，只要在42那邊停止循環(huán)即可歪玲。
var i = 0
var j = 1
for _ in 0..<42 {
(i, j) = (j, i + j)
}
i // returns 267914296
那么第 n 天呢？
和之前的問題類似掷匠，我們可以將其抽象成一個函數(shù)滥崩。用 n 來代替 42。
func nthFibonacci(n: Int) -> Int
{
var i = 0
var j = 1
for _ in 0..<n {
(i, j) = (j, i + j)
}
return i
}
nthFibonacci(42) // 返回 267914296
nthFibonacci(64) // 返回 10610209857723
第一周到底寫了多少 Swift讹语？
為了簡化問題钙皮，假定每個人寫代碼的速度是一樣的。知道每個人每天寫的代碼量后顽决，我們只需要把斐波那契數(shù)加起來即可短条。
func fibonacciSumUpTo(n: Int) -> Int
{
var sum = 0
for i in 0..<n {
sum += nthFibonacci(i)
// 第 i 天 使用 Swift 寫代碼的人數(shù)
}
return sum
}
fibonacciSumUpTo(7) // 返回 33
逐步簡化
不要急，Swift 的標(biāo)準(zhǔn)庫里面已經(jīng)有了一個函數(shù)叫做 reduce才菠，可以將數(shù)字加在一起茸时。我們該怎么寫呢?
[1, 1, 2, 3, 5, 8, 13].reduce(0, combine: +) // 返回 33
這樣可行，但是我們需要把每個數(shù)字都寫出來鸠儿。要是能用 nthFibonacci() 就好了屹蚊。
既然這些是連續(xù)的斐波那契數(shù)厕氨，我們可以簡單的使用1到7的范圍：
[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci)
// 返回 [1, 1, 2, 3, 5, 8, 13]
[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci).reduce(0, combine: +)
// 返回 33
或者我們可以更簡單进每，用 Swift 的range operator(...):
(1...7).map(nthFibonacci).reduce(0, combine: +) // 返回 33
這等同于 fibonacciSumUpTo
性能優(yōu)化
看上去很不錯，但是不要忘了 nthFibonacci(i) 從0開始加到 i命斧，所需的工作量將隨著i線性增加田晚。
而且我們所寫的 (1...n).map(nthFibonacci).reduce(0, combine: +) 從1到n每次湊要運(yùn)行 nthFibonacci， 這將大大增加運(yùn)算量国葬。
注意：計算越簡單的斐波那契數(shù)贤徒，真實(shí)耗費(fèi)每一步的時間幾乎可以忽略不計（開啟性能優(yōu)化）。這篇文章之前的草稿版本包括了時間消耗的表格汇四，但是我把表格去掉了接奈，怕誤導(dǎo)大家。取而代之的是通孽，我們討論的是一個相對的時間/性能的復(fù)雜度序宦。
讓我們將 nthFibonacci 和 fibonacciSumUpTo 兩個函數(shù)結(jié)合來減少一點(diǎn)運(yùn)算量：
func fastFibonacciSumUpTo(n: Int) -> Int
{
var sum = 0
var i = 0
var j = 1
for _ in 0..<n {
(i, j) = (j, i + j) // 計算下一個數(shù)
sum += i // 更新總數(shù)
}
return sum
}
fastFibonacciSumUpTo(7) // 返回 33
現(xiàn)在我們已經(jīng)將 fastFibonacciSumUpTo 的復(fù)雜度從二次降為線性了。
但是為了實(shí)現(xiàn)這個背苦，我們不得不寫了一個更加復(fù)雜的方程互捌。我們在分離相關(guān)度(把計算斐波那契數(shù)和求和分為2步) 和優(yōu)化性能之間進(jìn)行了權(quán)衡。
我們的計劃是用 Swift 的標(biāo)準(zhǔn)庫來簡化和解開我們的代碼行剂。首先我們來總結(jié)一些我們要做什么秕噪。
- 將前n個斐波那契數(shù)用線性時間(linear time)和常量空間(constant space)的方式加起來。
- 將前n個斐波那契數(shù)用線性時間(linear time)和常量空間(constant space)的方式加起來厚宰。
- 將前n個斐波那契數(shù)用線性時間(linear time)和常量空間(constant space)的方式加起來腌巾。
幸運(yùn)的是，Swift 正好有我們需要的功能！
1壤躲、 reduce 函數(shù)城菊，用 + 操作符來結(jié)合。
2碉克、 prefix 函數(shù)和惰性求值(Lazy Evaluation)
注意：prefix只有在 Xcode 7 beta 4中可用凌唬，作為 CollectionTypes 的一個全局函數(shù)使用，但其實(shí)已經(jīng)在 OS X 10.11 beta 5 API 作為 SequenceType 的擴(kuò)展出現(xiàn)了漏麦。我期望在下一個 Xcode beta 有一個延遲實(shí)現(xiàn)的版本客税；現(xiàn)在這里有一個自定義的實(shí)現(xiàn)。
3撕贞、 定制數(shù)列更耻，使用數(shù)列型協(xié)議(SequenceType protocol)
定制數(shù)列
Swift 的 for-in 循環(huán)的基礎(chǔ)是 SequenceType 協(xié)議。所有遵循這個協(xié)議的可以循環(huán)捏膨。
想要成為一個 SequenceType 只有一個要求秧均，就是提供一個創(chuàng)建器( Generator )：
protocol SequenceType {
typealias Generator: GeneratorType
func generate() -> Generator
}
而成為一個 GeneratorType 只有一個要求，就是生產(chǎn)元素( Elements )
protocol GeneratorType {
typealias Element
mutating func next() -> Element?
}
所以一個數(shù)列就是一個可以提供元素創(chuàng)建器的東西号涯。
最快創(chuàng)建定制數(shù)列的方法就是用AnySequence目胡。這是一個內(nèi)建的結(jié)構(gòu)體，可以響應(yīng)generate()链快，去調(diào)用一個你在初始化時所給的閉包誉己。
struct AnySequence<Element>: SequenceType {
init<G: GeneratorType where G.Element == Element>
(_ makeUnderlyingGenerator: () -> G)
}
類似的，我們可以用 AnyGenerator 和 anyGenerator 函數(shù)來造創(chuàng)建器域蜗。
func anyGenerator<Element>(body: () -> Element?) ->
AnyGenerator<Element>
所以寫一個斐波那契數(shù)列就相當(dāng)簡單了：
let fibonacciNumbers = AnySequence { () -> AnyGenerator<Int> in
// 為了創(chuàng)建一個生成器巨双，我們首先需要建立一些狀態(tài)...
var i = 0
var j = 1
return anyGenerator {
// ... 然后生成器進(jìn)行改變
// 調(diào)用 next() 一次獲取每一項(xiàng)
// (代碼看起來是不是很熟悉？)
(i, j) = (j, i + j)
return i
}
}
現(xiàn)在 fibonacciNumbers 是一個 SequenceType霉祸，我們可以使用 for 循環(huán)：
for f in fibonacciNumbers {
print(f) // 打印 1, 然后打印 1, 繼續(xù)打印 2, 3, 5, 8, 13, 21, 34, 55...
}
而且我們可以自由的使用 prefix:
for f in fibonacciNumbers.prefix(7) {
print(f) // 打印 1, 1, 2, 3, 5, 8, 13, 然后停止.
}
最后我們可以用 reduce 來加起來：
fibonacciNumbers.prefix(7).reduce(0, combine: +) // 返回 33
太棒了筑累！這是線性時間的，常量空間的丝蹭，最重要的是這非常清晰的展示了我們所要做的慢宗，而不需要使用 ... 和 map。
說明：如果你在playground里運(yùn)行這段代碼半夷，可能會發(fā)現(xiàn)這個版本比之前的要慢婆廊。這個版本只改變了常數(shù)部分，復(fù)雜度本身沒有變化巫橄，但是性能卻有明顯下降淘邻。和 fastFibonacciSumUpTo 進(jìn)行對比可以發(fā)現(xiàn)，這段代碼把單一的循環(huán)改成了函數(shù)調(diào)用湘换，這可能就是性能降低的原因宾舅。沒錯统阿，我們又需要進(jìn)行權(quán)衡。
靈活度
目前的目標(biāo)只是給了我們一個更好給工具去解答有關(guān)斐波那契數(shù)的問題筹我。深入鉆研來看扶平，我們可能會問：為什么我要先研究斐波那契數(shù)？這不過是這個數(shù)列恰好符合我們所發(fā)現(xiàn)的規(guī)律：
$$S_{今天} = S_{昨天} + S_{前天}$$
這個公式在我們代碼中表現(xiàn)為 (i, j) = (j, i + j)蔬蕊。但是這深藏了 AnySequence 和 anyGenerator结澄。如果我們要寫更加清晰的代碼 --- 可以描述我們想要解決的問題、不需要仔細(xì)分析 --- 我們最好寫的更加明顯點(diǎn)岸夯。
斐波那契數(shù)列常寫成這種形式：
$$F_{n} = F_{n-1} + F_{n-2}$$
這是類似的形式麻献，但是最重要的是這表現(xiàn)出遞推關(guān)系。這種數(shù)學(xué)關(guān)系指的是數(shù)列里某一個數(shù)的值取決于前面幾個數(shù)的值猜扮。
定義遞推關(guān)系的時候勉吻，首先要定義初始項(xiàng)。我們不能簡單的利用 (i, j) = (j, i + j) 來計算斐波那契數(shù)如果我們不知道什么是 i 什么是 j旅赢。在我們的例子里齿桃，我們的初始項(xiàng)為 i = 0 和 j = 1 —— 或者，我們可以把初始值定為1和1煮盼，因?yàn)槲覀兪堑鹊谝粋€值返回以后才進(jìn)行計算的短纵。
遞推關(guān)系的階數(shù)(order)是指每一步所需的前面項(xiàng)的個數(shù)，而且初始項(xiàng)數(shù)目必須等于階數(shù)（不然的話我們就沒有足夠的信息來計算下一項(xiàng)）孕似。
現(xiàn)在我們可以來設(shè)計API了踩娘！你只需提供初始項(xiàng)和遞推就可以創(chuàng)建遞推關(guān)系了：
struct RecurrenceRelation<Element>
{
/// - Parameter initialTerms: The first terms of the sequence.
/// The `count` of this array is
/// the **order** of the recurrence.
/// - Parameter recurrence:
Produces the `n`th term from the previous terms.
/// - 參數(shù) initialTerms: 序列的第一個元素集合.
/// 數(shù)組的個數(shù)也就代表這個遞推的排序刮刑。
/// - 參數(shù) recurrence：根據(jù)前面的元素推算出第 n 個元素
init(_ initialTerms: [Element], _ recurrence:
(T: UnsafePointer<Element>, n: Int) -> Element)
}
（我們在使用 UnsafePointer<Element> 而不是 [Element]喉祭，這樣我們就可以使用 T[n] 而不需要存儲先前計算的項(xiàng)）。
現(xiàn)在雷绢，我們的初始任務(wù)變得更加簡單了泛烙。多少人在使用Swift？ 只要用這個公式即可：
let peopleWritingSwift = RecurrenceRelation([1, 1])
{ T, n in T[n-1] + T[n-2] }
peopleWritingSwift.prefix(7).reduce(0, combine: +) // 返回 33
那么翘紊，如何來實(shí)現(xiàn)這個API呢?
我們來做吧蔽氨。
struct RecurrenceRelation<Element>: SequenceType, GeneratorType
{
首先我們需要一些內(nèi)存來存儲元素，還需要一個引用來鏈接到我們所要傳遞的閉包帆疟。
private let recurrence: (T: UnsafePointer<Element>, n: Int) -> Element
private var storage: [Element]
/// - 參數(shù) initialTerms: 序列的第一個元素集合.
/// 數(shù)組的個數(shù)也就代表這個遞推的排序鹉究。
/// - 參數(shù) recurrence：根據(jù)前面的元素推算出第 n 個元素
init(_ initialTerms: [Element], _ recurrence: (T: UnsafePointer<Element>, n: Int) -> Element)
{
self.recurrence = recurrence
storage = initialTerms
}
為了簡單點(diǎn)，我們同時采用 SequenceType and GeneratorType踪宠。對于 generate()自赔，我們只返回 self。
// SequenceType requirement
func generate() -> RecurrenceRelation<Element> { return self }
接下來柳琢，每次調(diào)用 next()绍妨，我們調(diào)用 recurrence 來產(chǎn)生下一個值润脸， 并且將其存在 storage 里。
// GeneratorType requirement
private var iteration = 0
mutating func next() -> Element?
{
// 首先推算出所有的初始元素值
if iteration < storage.count { return storage[iteration++] }
let newValue = storage.withUnsafeBufferPointer { buf in
// 調(diào)用閉包他去，傳入內(nèi)存地址中的指針的偏移量毙驯，知道 T[n-1] 是數(shù)組中最后一個元素
return recurrence(T: buf.baseAddress +
storage.count - iteration, n: iteration)
}
// 存儲下一個的值，丟棄到最舊的值
storage.removeAtIndex(0)
storage.append(newValue)
iteration++
return newValue
}
}
更新：@oisdk指出
UnsafePointer不是必須的灾测。在原來的版本中爆价，我使用它是為了讓 n 的值在 recurrence 中更加精確 - 但是自從 recurrence 只依賴與前一項(xiàng)，而不是 n 本身時媳搪，n 的值不再改變時允坚，這是ok的。 所以這個版本運(yùn)行良好蛾号。不使用UnsafePointer感覺更加安全了!
記壮硐睢：有許多種方法可以定義自定義數(shù)列。CollectionType鲜结，SequenceType展运，和 GeneratorType 只是協(xié)議，你可以按照自己所需的方式來遵循它們精刷。也就是說拗胜，在實(shí)踐中也許你很少需要這么做 —— Swift 的標(biāo)準(zhǔn)庫里有大多數(shù)你所需的。不過如果你覺得需要自定義的數(shù)據(jù)結(jié)構(gòu)怒允，你可以使用 CollectionType 和 SequenceType埂软。
更多的例子
現(xiàn)在我們已經(jīng)歸納了遞推關(guān)系，我們可以輕松地計算許多東西了纫事。比如說盧卡斯數(shù)（Lucas Number）勘畔。和斐波那契數(shù)類似，只不過初始項(xiàng)不同：
// 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521...
let lucasNumbers = RecurrenceRelation([2, 1]) { T, n in T[n-1] + T[n-2] }
或者”Tribonacci Numbers“丽惶，一個擁有有趣性質(zhì)的三階遞推：
// 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504...
let tribonacciNumbers = RecurrenceRelation([1, 1, 2])
{ T, n in
T[n-1] + T[n-2] + T[n-3]
}
花一些額外的功夫炫七，我們可以視覺化單峰映像的混沌二根分支。
func logisticMap(r: Double) -> RecurrenceRelation<Double>
{
return RecurrenceRelation([0.5]) { x, n in
r * x[n-1] * (1 - x[n-1])
}
}
for r in stride(from: 2.5, to: 4, by: 0.005) {
var map = logisticMap(r)
for _ in 1...50 { map.next() }
// 處理一些得到的值
Array(map.prefix(10))[Int(arc4random_uniform(10))]
// 隨機(jī)選擇接下來 10 個值當(dāng)中的一個
}
是不是很有數(shù)學(xué)的簡潔性呀钾唬？
相關(guān)推薦
- TED 演講万哪，The magic of Fibonacci numbers, 演講者，Arthur Benjamin.
- Binet's Formula, 使用一個幾乎常量時間的公式來計算斐波那契數(shù)抡秆。
- Arrays, Linked Lists, and Performance奕巍，作者 Airspeed Velocity, 對序列使用其他有意思的方法，包括對ManagedBuffer的討論儒士。
本文由 SwiftGG 翻譯組翻譯的止，已經(jīng)獲得作者翻譯授權(quán)，最新文章請?jiān)L問 http://swift.gg乍桂。
