快捷導(dǎo)航

c#實(shí)現(xiàn)sunday算法實(shí)例

更新時(shí)間：2013年08月19日 16:34:16 作者：

Sunday算法思想跟BM算法很相似，在匹配失敗時(shí)關(guān)注的是文本串中參加匹配的最末位字符的下一位字符,下面是用C#實(shí)現(xiàn)sunday的實(shí)例代碼，有需要的朋友可以參考一下

因正則表達(dá)式搜索總是出現(xiàn)死循環(huán)，開(kāi)始考慮改為其他搜索方式，因?yàn)?net自帶的IndexOf默認(rèn)只能找到第一個(gè)或最后一個(gè)，如果要把全部的匹配項(xiàng)都找出來(lái)，還需要自己寫(xiě)循環(huán)SubString，所以想找下有沒(méi)有現(xiàn)成的，就發(fā)現(xiàn)了在這個(gè)領(lǐng)域里，BM算法是王道，而sunday算法據(jù)說(shuō)是目前最好的改進(jìn)版，這一點(diǎn)我沒(méi)有從國(guó)外的網(wǎng)站尤其是wiki上找到印證，但中文談?wù)搒unday的文章很多，我就姑且認(rèn)為它是最好的吧。

復(fù)制代碼代碼如下:

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;
}

好了，現(xiàn)在測(cè)試下性能：

復(fù)制代碼代碼如下:

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算法耗時(shí)大概是indexof的20%左右。算法確實(shí)有用。

但千萬(wàn)不要使用substring來(lái)實(shí)現(xiàn)算法，那樣會(huì)新生成很多字符串中間變量，算法帶來(lái)的好處遠(yuǎn)遠(yuǎn)不如分配內(nèi)存復(fù)制字符串的消耗大，注釋掉的部分就是使用substring實(shí)現(xiàn)的，比indexof慢很多。

您可能感興趣的文章: