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慢很多。

赞 (0)

相关推荐

  • C#实现排列组合算法完整实例

    排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法.分享给大家供大家参考之用.具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections.Generic; namespace Test { class Prog

  • 基于私钥加密公钥解密的RSA算法C#实现方法

    本文实例讲述了基于私钥加密公钥解密的RSA算法C#实现方法,是一种应用十分广泛的算法.分享给大家供大家参考之用.具体方法如下: 一.概述 RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作. RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一.RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价. RSA的安全性依赖于大数分解.公钥和私钥都是两个大素数( 大于 1

  • C#加密算法汇总(推荐)

    方法一: 复制代码 代码如下: //须添加对System.Web的引用 using System.Web.Security; ... /// <summary> /// SHA1加密字符串 /// </summary> /// <param name="source">源字符串</param> /// <returns>加密后的字符串</returns> public string SHA1(string sour

  • c#冒泡排序算法示例

    复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace 冒泡排序{    class Program    {        static void swap( ref int  atemp, ref int  btemp)//注意ref的使用        {            int temp = atemp;            at

  • C#灰度化图像的实例代码

    用伪语句可以表示如下 public bitmap GrayScal(bitmap orgbmp){    建立一个与原图片等大的8位的图片    取出原图像中的每一个点    新图像的点=原图像点的红色量*系数1+绿色量*系数2+黄色量*系统3    返回新图像} 复制代码 代码如下: /// <summary>    /// 对图像进行点运算,    /// </summary>    public class PointTrans    {        private rea

  • C#计算两个文件的相对目录算法的实例代码

    楼主大菜鸟一只,第一次写技术博客,如果有概念错误或代码不规范的地方,还请各位多多批评指正.话不多说,来看题: 前一阵子开发了一个用户控件,里面调用了很多css,js等资源文件,而引用控件的页面所在目录是不同的.问题出来了:如果目录不同,那么控件里引用css,js资源文件的路径也会相应变化.现在已知两个文件相对于网站根目录的路径,如何计算相对路径呢?请看代码: 复制代码 代码如下: public string GetRelativePath(string path1, string path2){

  • C#实现把彩色图片灰度化代码分享

    彩色图片转为灰度图的公式如下: 复制代码 代码如下: gray(i,j) = 0.299 * Red(i,j)+0.587*Green(i,j)+0.114*Blue(i,j) 其中gray(i,j) 为转化后的灰度值  (i,j)为像素点的位置. 源代码如下: public static Bitmap ChangeGray(Bitmap b) { BitmapData bmData = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), Ima

  • KMP算法的C#实现方法

    本文实例简述了KMP算法的C#实现方法,分享给大家供大家参考.具体如下: 具体思路为:next函数求出模式串向右滑动位数,再将模式串的str的next函数值 存入数组next. 具体实现代码如下: static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; while (i < str.Length - 1) { if (j == -1 || str[i] == str[j]) {

  • 基于c#图像灰度化、灰度反转、二值化的实现方法详解

    图像灰度化:将彩色图像转化成为灰度图像的过程成为图像的灰度化处理.彩色图像中的每个像素的颜色有R.G.B三个分量决定,而每个分量有255中值可取,这样一个像素点可以有1600多万(255*255*255)的颜色的变化范围.而灰度图像是R.G.B三个分量相同的一种特殊的彩色图像,其一个像素点的变化范围为255种,所以在数字图像处理种一般先将各种格式的图像转变成灰度图像以使后续的图像的计算量变得少一些.灰度图像的描述与彩色图像一样仍然反映了整幅图像的整体和局部的色度和亮度等级的分布和特征.图像的灰度

  • C#实现协同过滤算法的实例代码

    复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace SlopeOne{    public class Rating    {        public float Value { get; set; }        public int Freq { get; set; }        public float AverageValue

  • c#哈希算法的实现方法及思路

    c#哈希算法的实现方法及思路

    有想过hash["A1"] = DateTime.Now;这句是怎么实现的吗?我们来重温下学校时代就学过的哈希算法吧. 我们要写个class,实现如下主程序调用: 复制代码 代码如下: static void Main(string[] args)        {            MyHash hash = new MyHash();            hash["A1"] = DateTime.Now;            hash["A2

  • C#彩色图片灰度化算法实例

    本文实例讲述了C#彩色图片灰度化实现方法.分享给大家供大家参考.具体方法如下: 主要功能代码如下: 复制代码 代码如下: public static Bitmap MakeGrayscale(Bitmap original) { //create a blank bitmap the same size as original Bitmap newBitmap = new Bitmap(original.Width, original.Height); //get a graphics obje

  • 解析C#彩色图像灰度化算法的实现代码详解

    代码如下所示: 复制代码 代码如下: public static Bitmap MakeGrayscale(Bitmap original)        {            //create a blank bitmap the same size as original            Bitmap newBitmap = new Bitmap(original.Width, original.Height);            //get a graphics object

  • c#中实现图片灰度化技术详解

    c#中实现图片灰度化技术详解

    去年买了本数字图像处理算法,一直都没有看,前几个星期都一直忙着工作上的活,趁这阶段悠闲点,玩一玩图片处理,这玩意还是非常有意思的. 以前我们在做Web上的用户注册时,通常都会做一个验证码,大家都知道用来防止暴力注册的,当然提到验证码大家都知道C#里面有一个Bitmap类专门用来处理图片的,好吧,这一篇我们从最简单的"图片灰度化"说起. 一:图片灰度化 我们都知道,位图是由一个一个像素点组成的,像素点可能是红色,橙色,粉色等等,这些颜色我们都知道是用RGB来表示的. 每个颜色分量都是一个

随机推荐