初探 Swift Sequences 和 Generators

作者:uraimo,原文鏈接羞延,原文日期:2015-11-12
譯者:CoderAFI渣淳;校對:Cee;定稿:numbbbbb

在這篇文章中我們將介紹 Swift 2 自定義序列肴楷,并舉例說明有限序列和無限序列的區(qū)別水由,本文是 Swift and the functional approach 系列其中一篇。

sequences
sequences

你可以訪問 GitHub 或下載 zip 文件來獲取本文示例程序的 playground赛蔫。

SequenceType 標準協(xié)議在官方文檔中被定義為一種簡單的數據類型砂客,該類型可以用 for...in 來循環(huán)遍歷。協(xié)議中最重要的定義是在上半部分:

public protocol SequenceType {
    typealias Generator : GeneratorType
    /// Return a *generator* over the elements of this *sequence*.
    ///
    /// - Complexity: O(1).
    public func generate() -> Self.Generator
    ...
    ...
}

上面的協(xié)議中關聯了另一個 GeneratorType 協(xié)議類型(Swift 讓協(xié)議泛型化的獨特方式)呵恢。當我們要自定義序列的時候鞠值,我們同時也要自定義一個實現這個協(xié)議的生成器,保證我們自定義的 SequenceType 在調用 generate() 方法時能夠返回指定元素類型的生成器渗钉。

序列協(xié)議中提供了許多有意思的方法彤恶,這些方法很多都已經在擴展中實現了钞钙,例如 mapflatmap(深入了解可以參看 map and flatMap)声离、filter芒炼、reducesubsequence functions 等术徊。

這些方法讓 SequenceType 協(xié)議的作用遠遠大于只進行 for each 遍歷本刽。

讓我們來看下 GeneratorType 的定義:

public protocol GeneratorType {
    typealias Element
    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Self.Element?
}

這個簡單的協(xié)議只包含了一個 next() 方法,該方法用來返回生成器管理的下一個元素赠涮。至關重要的一點是子寓,當序列遍歷到最后時,生成器應該返回 nil笋除。接下來當我們構造一個無限序列的時候斜友,來看看為什么這里要返回 nil

首先垃它,我們來寫一個簡單的斐波那契數序列生成器:

class FibonacciGenerator : GeneratorType {
    var last = (0,1)
    var endAt:Int
    var lastIteration = 0

    init(end:Int){
        endAt = end
    }

    func next() -> Int?{
        guard lastIteration<endAt else {
            return nil
        }
        lastIteration++

        let next = last.0
        last = (last.1,last.0+last.1)
        return next
    }
}

為了定義一個有限序列鲜屏,我們需要一個自定義構造函數來指定一個序列長度。當到達這個長度時 next() 方法就返回 nil国拇。這里我們用元組(Tuple)實現起來會節(jié)省很多代碼量墙歪,讓我們看下如何使用這個生成器:

var fg = FibonacciGenerator(end:10)

while let fib = fg.next() {
    print(fib)
}

用這種方式我們就可以遍歷生成器中的元素,直到生成器返回 nil贝奇。

根據這個生成器實現一個 SequenceType 輕而易舉。

class FibonacciSequence : SequenceType {
    var endAt:Int

    init(end:Int){
        endAt = end
    }

    func generate() -> FibonacciGenerator{
        return FibonacciGenerator(end: endAt)
    }
}

let arr = Array(FibonacciSequence(end:10))

for f in FibonacciSequence(end: 10) {
    print(f)
}

上面的序列正如預期那樣靠胜,可以在 foreach 遍歷中使用掉瞳,同樣也可以用來生成其他類型的序列,比如數組浪漠。

其實我們沒有必要單獨定義一種生成器類型陕习,我們可以用 anyGenerator 工具方法和 AnyGenerator<T> 類來降低序列定義的耦合性:

class CompactFibonacciSequence : SequenceType {
    var endAt:Int

    init(end:Int){
        endAt = end
    }

    func generate() -> AnyGenerator<Int> {
        var last = (0,1)
        var lastIteration = 0

        return anyGenerator({
            guard lastIteration<self.endAt else {
                return nil
            }
            lastIteration++

            let next = last.0
            last = (last.1,last.0+last.1)
            return next
        })
    }
}

這種定義方式跟上面序列的最終效果是一樣的。唯一的區(qū)別就是 generate 方法返回了 AnyGenerator<Int> 類型址愿。它已經不是我們開始的時候定義的簡單生成器類型该镣。

這種做法在這里看起來可能沒太大用處,但是在很多情況下响谓,相較于讓一個生成器嵌入一個序列集合中损合,用一個簡單 anyGenerator() 方法來生成的序列更具擴展性。

例如娘纷,我們用 Lucas 序列的前 10 個數來創(chuàng)建一個序列嫁审。Lucas 序列與斐波那契序列非常相似,不同之處是斐波那契序列以 0赖晶,1 開頭而 Lucas 序列以 2律适,1 開頭,所以當然最終會生成截然不同的序列,例如:2捂贿,1纠修,3,4厂僧,7扣草,11,18吁系,29...下面我們只定義一個生成器德召,并用它來初始化一個數組。

var last = (2,1)
var c = 0

let lucas = anyGenerator{
    ()->Int? in
    guard c<10 else {
        return nil
    }

    c++
    let next = last.0
    last = (last.1,last.0+last.1)
    return next
}

let a = Array(lucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

看起來不錯汽纤,我們刪除了一些無用的代碼上岗,我們也可以擴展我們的算法,讓它返回一個黃金分割比蕴坪,讓我們試試:

import Darwin

let Phi = (sqrt(5)+1.0)/2
let phi = 1/Phi

func luc(n:Int)->Int {
    return Int(pow(Phi, Double(n))+pow(-phi,Double(n)))
}

c = 0
var compactLucas = anyGenerator{ c<10 ? luc(c++): nil }

let a2 = Array(compactLucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

這樣確實行得通嗎肴掷?當然,你可以下載 playground打包的 zip 文件來驗證背传。

為了嘗試 SequenceType 提供的一些特性方法呆瞻。我們構建一個只返回偶數的 Lucas 數字序列:

c = 0
var evenCompactLucas = anyGenerator{ c<10 ? luc(c++): nil }.filter({$0 % 2 == 0})
let a3 = Array(evenCompactLucas) //[2, 4, 18, 76]

注意,這里我們其實是重新定義了 AnyGenerator径玖,由于前面的序列是有限的痴脾,當遍歷到最后時,就會產生另一個有限的序列梳星。這從另一方面也可以說明赞赖,我們很容易就能改變原有序列,返回一組新的數據集冤灾。我們也可以用 map 方法來做一些更直接的轉換前域。

無限序列

現在,我們移除 nil 的返回值限制韵吨,這樣就能根據 Lucas 算法生成一個無限序列匿垄。

c = 0
var infiniteLucas = anyGenerator{luc(c++)}

可見,將一個有限序列轉換成無限序列是非常容易的」榉郏現在我們生成了一個沒有數量限制的新序列椿疗。但是我們需要另外一種方式來限制序列元素數,從而讓無限序列元素數更可控盏浇。

幸運的是 SequenceType 協(xié)議提供了一個方法來解決這個問題:

let a4 = Array(infiniteLucas.prefix(10)) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

for var f in infiniteLucas.prefix(10){
    print(f)
}

這種方式將會從當前序列篩選出 10 個元素并添加到一個新的序列中变丧,而且新序列使用起來跟前面的無限序列是一樣的。

讓我們進一步來看一下 filter 方法的用法绢掰,看看怎么樣用它來獲取 Lucas 偶數痒蓬。

var onlyEvenLucas = infiniteLucas.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
    print(f)
}

然而童擎,上面的代碼并不會像預期那樣工作。

如果是在 playground 運行攻晒,在聲明 onlyEventLucas 時你會看到高亮報錯顾复。如果是在應用程序中寫了這段代碼,你的應用程序會崩潰鲁捏。

要了解問題的原因芯砸,必須要了解 filter 函數的工作原理。 當對一個序列進行 filter 操作時给梅,我們
必須要把序列的所有元素都獲取到假丧,但是如果沒有 nil 限制,序列元素是無限的动羽,就無法確認元素的遍歷操作什么時候結束包帚。

讓我們在每次從生成器獲取元素時都打印一段文本,來更形象的看下原因:

class InfiniteSequence :SequenceType {
    func generate() -> AnyGenerator<Int> {
        var i = 0
        return anyGenerator({
            print("# Returning "+String(i))
            return i++
        })
    }
}

var fs = InfiniteSequence().filter({$0 % 2 == 0}).generate()

for i in 1...5 {
    print(fs.next())
}

如果你運行這段代碼运吓,會發(fā)現在 InfiniteSequence 上的過濾處理一直在運行渴邦,直到一段時間后處理器無法再繼續(xù)運行,程序就崩潰了拘哨。

幸運的是谋梭,解決上面的問題也很容易。我們只需要延遲計算(Lazily evaluate)這個無限的 Lucas 序列:

var onlyEvenLucas = infiniteLucas.lazy.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
    print(f)
}

使用無限序列的 .lazy 屬性就能獲取一個新的 LazySequenceType 類型倦青,該類型會讓 map瓮床、flatmapreduce 或者 filter 這些方法延遲執(zhí)行产镐,也就是說真正的計算會等到例如 next 這樣的終端操作(Terminal Operation)(其他語言是這么叫的)執(zhí)行時才會被執(zhí)行纤垂。

讓無限序列支持延遲計算是一個必要步驟,默認情況下 Swift 的序列不能延遲計算(該特性是在 Swift 1.0 發(fā)布的)磷账。具體你可以通過官方文檔來詳細了解如何自定義一個 LazySequence(大多數情況可能是解決問題的最好辦法),我也會就該內容進行講解贾虽,敬請期待逃糟。

本文由 SwiftGG 翻譯組翻譯,已經獲得作者翻譯授權蓬豁,最新文章請訪問 http://swift.gg绰咽。

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市地粪,隨后出現的幾起案子取募,更是在濱河造成了極大的恐慌,老刑警劉巖蟆技,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件玩敏,死亡現場離奇詭異斗忌,居然都是意外死亡,警方通過查閱死者的電腦和手機旺聚,發(fā)現死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進店門织阳,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人砰粹,你說我怎么就攤上這事唧躲。” “怎么了碱璃?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵弄痹,是天一觀的道長。 經常有香客問我嵌器,道長肛真,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任嘴秸,我火速辦了婚禮毁欣,結果婚禮上,老公的妹妹穿的比我還像新娘岳掐。我一直安慰自己凭疮,他們只是感情好,可當我...
    茶點故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布串述。 她就那樣靜靜地躺著执解,像睡著了一般。 火紅的嫁衣襯著肌膚如雪纲酗。 梳的紋絲不亂的頭發(fā)上衰腌,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天,我揣著相機與錄音觅赊,去河邊找鬼右蕊。 笑死,一個胖子當著我的面吹牛吮螺,可吹牛的內容都是我干的饶囚。 我是一名探鬼主播,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼鸠补,長吁一口氣:“原來是場噩夢啊……” “哼萝风!你這毒婦竟也來了?” 一聲冷哼從身側響起紫岩,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤规惰,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后泉蝌,有當地人在樹林里發(fā)現了一具尸體歇万,經...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡揩晴,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現自己被綠了堕花。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片文狱。...
    茶點故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖缘挽,靈堂內的尸體忽然破棺而出瞄崇,到底是詐尸還是另有隱情,我是刑警寧澤壕曼,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布苏研,位于F島的核電站,受9級特大地震影響腮郊,放射性物質發(fā)生泄漏摹蘑。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一轧飞、第九天 我趴在偏房一處隱蔽的房頂上張望衅鹿。 院中可真熱鬧,春花似錦过咬、人聲如沸大渤。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽泵三。三九已至,卻和暖如春衔掸,著一層夾襖步出監(jiān)牢的瞬間烫幕,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工敞映, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留较曼,地道東北人。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓振愿,卻偏偏與公主長得像诗芜,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子埃疫,可洞房花燭夜當晚...
    茶點故事閱讀 45,781評論 2 361

推薦閱讀更多精彩內容

  • Spring Cloud為開發(fā)人員提供了快速構建分布式系統(tǒng)中一些常見模式的工具(例如配置管理,服務發(fā)現孩哑,斷路器栓霜,智...
    卡卡羅2017閱讀 134,715評論 18 139
  • 我們在學習web前端的路程起步時總是疑問胳蛮,我們如何更好的遍歷元素呢销凑?迭代器和生成器是什么?今天為大家?guī)吓c精彩的E...
    儂姝沁兒閱讀 3,343評論 0 6
  • 你不知道JS:異步 第四章:生成器(Generators) 在第二章仅炊,我們明確了采用回調表示異步流的兩個關鍵缺點:...
    purple_force閱讀 968評論 0 2
  • 來不及彷徨抚垄, 來不及懷念蜕窿, 2015已完美落幕。 我只能重新走上舞臺拉開帷幕呆馁, 微笑著說桐经,你好,2016浙滤! 我還年...
    高安藝閱讀 127評論 0 0
  • sqlite3SQL語句的特點 不區(qū)分大小寫(比如數據庫認為user和UsEr是一樣的)每條語句都必須以分號 “...
    光明程輝閱讀 4,257評論 4 23