讀編程與類型系統筆記10_泛型演算法和迭代器

来源:https://www.cnblogs.com/lying7/archive/2023/01/18/17059141.html
-Advertisement-
Play Games

隨著電腦系統的規模越來越大,業務量的迅速提升和互聯網的爆炸式增長,集中式系統採用大型主機單機部署帶來了一系列問題:系統大而複雜、難於維護、發生單點故障引起雪崩、擴展性差等。這些都使業務面臨巨大的壓力和嚴重的風險,為瞭解決集中式系統架構面臨的痛點,分散式系統架構逐步走上舞臺。分散式系統是一個硬體或軟... ...


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


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • GreatSQL社區原創內容未經授權不得隨意使用,轉載請聯繫小編並註明來源。 GreatSQL是MySQL的國產分支版本,使用上與MySQL一致。 作者: 葉金榮 文章來源:GreatSQL社區原創 如何快速臨時禁止某賬戶登入 角色ROLES管理需要先激活 關於授權的其他幾點補充 如何複製/復用賬戶 ...
  • GreatSQL社區原創內容未經授權不得隨意使用,轉載請聯繫小編並註明來源。 GreatSQL是MySQL的國產分支版本,使用上與MySQL一致。 作者: JennyYu 文章來源:GreatSQL社區原創 前言 兩表使用nest loop(以下簡稱NL)方式進行連接,小表驅動大表效率高,這似乎是大 ...
  • 摘要:華為雲EI DTSE技術佈道師王躍,針對統計信息對於查詢優化器的重要性,GaussDB(DWS)最新版本的analyze當前能力,與開發者和伙伴朋友們展開交流互動,幫助開發者快速上手使用統計信息的自動收集功能。 在本期《統計信息大揭秘——SQL執行優化之密鑰》的主題直播中,我們邀請到華為雲EI ...
  • 摘要:近日,中國信息通信研究院(簡稱“中國信通院”)公佈了第十五批“可信資料庫”評測結果。華為雲GaussDB(for MySQL)憑藉過硬的技術實力順利通過“HTAP資料庫基礎能力評測”。 本文分享自華為雲社區《華為雲GaussDB(for MySQL)通過中國信通院“可信資料庫”評測》,作者:G ...
  • 彙總數據 聚集函數 聚集函數(aggregate function) 運行在行組上,計算和返回單個值的函數。 | 函 數 | 說 明 | | : | : | | AVG() | 返回某列的平均值 | | COUNT() | 返回某列的行數 | | MAX() | 返回某列的最大值 | | MIN() ...
  • 摘要:斯坦福教授、Tcl語言發明者John Ousterhout的著作《A Philosophy of Software Design》提出了一個經久不衰的觀點——軟體設計的核心在於降低複雜性。 在新技術不斷涌現的雲時代,出現了一種“技術過載”現象——本應幫助企業提高效率的技術,反倒讓企業心生焦慮, ...
  • 以前寫過一篇在Linux上從零開始部署前後端分離的Vue+Spring boot項目,但那時候是部署自己的個人項目,磕磕絆絆地把問題解決了,後來在公司有了幾次應用到實際生產環境的經驗,發現還有很多可以補充的地方,很多指令和下載地址每次用到的時候再找就相對麻煩,通過這篇文章可以做一個記錄。 另外,之前 ...
  • 2023-01-18 一、Tomcat中的結點 1、Server(伺服器) Server代表整個Tomcat伺服器,一個tomcat只有一個Server Server中包含至少一個Service組件,用於提供具體服務。 2、Service Service中的一個邏輯功能層,一個Server可以包含多 ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 1. 講故事 年前遇到了好幾例托管堆被損壞的案例,有些運氣好一些,從被破壞的托管堆記憶體現場能觀測出大概是什麼問題,但更多的情況下是無法做出準確判斷的,原因就在於生成的dump是第二現場,借用之前文章的一張圖,大家可以理解一下。 為了幫助更多受此問題困擾的朋友,這篇來整理一下如何 快狠準 的 ...
  • 前言 .NET6 開始,.NET Croe API 項目取消了 Startup.cs 文件,在 Program.cs 文件的 Main 函數中完成服務的註冊和中間件管道的管理。但當我們項目引入更多包的時候,Program.cs 文件也會看起來很臃腫。 而且,我們不只會有一個後端項目,為了方便快速創建 ...
  • 目錄 背景 get 與 post 的區別 所有介面都用 post 請求? 背景 最近在逛知乎的時候發現一個有趣的問題:公司規定所有介面都用 post 請求,這是為什麼? 看到這個問題的時候其實我也挺有感觸的,因為我也曾經這樣問過我自己。在上上一家公司的時候接到一個項目是從零開始搭建一個微服務,當時就 ...
  • *以下內容為本人的學習筆記,如需要轉載,請聲明原文鏈接 微信公眾號「englyf」https://mp.weixin.qq.com/s/2GFLTstDC7w6u3fTJxflNA 本文大概 1685 個字,閱讀需花 6 分鐘內容不多, 但也花了一些精力如要交流, 歡迎關註我然後評論區留言 謝謝你的 ...
  • 在新版本的pandas中,上述代碼會引起警告,建議改成SQLAlchemy connectable(engine/connection),後續代碼將引入這種升級的連接方式。 ...
  • 幾乎所有的高級編程語言都有自己的垃圾回收機制,開發者不需要關註記憶體的申請與釋放,Python 也不例外。Python 官方團隊的文章 https://devguide.python.org/internals/garbage-collector 詳細介紹了 Python 中的垃圾回收演算法,本文是這篇 ...
  • 如果您想查找高於或低於平均值的數字,可以不必計算該平均值,就能查看更高或更低的值。通過Java應用程式,可以自動突出顯示這些數字。除了快速突出顯示高於或低於平均值的值外,您還可以查看高於或低於的值的個數。現在讓我們看看如何在 Java應用程式中實現此操作。 引入jar包 導入方法1: 手動引入。將  ...
  • 第一種方式:使用{} firstDict = {"name": "wang yuan wai ", "age" : 25} 說明:{}為創建一個空的字典對象 第二種方式:使用fromkeys()方法 second_dict = dict.fromkeys(("name", "age")) #valu ...
  • 在golang中可以使用a := b這種方式將b賦值給a,只有當b能進行深拷貝時a與b才不會互相影響,否則就需要進行更為複雜的深拷貝。 下麵就是Go賦值操作的一個說明: Go語言中所有賦值操作都是值傳遞,如果結構中不含指針,則直接賦值就是深度拷貝;如果結構中含有指針(包括自定義指針,以及切片,map ...
  • 本文結合京東監控埋點場景,對解決樣板代碼的技術選型方案進行分析,給出最終解決方案後,結合理論和實踐進一步展開。通過關註文中的技術分析過程和技術場景,讀者可收穫一種樣板代碼思想過程和解決思路,並對Java編譯器底層有初步瞭解。 ...