浙江龙网

  1. 首页 > 生活百科 > >

.NET源码学习 [算法2-数组与字符串的查找与匹配]

生活百科

[算法2-数组与字符串的查找与匹配] （.NET源码学习）关键词：1. 数组查找（算法）   2. 字符串查找（算法）   3. C#中的String（源码）   4. 特性Attribute 与内在属性（源码）   5. 字符串的比较（底层原理）   6. C#中的StringComparsion（源码）   7. 字符串与暂存池（底层原理）
 
【注：本人在写文章时遇到认为有必要或想要展开的点就会将其并入文章中，避免事后遗忘 。因此非主题内容可能会比较多，篇幅也可能比较大，各位学者在浏览时可以自行转跳到感兴趣的部分进行阅览 ， 存在相关问题或建议，欢迎留言指导，谢谢！】
 
查找 ， 大体上可以分为两类：数组查找、字符串查找 。其中数组查找以二分为主；字符串查找以BK、BM、KMP三类算法为主 。由于二分在之前的文章中已经详细叙述过，在此不再重复论述 。故本文主要以有关字符串的查找为重点，附带.NET关于String类型及相关底层逻辑的源码分析为主 ， 进行论述 。
【# 请先阅读注意事项】
【注：
（1）文章篇幅较长，可直接转跳至想阅读的部分 。
（2）以下提到的复杂度仅为算法本身，不计入算法之外的部分（如，待排序数组的空间占用）且时间复杂度为平均时间复杂度 。
（3）除特殊标识外，测试环境与代码均为.NET 6/C# 10 。
（4）默认情况下，所有解释与用例的目标数据均为升序 。
（5）默认情况下，图片与文字的关系：图片下方，是该幅图片的解释 。
【.NET源码学习 [算法2-数组与字符串的查找与匹配]】（6）文末“ [ # … ] ”的部分仅作补充说明，非主题（算法）内容，该部分属于 .NET 底层运行逻辑，有兴趣可自行参阅 。
（7）本文内容基本为本人理解所得 ， 可能存在较多错误 ， 欢迎指出并提出意见，谢谢 。】
一、有关数组(一) 二分查找及相关优化关于二分的相关内容，在本人的这篇文章中（LC T668笔记 & 有关二分查找、第K小数、BFPRT算法 - PaperHammer - 博客园 (cnblogs.com)）有较为详细地论述 ， 详情请参阅 。
在此，仅总结一下二分的要点：
1. 二分集合须保证有序 。有序是二分的前提 ， 在二分前须明确二分的对象 ， 该对象必须具有有序性 。
2. 确定搜索区间形式（闭区间、左闭右开、左开右闭） 。不同区间形式，循环条件与最终返回值不同；同时也应用于不同的场景 。
3. 尽量写或想清楚所有的if…else… ， 清楚地展现出所有细节，避免不必要的纰漏与麻烦 。
(二) 有关方法BinarySearch()的源码该方法的主要实现形式是双指针或折半查找，详细内容在本人之前的文章（[数据结构1.2-线性表] 动态数组ArrayList（.NET源码学习） - PaperHammer - 博客园 (cnblogs.com)）中，详情请参阅 。
二、有关字符串(一) .NET中的String与C#中的string1. C#是区分大小写的语言，所以string与String理论上是不同的，但在编译器的定义导航中，却将这两个类型均导航至同一个类——类String 。
2. 据现有资料可知，String是.NET（以前称为.NET Framework）中的类，string是C#中的类 。在C#中使用string时，编译器会将string自动映射到.NET中的String，同时调用的方法也是.NET中类String内部的方法 。据该原理 ， 使用String可以在一定程度上减少编译器的工作量，但微软官方不建议这样，依旧建议使用string以符合相关规范 。其他基本数据类型也是如此，如short映射Int16，int映射Int32，long映射Int64，double映射Double等 。
3. 这样做的原因个人猜测可能如下：.NET是一套底层运行规范，其需要对所有支持的语言定义一个通用的规则（CLS通用语言规范Common Language Specification）不同语言语法的不同，.NET通过CLS提供了公共的语法，不同语言经过IL的翻译生成对应的.NET语法 。如F#中的let赋值语句（let str = “.NET”;;）；VB中的String（Dim 变量名 As String = “.NET”）；加上现在C#中的string 。它们都是基于.NET运行的 ， 所以需要有一个总纲来规范化，使得每个语言具有独特性的同时，可以实现相同或相近的功能 。因此在.NET中定义了类String，无论时哪种语言，只要编译时需要使用.NET，均须遵守其相关规范，将独特的风格转换为统一且通用的规范化表达 。
4. 因此 ， String不是C#中的关键字 ， 可以将其用作变量名 。

.NET源码学习 [算法2-数组与字符串的查找与匹配]

推荐阅读


上一篇：二 APICloud可视化编程

下一篇：day43-反射02