时间:2021-05-20
因正则表达式搜索总是出现死循环,开始考虑改为其他搜索方式,因为.net自带的IndexOf默认只能找到第一个或最后一个,如果要把全部的匹配项都找出来,还需要自己写循环SubString,所以想找下有没有现成的,就发现了在这个领域里,BM算法是王道,而sunday算法据说是目前最好的改进版,这一点我没有从国外的网站尤其是wiki上找到印证,但中文谈论sunday的文章很多,我就姑且认为它是最好的吧。
复制代码 代码如下:
public static int SundaySearch(string text, string pattern)
{
int i = 0;
int j = 0;
int m = pattern.Length ;
int matchPosition = i;
while (i < text.Length && j < pattern.Length)
{
if (text[i] == pattern[j])
{
i++;
j++;
}
else
{
if(m==text.Length-1)break;
int k = pattern.Length - 1;
while (k >= 0 && text[m ] != pattern[k])
{
k--;
}
int gap = pattern.Length - k;
i += gap;
m = i + pattern.Length;
if (m > text.Length) m = text.Length - 1;
matchPosition = i;
j = 0;
}
}
if (i <= text.Length)
{
return matchPosition;
}
return -1;
}
好了,现在测试下性能:
复制代码 代码如下:
public static void PerformanceTest()
{
StreamReader reader = new StreamReader("D:\\LogConfiguration.xml", Encoding.ASCII);
string context = reader.ReadToEnd();
string pattern = "xxxx";
int count = 1000*10;
Stopwatch watch=new Stopwatch();
//watch.Start();
//for (int i = 0; i < count; i++)
//{
// int pos= Sunday.GetPositionFirst(context, pattern, true);
//}
//watch.Stop();
//Console.WriteLine(watch.ElapsedMilliseconds);
watch.Reset();
watch.Start();
for (int i = 0; i < count; i++)
{
int pos = context.IndexOf(pattern);
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);
watch.Reset();
watch.Start();
for (int i = 0; i < count; i++)
{
int pos = Sunday.SundaySearch(context, pattern);
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);
}
在可以找到匹配与不能找到匹配两种情况下,sunday算法耗时大概是indexof的20%左右。算法确实有用。
但千万不要使用substring来实现算法,那样会新生成很多字符串中间变量,算法带来的好处远远不如分配内存复制字符串的消耗大,注释掉的部分就是使用substring实现的,比indexof慢很多。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了PHP实现的字符串匹配算法————sunday算法。分享给大家供大家参考,具体如下:Sunday算法是DanielM.Sunday于1990年提出
本文实例讲述了C#二分查找算法。分享给大家供大家参考。具体实现方法如下://inputarrayisassumedtobesortedpublicintBina
本文实例讲述了C#折半插入排序算法实现方法。分享给大家供大家参考。具体实现方法如下:publicstaticvoidBinarySort(int[]list){
本文实例讲述了C#冒泡法排序算法。分享给大家供大家参考。具体实现方法如下:staticvoidBubbleSort(IComparable[]array){in
本文实例讲述了java实现的海盗算法。分享给大家供大家参考,具体如下:前面介绍了《C#实现的海盗分金算法》,这里再给出一个Java优化版的算法:packageu