c#实现sunday算法实例

 更新时间:2020年6月25日 11:40  点击:2219

因正则表达式搜索总是出现死循环,开始考虑改为其他搜索方式,因为.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慢很多。

[!--infotagslink--]

相关文章

  • C#实现简单的登录界面

    我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
  • 浅谈C# 字段和属性

    这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
  • C#中截取字符串的的基本方法详解

    这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
  • C#实现简单的Http请求实例

    这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
  • C#连接SQL数据库和查询数据功能的操作技巧

    本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
  • C#中new的几种用法详解

    本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
  • 使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)

    这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
  • C#开发Windows窗体应用程序的简单操作步骤

    这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
  • C#从数据库读取图片并保存的两种方法

    这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
  • C#和JavaScript实现交互的方法

    最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
  • C++调用C#的DLL程序实现方法

    本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
  • 轻松学习C#的基础入门

    轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
  • C#变量命名规则小结

    本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
  • C#绘制曲线图的方法

    这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
  • C# 中如何取绝对值函数

    本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
  • c#自带缓存使用方法 c#移除清理缓存

    这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
  • c#中(&&,||)与(&,|)的区别详解

    这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
  • 经典实例讲解C#递归算法

    这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
  • C#学习笔记- 随机函数Random()的用法详解

    下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
  • C#中list用法实例

    这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25