讀程式設計與類型系統筆記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.一個高效，但是對疊代器要求更高的版本