讀程式設計與類型系統筆記10_泛型算法和疊代器
作者:躺着的柒
讀程式設計與類型系統筆記10_泛型算法和疊代器
1.常用算法
1.1.map()
1.1.1.接受一個T值序列和一個函數(value: T) => U,将該函數應用到序列中的全部元素,然後傳回一個U值序列
1.1.2.别名
1.1.2.1.fmap()
1.1.2.2.select()
1.2.filter()
1.2.1.接受一個T值序列和一個謂詞(value: T) => boolean,并傳回一個T值序列,其中包含謂詞傳回true的所有資料項
1.2.2.别名
1.2.2.1.where()
1.3.reduce()
1.3.1.接受一個T值序列、一個T類型的初始值,以及将兩個T值合并為一個值的操作(x: T, y: T) => T
1.3.2.當使用該操作把序列中的全部元素合并起來後,它傳回一個T值
1.3.3.别名
1.3.3.1.fold()
1.3.3.2.collect()
1.3.3.3.accumulate()
1.3.3.4.aggregate()
1.4.any()
1.4.1.接受一個T值序列和一個謂詞(value: T) => boolean
1.4.2.如果序列中的任何一個元素滿足謂詞,它就傳回true。
1.5.all()
1.5.1.接受一個T值序列和一個謂詞(value: T) => boolean
1.5.2.如果序列的全部元素滿足謂詞,它将傳回true
1.6.none()
1.6.1.接受一個T值序列和一個謂詞(value: T) => boolean
1.6.2.如果序列中沒有元素滿足謂詞,它将傳回true
1.7.take()
1.7.1.接受一個T值序列和一個數字n
1.7.2.它傳回的結果序列由原序列的前n個元素構成
1.7.3.别名
1.7.3.1.limit()
1.8.drop()
1.8.1.接受一個T值序列和一個數字n
1.8.2.它傳回的結果序列包含原序列中除前n個元素之外的所有元素
1.8.2.1.前n個元素将被丢棄
1.8.3.别名
1.8.3.1.skip()
1.9.zip()
1.9.1.接受一個T值序列和一個U值序列
1.9.2.它傳回的結果序列由T和U值對組成,實際上是把兩個序列組合了起來
1.10.其他算法
1.10.1.order()
1.10.2.reverse()
1.10.3.split()
1.10.4.concat()
1.11.庫算法
1.11.1.在Java中,它們包含在java.util.stream包
1.11.2.在C#中,它們包含在System.Linq命名空間中
1.11.3.在C++中,它們包含在标準庫頭檔案中
1.11.3.1.C++現在越來越傾向于使用範圍
1.11.3.2.通過更新算法,使其接受範圍作為實參,并傳回範圍
1.11.4.JavaScript的underscore.js包和lodash包
1.11.5.把大部分循環替換為調用庫算法
1.12.經驗準則
1.12.1.自己在編寫循環時,應該檢查是否有庫算法或者管道能夠完成相同的工作
1.12.1.1.庫算法被高效實作并且經過實踐證明,而且因為能夠明确表達所做的操作,是以我們的代碼也更加容易了解
1.12.2.并不是所有資料結構都支援特化的疊代器
1.12.3.如果确實遇到了使用可用算法無法解決的問題,則應該考慮為解決方案建立一個泛型的、可重用的實作,而不是特定的、一次性的實作
1.13.實作流暢管道
1.13.1.一個流暢的API來把算法連結成管道
1.13.2.流暢的API是基于方法鍊的API,可以使代碼更加容易閱讀
1.13.3.友善地從左到右閱讀,而且我們能夠用一種非常自然的文法,連結任意多個算法來構成管道
1.13.4.缺點
1.13.4.1.包含了所有的算法,是以很難擴充
1.13.4.1.1.C#提供了擴充方法,可以用來向類或接口添加方法,而不必修改其代碼
1.13.4.2.如果它是庫的一部分,那麼調用代碼在不修改類的情況下,很難添加一個新的算法
2.限制類型參數
2.1.限制告訴編譯器某個類型實參必須具有的能力
2.2.一旦要求泛型類型上必須有特定成員,就使用限制将允許類型的集合限制為具有必要成員的那些類型
2.3.哈希集合
2.3.1.類型T需要提供一個哈希函數,該函數接受T類型的一個值,傳回一個數字,即其哈希值
2.3.2.Java的頂層類型Object有一個hashCode()方法
2.3.3.C#的頂層類型Object有一個GetHashCode()方法
3.大O表示法
3.1.當函數的實參趨近于特定值n時,執行該函數需要的時間和空間的上界
3.2.時間上界
3.2.1.時間複雜度
3.2.2.常量時間,或O(1)
3.2.2.1.函數的執行時間不依賴于它需要處理的資料項個數
3.2.2.2.例如:函數first()取出一個序列中的第一個元素
3.2.3.對數時間,或O(logn)
3.2.3.1.函數的輸入在每一步減半,是以即使對于很大的n值,它的效率也很高
3.2.3.2.例如,在排序後的序列中進行二分搜尋
3.2.4.線性時間,或O(n)
3.2.4.1.函數的運作時間與其輸入成比例。周遊一個序列需要的時間是O(n)
3.2.5.二次方時間,或O(n2)
3.2.5.1.其效率比線性時間低得多,因為運作時間的增長比輸入規模的增長快得多
3.2.5.2.序列上的兩個嵌套循環的運作時間為O(n2)
3.2.6.線性代數時間,或O(nlogn)
3.2.6.1.不如線性時間高效,但是比二次方時間高效
3.2.6.2.最高效的比較排序算法是O(nlogn)
3.2.6.3.不能隻使用一個循環排序一個序列,但能夠做到比使用兩個嵌套循環更快
3.3.空間上界
3.3.1.空間複雜度
3.3.2.常量空間,或O(1)
3.3.2.1.在輸入的規模增長時,函數不需要更多空間
3.3.2.2.max()函數需要額外的記憶體來存儲正在計算中的最大值和疊代器,但無論序列有多大,函數需要的記憶體量是固定的
3.3.3.線性空間,或O(n)
3.3.3.1.函數需要的記憶體量與其輸入的規模成比例
3.3.3.2.二叉樹周遊就是這樣一個函數,它将所有結點的值複制到一個數組中,以提供樹的疊代器
4.常用疊代器
4.1.輸入疊代器
4.1.1.能夠周遊序列一次并提供其值的疊代器
4.1.1.1.允許讀取值
4.1.2.不能第二次重放值,因為值可能已經不再可用
4.2.輸出疊代器
4.2.1.能夠周遊一個序列并向其寫入值的疊代器,它并不需要能夠讀出值
4.2.1.1.允許設定值
4.3.前向疊代器
4.3.1.可以向前推進、可以讀取目前位置的值以及更新該值的疊代器
4.3.2.可以被克隆,推進該疊代器不會影響該疊代器的克隆
4.3.3.能夠周遊一個序列任意多次,并修改序列
4.4.雙向疊代器
4.4.1.具有前向疊代器的所有能力,但除此之外,還可以遞減
4.4.2.既可以前向,又可以後向周遊序列
4.4.3.泛型reverse()
4.5.随機通路疊代器
4.5.1.能夠以常量時間向前或向後跳過任意多個元素
4.5.2.能夠實作最高效的算法,提供這種疊代器的資料結構相對較少
4.5.2.1.雙向連結清單不能支援随機通路疊代器
5.自适應算法
5.1.為功能較少的疊代器提供了更加通用的、效率相對較低的實作
5.1.1.一個低效,但是對疊代器要求較低的版本
5.2.為功能較多的疊代器提供了更加高效的、沒那麼通用的實作
5.2.1.一個高效,但是對疊代器要求更高的版本