1. 首頁 > 生活百科 > >

.NET源碼學習 [算法2-數組與字符串的查找與匹配]( 三 )

生活百科


一般地，對于運算符“==”和Equals()方法，在比較方式上還是有所差異 。
（1）對于值類型和字符串，這兩種方式均只比較內容；
（2）對于除字符串以外的引用類型，運算符”==”比較的是在棧中的引用（是否指向同一個對象）；方法Equals()比較的是在堆中的內容（是否是同一個對象的引用） 。
但這樣就有一個問題，我們知道C#對于字符串有某些優化 。一般地，內容相同的字符串不會開辟新的堆空間，而是指向儲存在暫存池（堆的一部分 ， Java中稱為常量池）中的對象 。但以某些方式創建的字符串對象，并不會檢查暫存池，而是直接在堆中開辟新空間，導致內容相同的字符串，棧和堆的地址均不同 。那么這樣是否會導致判斷運算符和方法Equals()出現問題呢？有關該部分的詳細內容請轉到文末的 [# 有關字符串的比較與暫存池]

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
其次是ReadOnlySpan<T> 。這是一種較為特殊的運算符重載，其中關鍵字implicit用于聲明隱式的自定義類型轉換運算符 。它可以實現2個不同類型的隱式轉換，提高代碼的可讀性 。但是使用隱式轉換操作符之后，在編譯時會跳過異常檢查，所以在使用隱式轉換運算符前，應當在一定程度上確保其不會引發異常并且不會丟失信息，否則在運行時會出現一些意外的問題 。該隱式轉換 ， 是將string類型轉換成ReadOnlySpan<char>類型 。
先簡單介紹一下類型Span<T>
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
該類型被微軟官方稱為“新增的重要組成部分“，其主要作用是提供任意內存連續區域的類型安全與內存安全表示形式 。即，此數據類型可以實現對任意內存的相鄰區域進行操作 ， 無論相應內存是與托管對象相關聯，還是通過互操作由本機代碼提供，亦或是位于堆棧上 。解決了在不使用不安全代碼（指針等直接對內存進行的操作）的情況下，實現了在內存上 ， 對數據進行修改的操作 。更多詳細信息請參閱（C# - Span 全面介紹：探索 .NET 新增的重要組成部分 | Microsoft Docs） 。
ReadOnlySpan<T>亦是如此，只是被附上了對內部元素只讀的屬性，以滿足字符串不可修改的基本性質 。
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
其將傳入的字符串首字符作為指針的起始位置，length為字符串的長度 ， 通過指針+偏移量的方式（類似于C++中通過指針ptr訪問數組第一個位置，ptr++實現向后偏移），實現對數據的訪問 。
5. 九個構造方法
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
與其他類型的構造方法不同 ， 這九個構造方法均為外部方法extern，需要從外部從新定義其實現形式 。個人猜測 ， 外部定義可能在.NET庫中 。其功能均是將所給數據集，按照一定條件轉化為字符串 。詳細信息參考下表：
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
(三) 有關String的查找與匹配1. BF算法（Brute Force）Brute Force，一種暴力匹配算法，其思想是對于兩個字符串 s 與，在s（主串）中查找/匹配pat（模式串） 。若s[i] == pat[j]，則i++且j++；否則i++且j = 0 。此時 i 即為模式串 pat 在主串 s 中第一次匹配的起始下標位置 。
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
復雜度分析：
  • 時間復雜度：O( nm )（最快O( n+ m )，pat 在 s 的開頭就匹配完成；最慢O( nm ) ， 每次都是在 pat 的末尾匹配失?。?/li>
  • 空間復雜度：O( 1 )
我們找個題目測試一下其運行效率（題目：kmp算法_?？皖}霸_?？途W (nowcoder.com)）
.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

文章插圖
實測運行時間：
【注：由于牛客上的本題無法獲取該超時樣例，因此此處及之后選用某一衰減測試樣例進行實測計時，僅用于觀察算法時間復雜度 。樣例：主串字符全為 ‘A’，長度為500000；模式串字符全為 ‘A’，長度為100】

推薦閱讀