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. 一個高效，但是對迭代器要求更高的版本

標籤：設計模式

上一篇：學習筆記——Tomcat中的結點（Server、Service、Connector、Container、Engine、Host、Context）；Tomcat啟動-startup.bat

下一篇：從0到1詳解ZooKeeper的應用場景及架構