科学就是不断地认识,不仅是发现,而且是发明。——鲁巴金(上海网站建设)
撒列实现关键字过滤,速度可快了
Admin
2012年1月20日
一向对搜刮、过滤很好奇,感觉他们很有技巧含量,只有很是NB的人才干做。很想知道他们的道理,实现如许的功能,设计是不是必须得很是NB很是独特,代码是不是要写得很是好,机能很是高。总之这一切都不是我如许级此外人能做的。直到我看了《编程珠玑(第二版)》中的这么一段文字:
“假定我们可以在履行搜刮之前对文本内容进行预处理惩罚,那么我们可以建树一个撒列表(或者搜刮树),为文档中的每个不合的单词建树索引,并为每个单词的每次呈现存储一个链表,如许的逆向索引使得法度可以很快的找到给定的单词,为了查找短语,我们可以对此中包含的每个单词的链表进行交叉,但实现起来斗劲错杂,速度可能会很慢。(不过一些网页搜刮引擎用的就是如许的办法)”
思路就这么简单,我靠!连有的搜刮引擎也用这种思路。这种撒列的体式格式处理惩罚关键字过滤速度的确是蛮快,10000个字组织成一个撒列表也就几毫秒,只要你预分派的内存较好,根蒂根基上没什么操纵,就是向内存中填数据。在撒列表中断定一个键是否存在的时候错杂度为O(1),其实还可以本身重写Dictionary<TKey, TValue>,关键字过滤的效力可能会更好点。
实现的思路斗劲简单:
1:处理惩罚关键字,生成一个关键字字典表
2:处理惩罚要过滤的文本,同样生成一个字典表
3:将文本,两个字典表三者进行比对
如今来测试下面一段文字(我上篇博客中的一段文字):
"看云风博客关于解决12306并发题目的启发:我如今做骏卡接口,可能呈现并发题目,就是一个订单可能向我们的接口发送多个恳求,而我如今做的办法是去数据库中对应的表验证,看订单是否存在,若是存在就提示一下,若是不存在按流程走,然则这个样每来一个订单我都须要去数据库查,若是我在内存中保护一个订单凑集,如许就能很快解决断定订单是否存在的题目,惯性思维太严重了,什么都去数据库查,如许的机能是最差的,其实很多题目在内存中就可以搞定的,比来还有一个希罕感触感染,不要做井底之蛙,多看牛人的器材收成真的比本身居心写代码进步快很多,其实很多时辰我写的法度机能差,效力低都是因为办法的原因,没有找到好的办法,没有灵光一闪的感触感染,用了最烂的办法解决题目"
测试代码:
class Program { static void Main(string[] args) { string keys = "云风博客|并发题目|最烂的办法|内存|凑集|数据库|机能"; using (new OperationTimer("keyWords:")) { WordSearch ws = new WordSearch(keys); string str = "看云风博客关于解决12306并发题目的启发:我如今做骏卡接口,可能呈现并发题目,就是一个订单可能向我们的接口发送多个恳求,而我如今做的办法是去数据库中对应的表验证,看订单是否存在,若是存在就提示一下,若是不存在按流程走,然则这个样每来一个订单我都须要去数据库查,若是我在内存中保护一个订单凑集,如许就能很快解决断定订单是否存在的题目,惯性思维太严重了,什么都去数据库查,如许的机能是最差的,其实很多题目在内存中就可以搞定的,比来还有一个希罕感触感染,不要做井底之蛙,多看牛人的器材收成真的比本身居心写代码进步快很多,其实很多时辰我写的法度机能差,效力低都是因为办法的原因,没有找到好的办法,没有灵光一闪的感触感染,用了最烂的办法解决题目"; ConsoleColor color = Console.ForegroundColor; Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine("原文:"); Console.ForegroundColor = color; Console.WriteLine(str); Console.WriteLine(); Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine("过滤后:"); Console.ForegroundColor = color; Console.WriteLine(ws.Filter(str)); } Console.Read(); }
}
输出成果截图:

别的奉上一个简单实用的代码运行时候测试类,测试某段代码的运行时候可是很便利的哦
using System; using System.Diagnostics;
namespace WordFilter { /// <summary> /// 测试代码运行时候帮组类 /// </summary> public class OperationTimer : IDisposable { private string Text; private Int32 collectCount; private Stopwatch stopWatch;
public OperationTimer(string txt) { PerpareForOperation(); this.Text = txt; collectCount = GC.CollectionCount(0); stopWatch = new Stopwatch(); stopWatch.Start(); }
public void Dispose() { stopWatch.Stop(); Console.WriteLine("{0} Milliseconds (GCs={1}) {2}", stopWatch.ElapsedMilliseconds, GC.CollectionCount(0) - collectCount, Text); }
private static void PerpareForOperation() { GC.Collect(); GC.WaitForPendingFinalizers(); GC.Collect(); } } }
实现撒列的项目组核心代码:
public Dictionary<char, IList<char>> HandleKeyWords(IEnumerable<string> text, int size) { Dictionary<char, IList<char>> dicList = new Dictionary<char, IList<char>>(size);//预分派很是关键 int len, i; foreach (string s in text) { if (s == string.Empty) { continue; } len = s.Length - 1; for (i = 0; i < len; i++) { if (dicList.ContainsKey(s[i])) { if (dicList[s[i]] != null && !dicList[s[i]].Contains(s[i + 1])) { dicList[s[i]].Add(s[i + 1]); } } else { dicList.Add(s[i], new List<char>(2) { s[i + 1] }); } } if (!dicList.ContainsKey(s[len])) { dicList.Add(s[len], null); } }
return dicList; }
我也想贴出全部代码,然则还有一些BUG,功能还有待完美,完美一些了会贴出源码的,在截一张图给大师看看

关键字过滤,欲望能过滤掉大师不想听的,陈太汉祝大师新年康乐
作者:陈太汉
博客:http://www.cnblogs.com/hlxs/
|