- 相關推薦
c#實現(xiàn)sunday算法實例
Sunday算法思想跟BM算法很相似,在匹配失敗時關注的是文本串中參加匹配的最末位字符的下一位字符，下面小編為大家整理了c#實現(xiàn)sunday算法實例，希望能幫到大家！
因正則表達式搜索總是出現(xiàn)死循環(huán)，開始考慮改為其他搜索方式，因為.net自帶的IndexOf默認只能找到第一個或最后一個，如果要把全部的匹配項都找出來，還需要自己寫循環(huán)SubString，所以想找下有沒有現(xiàn)成的，就發(fā)現(xiàn)了在這個領域里，BM算法是王道，而sunday算法據(jù)說是目前最好的改進版，這一點我沒有從國外的網(wǎng)站尤其是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;
}
好了，現(xiàn)在測試下性能：
復制代碼 代碼如下:
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來實現(xiàn)算法，那樣會新生成很多字符串中間變量，算法帶來的好處遠遠不如分配內(nèi)存復制字符串的消耗大，注釋掉的部分就是使用substring實現(xiàn)的，比indexof慢很多。
【c#實現(xiàn)sunday算法實例】相關文章：
c#實現(xiàn)輪詢算法實例代碼05-31
C#實現(xiàn)協(xié)同過濾算法的實例代碼06-19
KMP算法的C#實現(xiàn)方法04-11
C語言中實現(xiàn)KMP算法實例08-09
C語言實現(xiàn)歸并排序算法實例03-19
c#快速排序算法04-21
c#冒泡排序算法08-15