[演算法1-排序](.NET源碼學習)& LINQ & Lambda

来源:https://www.cnblogs.com/PaperHammer/archive/2022/08/08/16562690.html
-Advertisement-
Play Games

[演算法1-排序](.NET源碼學習)& LINQ & Lambda 說起排序演算法,在日常實際開發中我們基本不在意這些事情,有API不用不是沒事找事嘛。但必要的基礎還是需要瞭解掌握。 排序的目的是為了讓無序的數據,變得“有序”。此處的有序指的是,滿足當前使用需求的順序,除了自帶的API,我們還可以自定 ...


[演算法1-排序](.NET源碼學習)& LINQ & Lambda

說起排序演算法,在日常實際開發中我們基本不在意這些事情,有API不用不是沒事找事嘛。但必要的基礎還是需要瞭解掌握。

排序的目的是為了讓無序的數據,變得“有序”。此處的有序指的是,滿足當前使用需求的順序,除了自帶的API,我們還可以自定義比較器對象、使用LINQ語句、Lambda表達式等方式完成排序。本文將逐一介紹十大排序,並著重介紹分析基於C#的LINQ常用語句和Lambda表達式,二者對排序的實現。

【# 請先閱讀註意事項】

【註:(1)以下提到的複雜度僅為演算法本身,不計入演算法之外的部分(如,待排序數組的空間占用)且時間複雜度為平均時間複雜度

   (2)除特殊標識外,測試環境與代碼均為.NET 6/C#

   (3)預設情況下,所有解釋與用例的目標數據均為升序

   (4)預設情況下,圖片與文字的關係:圖片下方,是該幅圖片的解釋

   (5)本文篇幅較長,和主標題(排序)契合度較低,建議分期閱讀;也可能存在較多錯誤,歡迎指出並提出意見,請見諒】

一. 十大排序

這十大排序對於有基礎的程式員並不陌生,只是一些經常不用的小細節可能記憶模糊,該部分內容會對排序方法簡要分析,旨在作為筆記,需要的時候幫助回憶相關內容。

(一) 冒泡排序(BubbleSort)

名字的起源十分生動形象:氣泡從水底向上浮,隨氣壓變化氣泡體積逐漸變大最終破裂;在某一時刻讓時間靜止,可觀察到從水面到水底,氣泡體積依次減小,體積排列有序,故得此名。

1. 原理:兩兩比較,按照比較器對象進行交換。

2. 複雜度:時間O(n2)    空間O(1)

3. 實現:(C++14 GCC 9)

(指針形式)

 

(二) 選擇排序(SelectSort)

1.  原理:選擇——選定一個數,確定當前該數的位置後,再選擇下一個數。註意其和冒泡排序的區別。

2.  複雜度:時間O(n2)    空間O(1)

3.  實現:(C++14 GCC 9)

 

二者區別在於:冒泡是相鄰的數比較;選擇是每次固定一個數與其他數比較。

(三) 插入排序(InsertSort)

其操作方式類似於我們再打牌時,抽出一些牌放入合適的位置。

1.     原理:選定一個數,將該數插入合適的位置。即,若排序結果為升序,則將數b插入某一位置,使得a < b < c。

2.     複雜度:時間O(n2)    空間O(1)

3.     實現:(C++14 GCC 9)

(四) 希爾排序(ShellSort)

此排序由希爾提出,是對插入排序的改進。改進的思想是:將一整個待排序序列分割為多個組,每一次對每個組的同一位置進行插入排序。即,將第一、二、三…組的第一個元素看為一個新的序列進行插排,第二個元素看為一個新的序列進行插排……以此類推。實驗證明,該思想在一定程度上有助於加快插入排序的運行。

1.     原理:分割式插排

2.     複雜度:時間O(n1.3)    空間O(1)

3.     實現:(C++14 GCC 9)

大量數據表明,當h /= 3時可達到最優效果。

(五) 快速排序(QuickSort)

快速排序是最常用的一個排序,在之前的介紹.NET數組源碼的排序方法([數據結構-線性表1.1] 數組 (.NET源碼學習))中也出現過,雖然其內部有三種排序方式,但主體還是快速排序。之所以稱之為快速,是因為其時間複雜度不再是n2級,而是nlog2n級。一般地,在1s的時間範圍內,總時間複雜級數需要小於等於108,快速排序的出現,解決了許多大量數據排序的問題,提高了不少效率。

1.     原理:類二分法

2.     複雜度:時間O(nlog2n)    空間O(log2n)

3.     實現:(C++14 GCC 9)

快速排序只是使用數組原本的空間進行排序,所以所占用的空間應該是常量級的,但是由於每次劃分之後是遞歸調用,遞歸在運行的過程中會在棧上消耗一定的空間,在一般情況下的空間複雜度為O(logn),在最差的情況下,若每次只完成了一個元素,那麼空間複雜度為O(n)。

[# Array.Sort()源碼再讀—有關快速排序]

這是該方法中的快速排序,和我們一般的快速排序不同,其運用了SwapIfGreater()方法、三數取中法對快速排序進行了優化。

  • Line 197:此處的num為數組長度。
  • l  Line 198:num >> 1 相當於 num / 2,一般地,可視為中間位置索引值。
  • l  Line 199~201:SwapIfGreater()方法

根據傳入的比較器對象,對兩個元素進行相應處理。

在排序前,其先把索引為0和mid的兩個元素、索引為0的元素和最後一個元素、索引為mid的元素和最後一個元素進行處理,優先保證這三個位置上的元素符合要求。

該方法即為三數取中法

1.     方法:是知道無序數列的首和尾,便可以求出其中間位置的數,此時只需在首、中、尾這三個數中,選擇中間的這個數作為基準值,進行快速排序,即可進一步提高快速排序的效率。

最初的快速排序是選擇第一個或最後一個元素為基準值,然後將整個序列分為兩部分。但當數組本身有序度較高完全有序時,快排會達到O(n2)的時間複雜度,因為可能會導致分完後的兩部分中,某一部分為空集。即,相當於沒有二分就開始排序。

2.     優化原理:將首、中、尾排序後,選取中間位置的元素,能有效避免“一邊倒”的問題,從而真正利用上二分思想的加速性。

  • Line 202:t 即為基準值。
  • Line 203:交換中間位置和末尾的元素。使得這三個元素大小變成“峰谷”狀,由於基準值是三個元素中間大小的一個,這樣相當於保證分成的兩部分不出現空集。

該源碼和本人寫的代碼格式不同,本人運用遞歸的方法,將序列無限二分至無法再分,先左後右逐步有序;源碼利用迭代方法,三數取中 + 雙向搜索,從整體到局部。雖然平均複雜度均為log級,但長遠看來源碼具有較高的優越性。

  • Line 206~218:從兩端開始,以中間位置為中心、基準值為判斷依據開始交換。

當最外層while迴圈結束後,i的左側一定全都是小於基準值的元素,num3的右側一定全都是大於基準值的元素。此時,相對於基準值而言,i的左側是有序的,num3的右側是有序的。

  • Line 220~223:將i位置的元素與末尾元素交換。此時i位置的元素,是大於等於末尾元素的。交換後,從開頭到i位置的元素相對於剛纔而言,更加有序。

 

上圖是本人手寫的一份基本流程草圖,該快速排序有別於一般形式的快速排序,但整體思想依舊不變:類二分法,從子集有序到整體有序,加上兩種方法的優化,效率已經是很高的了。

(六) 歸併排序

歸併,即合併,既然要合併,那之前就得拆開。所以,歸併排序的方法就是先把元素二分,二分後每段再二分,直到無法二分。再根據比較器對象,按一定順序合二為一,逐層回調,最後完成排序。

1.     原理:類二分法

2.     複雜度:時間O(nlog2n)    空間O(n)

3.     實現:(C++14 GCC 9)

快速排序是先排序,使得整個序列以基準值有序,再二分;歸併排序是直接二分到底,再逐層往回排序,從局部到整體

(七) 堆排序

堆的結構類似於二叉樹,而二叉樹的相關操作(如,查詢、插入、刪除等)的時間複雜度一般都在常數級和log級,所以堆排序的效率也比較高。

1.     原理:根據數組索引和二叉樹位置的關係,構建大/小頂堆(二叉樹)並還原。

2.     複雜度:時間O(nlog2n)    空間O(1)

3.     實現:(C++14 GCC 9)

一般地,目標為升序數組則構建大頂堆,目標為降序數組則構建小頂堆。

[# Array.Sort()源碼再讀—有關堆排序]

該源碼與一般的堆排序寫法如出一轍,上方的HeapSort()方法用於控制每次調整堆的範圍,保證有序元素不再被調整;下方的DownHeap()方法用於構建/調整堆,將合適的元素放到合適的位置。

  • Line 231~234:第一次構建堆,構建大頂堆。即,讓每一個父結點的值大於等於子結點的值。
  • Line 235~239:調整堆。每次調整後,根節點總是最大的,所以將根節點與最後一個非調整好的結點(從右下角開始往前)進行交換,交換後靠近末尾的部分元素已經是有序的了,所以下一次調整堆頂時,應將其排除在外,這就是參數中j – 1的由來。
  • Line 243:參數:keys為待排序元素集;i為排序起始位置的索引(由於第一次構建堆頂時,保證了父結點的值大於等於子結點的值,所以交換後0索引處的值一定是較小的值,且該位置是一個動態存儲域,所以調整的其實索引可以從1開始,這就是傳入值為1的原因);n為排序結束的索引;lo為應當進行交換的元素的索引(堆排序在建好堆後,一般從最後一個非葉子結點開始進行判斷。即,從最後一個分支,倒著往前進行。對於數組索引即為2 * 起始索引 + 1);

之後的過程和本人以C++語言所寫的過程大體相似。

(八) 計數排序、桶排序

理論上這兩者排序的思想是類似的:新建數組,以索引代表元素,統計每個元素出現次數,最後再輸出。

1.     原理:按索引順序,以索引值代表數組值,統計出現次數。

2.     複雜度:時間O(n + k)    空間O(n + k)(其中,k為max – min)

3.     實現:(C++14 GCC 9)

當然,從標準出發,這二者肯定是不一樣的。

對於桶排序,將待排序元素劃分到不同的痛。先掃描一遍序列求出max和min ,設桶的個數為 k ,則把區間 [min, max] 均勻劃分成 k 個區間,每個區間就是一個桶,將序列中的元素分配到各自的桶。

對於計數排序,每個數值為一個桶。計數排序本質上是一種特殊的桶排序,當桶排序的桶的個數最大的時候,就是計數排序。

(九) 基數排序

1.     原理:按照元素的每一位進行比較來排序。

2.     複雜度:時間O(n * k)    空間O(n + k) (其中,k為max – min)

3.     實現:(C++)來自(1.10 基數排序 | 菜鳥教程 (runoob.com)

 

小結一

基數排序與計數排序、桶排序這三種排序演算法都利用了桶的概念,但對桶的使用上有一定差異:

(1)桶排序:每個桶存儲一定範圍的數值;

(2)計數排序:每個桶只存儲單一鍵值;

(3)基數排序:根據鍵值的每位數字來分配桶;

基數排序不是直接根據元素整體的大小進行元素比較,而是將原始列表元素分成多個部分,對每一部分按一定的規則進行排序,進而形成最終的有序列表。

LINQ語句及常用方法

LINQ(Language-Integrated Query)語言集成查詢,常用於對數據的查詢。一般地,完整的查詢操作包括創建數據源、定義查詢表達式和在foreach語句中執行查詢。

該部分將分析相關方法的源碼,以及內部的orerby與orderbyDescending排序方法。本人會儘可能的講述清楚過程的細節,但之前也沒有詳細讀過源碼,該文章也是邊讀邊學邊寫,可能存在解讀錯誤,也可能會有與讀者相矛盾的觀點,還望各位指出,請諒解。

(一) All()方法

確定序列的所有元素是否都滿足條件。

  • Line 10:LINQ方法中的參數並不像一般方法中的參數一樣,各個對應。
  • Line 12~15:檢查源數據是否為空,防止訪問沒有分配引用地址的對象。
  • Line 16~19:檢查過濾器對象是否為空。
  • Line 20~27:對每個元素根據傳入的委托表達式進行判斷。

對於這兩個參數,可以發現:

(一) 不管是在源碼還是在從元數據中,該方法均有兩個參數。但在使用時,卻只需要傳入一個參數。

(二) TSource和泛型T不是一個東西,泛型T可以容納所有類型,但需要手動指定數據類型;TSource可以容納所有類型,但可自動識別類型

當要訪問的元素集是什麼類型時,TSource會自動分配對應的類型。

(三) 待傳入的參數Func<TSource, bool> predicate是一個方法(稱為此處過濾器),將方法作為參數,無疑用到了委托。

關鍵字in和out一般用在泛型interface和delegate中, 用來進行逆變和協變(in逆變,out協變)。(協變、逆變將在下方介紹

Func()方法是一個有返回值的泛型委托,可包含0~16個參數T,併在最後多加一個參數,表示返回值類型。我們也可以自己定義該方法,如:

根據我們自己寫的調用的操作步驟,可以發現,我們只需傳入待處理參數,不用管最後的返回參數。

 

其基本語法格式為:方法名(臨時變數 => 條件表達式)。其中,括弧中的式子稱為Lambda表達式,會在後文介紹。

(二) Any()方法

判斷是否包含任何元素、是否存在元素滿足指定的條件。

(1)首先是判斷源數據是否包含任何元素。

  • Line 15~29:嘗試將source轉換為集合(介面)類型,若轉換成功,即序列可以作為ICllection<>的實例,則通過返回Count屬性,判斷其是否包含任何的元素。
  • Line 20~35:嘗試將source轉換為IListProvider(介面)類型,若轉換成功,則調用GetCount()方法,預設傳入true,進行判斷;而否則嘗試轉換為集合類型。
  • Line 37~42:提取source的迭代器對象,判斷其是否存在下一個元素,如果枚舉數已成功地推進到下一個元素,返回true;如果枚舉數傳遞到集合的末尾,返回false。

對於IListProvider,其內部包含了三個方法:轉換為數組、轉換為泛型集合、GetCount()方法。

其中,前兩個方法的實現均是將元素放入到新的數據結構中,最後返回。內部的欄位_source[]指的是源數據及,_predicate()方法指的是傳入的條件表達式;LargeArrayBuilder可以近似看作StringBuilder。

對於GetCount()方法,其原理也是通過遍歷源數據集,在滿足相應條件的情況下記錄元素個數。

(2)判斷源數據是否包含任意一個符合條件的元素

通過遍歷的方式逐一檢查,存在一個滿足條件就返回true,一個都不滿足就返回false;

(三) 基本計算--Count()、Max()、Min()、Sum()方法

(1)Count()方法

其包含兩個重載形式:一個是純計數,另一個是帶條件計數(記錄滿足條件的元素個數)。

可以發現,其原理和Any()方法中的GetCount()方法基本類似。

(2)Max()、Min()、Sum()方法

這三種方法,前兩種每種包含21個重載函數,Sum()方法包含19個重載函數,因為需要針對不同的數據類型。但最大不同依舊在於是否帶有條件。

其實現原理基本類似,且沒有什麼新的東西,所以在此不做過多論述。

(四) Where的實現

Where子句用在查詢表達式中,用於指定將在查詢表達式中返回數據源中的哪些元素。它將一個布爾條件應用於每個源元素(由範圍變數引用),並返回滿足指定條件的元素。一個查詢表達式可以包含多個Where子句,一個子句可以包含多個條件表達式。簡而言之,Where起到一個篩選器的作用,篩選出符合條件的元素。

並且可以發現,篩選出的元素預設情況下共同構成一個可枚舉的集合

Where方法的過濾功能主要通過迭代器實現,其源代碼包含7個迭代器。按照功能劃分如下:

(1)索引參與過濾操作運算的迭代器WhereIterator,容器(可迭代對象)包含Enmuerable,List和Array。

(2)索引不參與過濾運算

  1. Enmuerable:WhereEnumerableIterator和WhereSelectEnumerableIterator

  2. List:WhereListIterator和WhereSelectListIterator

  3. Array:WhereArrayIterator和WhereSelectArrayIterator

其中Enmuerable迭代器,List迭代器和Array迭代器在實現上相差不大,都是通過設計模式中的迭代器模式實現具體的功能。區別是Enmuerable迭代器,List迭代器都是調用容器自身的迭代器實現逐個元素的比較和過濾,而Array迭代器是通過數組索引操作實現元素比較和過濾。

除了WhereIterator,其餘六個迭代器均派生自迭代器類Iterator

[# 有關Iterator的源碼]

  • Line 12:在構造函數內獲取當前線程的Id。
  • Line 21:Current屬性包含一個get訪問器(只讀),返回當前對象。
  •  Line 26:該類繼承了介面IEnumerable,所以必須實現GetEnumerator()方法。如果當前迭代器的線程Id和當前線程的Id不同,則克隆一個新的迭代器返回,否則返回當前迭代器。
  • Line 29:該類繼承了介面IDisposable,所以必須實現Dispose()方法。必要情況下釋放對象。
  • Line 36~40:因為需要進行篩選(迭代器遍歷)工作,所以需要定義迭代器,並將其初始狀態設置為1,返回當前迭代器。
  • Line 44:該方法MoveNext()來自於所繼承的介面IEnumerator,其根據不同的容器,有不同的實現(就像剛纔提到的List和Array的迭代方式),所以定義為抽象方法。

  • Line 47~50:虛方法Select(),預設返回WhereEnumerableIterator迭代器。
  • Line 53~56:虛方法Where(),預設返回WhereSelectEnumerableIterator迭代器。

這兩個迭代器均不參與過濾運算,兩個虛方法主要用於具體容器的復用或重寫。如果調用Where的迭代器,屬於剛纔提到的不參與過濾運算的六個迭代器對象,則會覆蓋父類中的某些方法;如果是其它迭代器,例如Distinct迭代器,則會調用父類的Where和Select方法。

Where擴展方法(一)

  • Line 12~19:檢查數據源和過濾器是否為空。
  • Line 20:嘗試將source轉換為迭代器對象,會產生兩種情況:

(1)如果是Where相關的迭代器,如調用形式為XX.Where().Where()。此處iterator.Where(predicate)的Iterator是Where相關的迭代器對象(WhereListIterator、WhereArrayIterator),此時調用的Where方法是派生類WhereXXXIterator重寫後的Where方法,返回的是WhereXXXIterator對象,XXX表示List或Array或Enumerable。

(2)如果是其他迭代器,如調用形式為XX.Distinct().Where(),此處iterator.Where(predicate)的Iterator是Distinct的迭代器對象,此時調用的Where方法是父類Iterator種的Where方法,返回的是預設的WhereEnumerableIterator對象。

  • Line 25~33:嘗試將source轉換為數組類型。若轉換成功且長度不為0,則返回WhereArrayIterator實例。
  • Line 34~41:嘗試將source轉換為List類型。若轉換成功且長度不為0,則返回WhereListIterator實例。
  • 若兩種類型均無法轉換,則返回預設實例WhereEnumerableIterator。

Where擴展方法(二)

該方法為帶索引參數的擴展方法,其沒有對線程對資源的占用情況進行檢查,而是直接調用了WhereIterator方法

WhereIterator方法中維護了一個計數器,每迴圈一次,計數器加1,計數器中如果出現整型數字溢出情況,則拋出異常。yield return將結果以值的形式返回給枚舉器對象,可一次返回一個元素;yield break將控制權無條件地交給迭代器的調用方,該調用方為枚舉器對象的IEnumerator.MoveNext方法(或其對應的泛型System.Collections.Generic.IEnumerable<T>)或Dispose方法。

[# 有關迭代器WhereEnumerableIterator的源碼]

其包含三個欄位:源數據、過濾器、迭代器對象。

 

GetCount()方法在上文提到過,用於計算源數據集中,符合條件的元素個數,預設傳入true。

包含兩個類型轉換方法,分別轉換為數組類型和泛型集合類型。轉換原理均是通過建立相應對象,並寫入數據完成。

一個構造方法,初始化源數據集和過濾器對象。

繼承的類與介面。

由於其繼承了許多介面和類,所以此處重寫了介面中的方法,包括創建並返回新的(克隆)迭代器對象、釋放對象、向後移動到下一個元素。

  • Line 85:變數 _state 位於類Enumerable中的Iterator類型中,初始值為1,用於表示當前狀態,指示出下一步應當怎麼做。

重寫了IEnumerable<TSource>介面中的Select()和Where()方法,用於當調用Where的迭代器不屬於六大類型時,調用上一級的方法。

【Select()方法和Where()方法原理類似,在此不作敘述】

(五)排序

將了這麼多題外話,終於拉回了主題。Linq中也有用於排序的方法,包括OrderBy、OrderByDescending、ThenBy、ThenByDescending,在一個語句中,以OrderBy型開頭,之後的只能用ThenBy型,但ThenBy型可多次使用。一般地,O/T型共同存在的排序多用於多關鍵字排序

基礎語法如下:

 

[# 有關OrderBy的源碼]

OrderBy()方法有兩個重載方法,均返回一個OrderedEnumerable類型的對象。

其內置的排序方法,位於類EnumerableSorter<TElement, TKey>中,分別為PartialQuickSort()和QuickSort()。

在排序前,

(1)   對於QuickSort()方法

其重寫了父類EnumerableSorter<TElement>中的同名抽象方法,並調用類ArraySortHelper<T>中的IntrospectiveSort()方法,這與前一篇文章中提到的數組排序方法Array.Sort(),方法一致。

(2)   對於PartialQuickSort()方法

該方法直接定義在類EnumerableSorter<TElement, TKey>中,針對源數據集的某一部分進行排序。

  • Line 3:map為待排序數組;letf與right為邊界指針(此處的指針有別於C/C++中的指針,此處僅代表一個標記);minIdx與maxIdx為排序區域。
  • Line 12~19:當left小於length(未越界)時,CompareKeys()方法用於返回兩元素的大小關係:相等返回0,左大右小返回1,反之返回-1。

從左往右,找到第一個大於等於中間位置的元素。

其方法內部的四個紫色欄位均在類EnumerableSorter中

【註:下方有關五個參數的解釋為推斷得出】

_keySelector表示委托方法Func(),過濾器;_compare表示比較器對象;_descending表示是否降序;_next下一個迭代排序器對象;_keys表示經過濾器篩選出的待排序數據集;

  • Line 20~23:從右往左,找到第一個小於等於中間位置的元素。
  • Line 24~37:如果left與right沒有彼此越過對方,則交換位置,並開始下一次查找。

此時,內層迴圈結束,完成了以中間位置元素為基準值的排序,保證基準值左側小、右側大。

  • Line 38~45:若此時兩指針並未在需求的排序區域內,則相對應方向移動。
  • Line 46~61:當內層迴圈結束時兩指針的大小關係為num = num2 + 1,所以Line 46在判斷被兩指針分割的兩部分,哪一部分更短,優選處理短的一部分。

整個排序過程以遞歸的方式進行,類似於快速排序。

註:以下內容屬於推斷得出】

 

數據集在調用OrderBy()等一類排序方法後,會先將源數據轉換為泛型Buffer類型

之後,再調用類OrderedEnumerable中的SortedMap()方法

在調用真正開始排序前,首先調用ComputeMap()方法,根據過濾器,篩選出要排序的元素,並保存在_keys中。再根據不同的參數,調用不同的方法進行排序。

以上為OrderBy一類排序方法的“前搖”和過程,其餘的OrderByDescenidng()、ThenBy()、ThenByDescending()方法與OrderBy()類似。

流程圖如下:

小結二

綜合來看,就對於OrderBy一類排序演算法本身,其時間複雜度和Array中的Sort()方法相差不大,但實際運行效果卻要比Array.Sort()方法慢。原因應該在於其需要頻繁創建EnumerableSorter對象、將數據類型轉換為Buffer再轉換為數組、排序後從IOrderByEnumerable類型轉換為源數據類型,這些過程大大延長了總時間,尤其是在數據量較大的時候,所需時間將會產生較大差異。

 

三.有關Lambda表達式

Lambda表達式用來創建匿名函數,常用於委托、回調,且可以訪問到外部變數。使用Lambda運算符“=>”,從其主體中分離 lambda 參數列表,可採用以下任意一種形式:

一般地,輸入的參數不需要顯示指定類型。但當編譯器無法判斷其類型時,可顯示指明各個參數的類型:

(一) 有關匿名

(1)匿名類型

該類型可用來將一組只讀屬性封裝到單個對象中,而無需顯式定義一個類型。類型由編譯器在編譯階段生成,並且不能在源代碼級使用。可結合使用new運算符和對象初始值設定項創建匿名類型。

其中,這裡的var被定義為匿名類型(AnonymousType),v被定義為類型 `a 。

在反編譯程式中,查詢到20中相關的方法

根據IL DASM工具可以發現,其包含的主要信息:類<>f__AnonymousType0`2<’<參數para>j__TPar’,’<Message>j__TPar’>;私有隻讀欄位<Amount>i__Field和<Message>i__Field;三個非靜態重寫方法Equals()、GetHashCode()、ToString()。

以此為例,在源碼中找到相關信息,其位於程式集PresentationFramwork.dll中

  • Line 8:內部密封類,類名為<>f__AnonymousType0;泛型類型為<ControlsUsedInApp>j__TPar。
  • Line 12~17:定義參數變數的屬性—get(只讀)。
  • Line 21~25:構造函數,將傳入的參數賦值給類的內部變數。
  • Line 29~33:Equals()方法,嘗試將傳入的Object類型對象轉換為與被比較對象相同的匿名類型,並按照預設比較其和基本原則,按順序逐一比較內部參數。

  • Line 37~40:返回當前對象的哈希代碼。哈希碼為每個變數/對象的唯一標識符,用於在一定情況下相互區別。
  • Line 44~53:將匿名類型的整個部分轉化為字元串的形式(大括弧居然也算!?)。

(2)匿名方法

委托是用於引用與其具有相同標簽的方法。即,可以使用委托對象調用可由委托引用的方法。匿名方法提供了一種傳遞代碼塊作為委托參數的技術,其沒有名稱只有方法體;沒有返回值類型,類型根據具體方法中的return語句推斷。如,Func()方法、Action()方法、Predicate()方法。

所以在OrderBy一類排序中,其內部需要傳入一個匿名方法,以賦值給Func()方法,故使用Lambda表達式。

(二) Lambda 表達式的自然類型

Lambda表達式本身沒有類型,因為CLS(通用類型系統)沒有“Lambda 表達式”這一固有概念。不過,有時以非正式的方式談論 Lambda 表達式的“類型”會很方便。該非正式“類型”是指委托類型或 Lambda 表達式所轉換到的Expression類型。

從C# 10開始,Lambda表達式可能具有自然類型。編譯器不會強製為 Lambda 表達式聲明委托類型(如Func<>或Action<>),而是根據 Lambda 表達式推斷委托類型。

也就是說,一開始的Lambda表達式只能賦值給委托類型。而在此之後,Lambda表達式可以根據具體的情況,賦值給具體的類型。

【註:更多Lambda表達式內容請參閱Lambda 表達式 - C# 引用 | Microsoft Docs

[# 有關泛型的協變與逆變]

據官方解釋,協變指能夠使用比原始指定的派生類型的派生程度更大(更具體的)的類型;逆變指能夠使用比原始指定的派生類型的派生程度更小(不太具體的)的類型。

在談論協變與逆變之前先來看一下泛型集合中的對象轉換。

此處有三個類。其中Student與Worker派生自Person,那麼可以將Person稱為Student和Worker的上層數據類型;Student和Worker稱為Person的下層類型。

可以發現,雖然Person時Student和Worker的父類,但List<Person>不是List<Student>和List<Worker>的父類,所以後兩行的賦值會報錯。

在C# 4之前,類似於上述的賦值操作是不被允許的。因為假設其能夠賦值,即List<Person> p = new List<Student>();成立,那麼雖然p的類型為List<Person>但其實例對象使List<Student>,在調用方法時,調用的也就是Student的方法。如果現在實現這個語句:p.Add(new Person());其實質上是用Student中的Add方法,而Student又是Person的子類,Person無法安全(直接)轉換為Studnt對象,所以這樣的集合定義沒有意義,因此不被允許。

從C# 4開始,類似的操作,在泛型委托、泛型介面中,允許發生。但上述操作依舊是無法實現的,因為其違反類型類型轉換的基本流程。

定義一個無參泛型委托。

  • 協變:

我們嘗試在上層類型中存放下層類型。不出意外,依舊報錯。根據剛纔的分析,要想解決這個錯誤,需要解決兩個問題:

(1)   在調用p()方法時,實際上調用的是s()方法,所以需要s執行的結果能轉換為p執行後所返回的類型。即,s能夠轉換為p類型。

(2)   解除編譯器的檢查限制,在此處允許將Work<Student>類型的對象賦值給Work<Person>類型的變數。

對於(1)已經滿足,由隱式轉換直接完成;而條件(2)就需要在委托中加上out關鍵字。

  • 逆變

嘗試在上層類型中存放下層類型。解決這個錯誤,也需要解決兩個問題:

(1)在調用s()方法時,實際上調用的是p()方法,即,p能夠轉換為s類型。

(2)解除編譯器的檢查限制,在此處允許將Work<Person>類型的對象賦值給Work<Student>類型的變數。

對於(1)因為Student為Person的子類,所以二者存在聯繫,通過強制類型轉換可以實現;而條件(2)需要在委托中加上in關鍵字。

【註:如果沒有子父類的關係,加上in/out關鍵字,也無法實現】

簡而言之:協變可以在上層數據類型中存放下層對象;逆變可以在下層的數據類型中存放上層對象(這裡的上層與下層是相對而言),這兩個過程本質上是參數的類型轉換

據微軟官方的說法,協變於逆變只發生在數組、委托、泛型參數之上,對於類的上下轉型而言不算做協變於逆變。

TRANSLATE with x English
Arabic Hebrew Polish
Bulgarian Hindi Portuguese
Catalan Hmong Daw Romanian
Chinese Simplified Hungarian Russian
Chinese Traditional Indonesian Slovak
Czech Italian Slovenian
Danish Japanese Spanish
Dutch Klingon Swedish
English Korean Thai
Estonian Latvian Turkish
Finnish Lithuanian Ukrainian
French Malay Urdu
German Maltese Vietnamese
Greek Norwegian Welsh
Haitian Creole Persian  
  TRANSLATE with COPY THE URL BELOW Back EMBED THE SNIPPET BELOW IN YOUR SITE Enable collaborative features and customize widget: Bing Webmaster Portal Back
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 集成 Spring Doc 介面文檔和 knife4j 前面已經集成 MyBatis Plus、Druid 數據源,開發了 5 個介面。在測試這 5 個介面時使用了 HTTP Client 或 PostMan,無論是啥都比較麻煩:得自己寫請求地址 URL、請求參數等,於是多年前就出現了 Swagg... ...
  • 前言 😋 嗨嘍,大家好呀~這裡是愛看美女的茜茜吶 環境開發: Python 3.8 Pycharm 模塊使用: requests parsel csv 基本流程思路: 告訴你 實現程式 應該怎麼去操作 一. 數據來源分析: 分析我們想要數據內容在哪裡? 請求那個網站, 可以得到相應的數據 抓包分析 ...
  • 精華筆記: 向上造型: 代碼復用 超類型的引用指向派生類的對象 能點出來什麼,看引用的類型 這是規定,記住就OK 何時向上造型: 多種角色能幹的事都一樣的時候,可以將多種角色統一造型到超類數組中,實現代碼復用 eg: 學生/老師/醫生都是輸出名字+問好 乾的事都一樣, ​ 就可以將學生/老師/醫生統 ...
  • 前兩天一個鄰居發出了靈魂質問:“為什麼我買的180平和你的169平看上去一樣大?” “因為咱倆的套內面積都是138平......” 我們去看房子,比較不同樓盤的價格,看的都是單價,可這個單價,卻是用(總價 ÷ 建築面積)計算的。而我們實際買到手裡的,是套內面積。 套內面積 = 使用面積+牆體厚度+陽 ...
  • 線程本地存儲 · 語雀 (yuque.com) 線程本地存儲提供了線程記憶體儲變數的能力,這些變數是線程私有的。 線程本地存儲一般用在跨類、跨方法的傳遞一些值。 線程本地存儲也是解決特定場景下線程安全問題的思路之一(每個線程都訪問本線程自己的變數)。 Java 語言提供了線程本地存儲,ThreadLo ...
  • 在大部分涉及到資料庫操作的項目裡面,事務控制、事務處理都是一個無法迴避的問題。這裡我們一起探討下關於事務控制相關的一些內容。 ...
  • 來源: blog.csdn.net/fumitzuki/article/details/81630048 volatile關鍵字是由JVM提供的最輕量級同步機制。與被濫用的synchronized不同,我們並不習慣使用它。想要正確且完全的理解它並不容易。 Part1Java記憶體模型 Java記憶體模型 ...
  • 多商戶商城系統,也稱為B2B2C(BBC)平臺電商模式多商家商城系統。可以快速幫助企業搭建類似拼多多/京東/天貓/淘寶的綜合商城。 多商戶商城系統支持商家入駐加盟,同時滿足平臺自營、旗艦店等多種經營方式。平臺可以通過收取商家入駐費,訂單交易服務費,提現手續費,簡訊通道費等多手段方式,實現整體盈利。 ...
一周排行
    -Advertisement-
    Play Games
  • 一、引言:什麼是 JSON JSON (Java Script Object Notation) 是一種很常用的數據格式,它常常用在 web 應用程式中。它可以表示結構化的數據。 下麵是常見的 JSON 文件結構 { "name": "Kamishiro Rize", "age": "22", "o ...
  • 前言 大家好,我是蝸牛,在上一篇中,我們介紹了不同版本的HTTP區別和發展背景,這篇文章我們來聊聊HTTP的缺點,HTTP缺點大致總結有以下三點: 通信使用明文(不加密),內容可能會被竊聽。 不驗證通信方的身份,因此有可能遭遇偽裝(客戶端和服務端都有可能) 無法證明報文的完整性,有可能會被篡改。 其 ...
  • resultMap處理欄位和屬性的映射關係 如果欄位名與實體類中的屬性名不一致,該如何處理映射關係? 第一種方法:為查詢的欄位設置別名,和屬性名保持一致 下麵是實體類中的屬性名: private Integer empId; private String empName; private Integ ...
  • 大家在看到這篇文章前,為了有一個舒適的c++IDE,一定感受到了Dev-c++的廉價感,Clion功能的多餘,VS的臃腫。他們也有自己的優點,但糟點太多,令人十分難受。而VS Code,可以取長補短。下麵的配置內容,可以讓你在刷題時,享受絲滑的動畫,體會集成終端的方便,讓你覺得Coding不再枯燥。 ...
  • 給定一個不含重覆數字的數組 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。 示例 1: 輸入:nums = [1,2,3] 輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2: 輸入:nums = [0,1] 輸 ...
  • 設計模式的目的 編寫軟體過程中,程式員面臨著來自 耦合性,內聚性以及可維護性,可擴展性,重用性,靈活性 等多方面的 挑戰,設計模式是為了讓程式(軟體),具有更好 代碼重用性 (即:相同功能的代碼,不用多次編寫) 可讀性 (即:編程規範性, 便於其他程式員的閱讀和理解) 可擴展性 (即:當需要增加新的 ...
  • 本文講解了決策樹的創鍵的過程,包括熵,信息增益的計算,還有決策樹的創建,以及使用matplotlib讓決策樹可視化的詳細過程 ...
  • ♠ use C++11 倍數 若 $a,b,k \in \mathbb N$,且 $a \times k=b$,那麼 $b$ 是 $a$ 的倍數,稱 $a$ 整除 $b$,記作 $a \mid b$。 $[1,n]\in \mathbb N$ 中 $x \in \mathbb N$ 的倍數有 $\l ...
  • LinkList可以定義指向List的指針 1.當函數參數為LinkList L時,意味著只改變或操作List的內容,而不需要改變L這個指針 如 Status GetElem(LinkList L,int i,ElemType) 2.當參數為LinkList &L時,意味著需要改變或操作L這個指針本 ...
  • Spring 5框架 一、Spring概念 1、Spring是輕量級的JavaEE框架 2、Spring可以解決企業應用開發的複雜性 3、Spring有兩個核心部分:IOC和AOP ​ 1)IOC:控制反轉,把創建對象過程交給Spring進行管理 ​ 2)AOP:面向切麵,不修改源代碼進行功能增強 ...