快速的字符串查找算法（Boyer-Moore）性能测试代码

来源：百度文库编辑：神马文学网时间：2024/04/23 15:18:11

快速的字符串查找算法（Boyer-Moore）
在CodeProject，Efficient Boyer-Moore Search in Unicode Strings，作者leseul 展示了Boyer-Moore算法的威力，代码这里下载：
Download source - 10.2 Kb
Download demo project - 5.18 Kb
我写了一个性能测试：
public static void Main()
{
string pattern = "AbC";
string target = "AbCaBc";
string pressure;
StringBuilder b = new StringBuilder();
int count = 10000000;
for (int i = 0; i < count; i++)
{
b.Append(target);
}
pressure = b.ToString();
//BM without case senstive
HiPerfTimer time = new HiPerfTimer();
time.Start();
CIBMSearcher BMS = new CIBMSearcher(pattern, false);
int index = BMS.Search(pressure, 0);
while (index >= 0)
{
index = BMS.Search(pressure, index + pattern.Length);
}
time.Stop();
Console.WriteLine("BM without case senstive:" + time.Duration);
GC.Collect();
//BM with case senstive
time = new HiPerfTimer();
time.Start();
BMS = new CIBMSearcher(pattern, true);
index = BMS.Search(pressure, 0);
while (index >= 0)
{
index = BMS.Search(pressure, index + pattern.Length);
}
time.Stop();
Console.WriteLine("BM with case senstive:" + time.Duration);
GC.Collect();
//SubString without case senstive
time = new HiPerfTimer();
time.Start();
index = pressure.IndexOf(pattern);
while (index >= 0)
{
index = pressure.IndexOf(pattern, index + pattern.Length);
}
time.Stop();
Console.WriteLine("SS without case senstive:" + time.Duration);
GC.Collect();
Console.ReadLine();
}
结果如下：
BM without case senstive:1.2411443536895
BM with case senstive:0.707685620917367
SS without case senstive:1.77157282256596
SS是SubString。
我的电脑是PIV 2.8G + 1GRAM 。
BM的威力可见一斑，估计我之前写的高效的忽略大小写的字符串替换(Replace)函数（多种方法比较）可以大大改善了。
高效的算法的意义就在于此啊！这个算法现暂不研究，今天太忙，得看看今晚是否有时间研究一下。
注释：代码不格式化是因为代码插入功能有错误，无法使用。
点击这里下载我的写的测试代码

快速的字符串查找算法（Boyer-Moore）性能测试代码博客园 - 灵感之源的Forgio-智能工厂 - 快速的字符串查找算法（Boyer-Moore） java中GB2312字符串的判断（代码片段）字符串hash算法比较|字符串,hash,算法性能测试指标的基本概念学术的四种型态Ernest Boyer KMP字符串匹配算法笔记查找字符在字符串中最后出现的位置，急！ - Shell - ChinaUnix.net KMP：在一个长字符串中匹配一个短子串的无回溯算法 KMP：在一个长字符串中匹配一个短子串的无回溯算法穴位快速查找穴位快速查找* 软件测试：针对代码移交的测试技术文摘: 字符串hash算法比较字符串相似度算法介绍 zz 性能测试（并发负载压力）测试分析如何准确、快速的查找对方的IP地址快速、准确查找对方IP地址的方法算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD... 经络与穴位--快速查找(另一版本）快速排序算法快速排序算法快速计算法科学快速品算法