一般地,对于运算符“==”和Equals()方法,在比较方式上还是有所差异 。
(1)对于值类型和字符串,这两种方式均只比较内容;
(2)对于除字符串以外的引用类型,运算符”==”比较的是在栈中的引用(是否指向同一个对象);方法Equals()比较的是在堆中的内容(是否是同一个对象的引用) 。
但这样就有一个问题,我们知道C#对于字符串有某些优化 。一般地,内容相同的字符串不会开辟新的堆空间,而是指向储存在暂存池(堆的一部分 , Java中称为常量池)中的对象 。但以某些方式创建的字符串对象,并不会检查暂存池,而是直接在堆中开辟新空间,导致内容相同的字符串,栈和堆的地址均不同 。那么这样是否会导致判断运算符和方法Equals()出现问题呢?有关该部分的详细内容请转到文末的 [# 有关字符串的比较与暂存池]
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2195024-17.png)
文章插图
其次是ReadOnlySpan<T> 。这是一种较为特殊的运算符重载,其中关键字implicit用于声明隐式的自定义类型转换运算符 。它可以实现2个不同类型的隐式转换,提高代码的可读性 。但是使用隐式转换操作符之后,在编译时会跳过异常检查,所以在使用隐式转换运算符前,应当在一定程度上确保其不会引发异常并且不会丢失信息,否则在运行时会出现一些意外的问题 。该隐式转换 , 是将string类型转换成ReadOnlySpan<char>类型 。
先简单介绍一下类型Span<T>
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2191W4-18.png)
文章插图
该类型被微软官方称为“新增的重要组成部分“,其主要作用是提供任意内存连续区域的类型安全与内存安全表示形式 。即,此数据类型可以实现对任意内存的相邻区域进行操作 , 无论相应内存是与托管对象相关联,还是通过互操作由本机代码提供,亦或是位于堆栈上 。解决了在不使用不安全代码(指针等直接对内存进行的操作)的情况下,实现了在内存上 , 对数据进行修改的操作 。更多详细信息请参阅(C# - Span 全面介绍:探索 .NET 新增的重要组成部分 | Microsoft Docs) 。
ReadOnlySpan<T>亦是如此,只是被附上了对内部元素只读的属性,以满足字符串不可修改的基本性质 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192137-19.png)
文章插图
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2193964-20.png)
文章插图
其将传入的字符串首字符作为指针的起始位置,length为字符串的长度 , 通过指针+偏移量的方式(类似于C++中通过指针ptr访问数组第一个位置,ptr++实现向后偏移),实现对数据的访问 。
5. 九个构造方法
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2193613-21.png)
文章插图
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S219A48-22.png)
文章插图
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194549-23.png)
文章插图
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21932b-24.png)
文章插图
与其他类型的构造方法不同 , 这九个构造方法均为外部方法extern,需要从外部从新定义其实现形式 。个人猜测 , 外部定义可能在.NET库中 。其功能均是将所给数据集,按照一定条件转化为字符串 。详细信息参考下表:
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192258-25.png)
文章插图
(三) 有关String的查找与匹配1. BF算法(Brute Force)Brute Force,一种暴力匹配算法,其思想是对于两个字符串 s 与,在s(主串)中查找/匹配pat(模式串) 。若s[i] == pat[j],则i++且j++;否则i++且j = 0 。此时 i 即为模式串 pat 在主串 s 中第一次匹配的起始下标位置 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192229-26.png)
文章插图
复杂度分析:
- 时间复杂度:O( nm )(最快O( n+ m ),pat 在 s 的开头就匹配完成;最慢O( nm ) , 每次都是在 pat 的末尾匹配失败)
- 空间复杂度:O( 1 )
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192J9-27.png)
文章插图
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192X0-28.png)
文章插图
实测运行时间:
【注:由于牛客上的本题无法获取该超时样例,因此此处及之后选用某一衰减测试样例进行实测计时,仅用于观察算法时间复杂度 。样例:主串字符全为 ‘A’,长度为500000;模式串字符全为 ‘A’,长度为100】
推荐阅读
- 【前端必会】不知道webpack插件? webpack插件源码分析BannerPlugin
- 20220929-ArrayList扩容机制源码分析
- Optional源码解析与实践
- Go 源码解读|如何用好 errors 库的 errors.Is 与 errors.As() 方法
- .Net下的分布式唯一ID
- .NET 反向代理 YARP 代理 GRPC
- 赞美父亲的作文结尾 赞美父亲的高中作文
- 关于对自己有信心的名言名语 对学习有信心的名言
- 关于父亲的高中作文800字 关于父亲的高中作文
- 高一化学全面学习方法整理