c#实现sunday算法实例
因正则表达式搜索总是出现死循环,开始考虑改为其他搜索方式,因为.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慢很多。
上一篇: 01-HTML深入
下一篇: 利用多线程句柄设置鼠标忙碌状态的实现方法
推荐阅读
-
C#下实现创建和删除目录的实例代码
-
python基础教程:决策树剪枝算法的python实现方法详解本文实例讲述了决策树剪枝算法的python实现方法。分享给大家供大家参考,具体如下: 决策树是一种依托决策而建立起来的一种树。在机器学习中
-
c# 应用NPOI获取Excel中的图片,保存至本地的算法的图文代码实例详解
-
C#的3DES加密解密算法实例代码
-
C#实现简单的JSON序列化功能代码实例
-
java实现sunday算法示例分享
-
基于C#实现的三层架构实例
-
c# in depth的泛型实现实例代码
-
java实现遗传算法实例分享(打印城市信息)
-
java实现哈弗曼编码与反编码实例分享(哈弗曼算法)