(点选下方社会公众号,可加速高度关注)
来源:枕边书
www.cnblogs.com/zhenbianshu/p/7197349.html
难题来历
博纳瓦县工作中碰到一个难题:
有 60万 条短最新消息历史记录笔记,每条约 50 字,5万 关键字,宽度 2-8 字,绝大部分为英文。明确要求将这 60万 条历史记录中包含的关键字全部抽取出来并统计数据各关键字的投弹单次。
责任编辑完整如是说了我的同时实现方式,看我如何将需要运行十半小时的各项任务强化到五分钟以内。尽管同时实现词汇是 PHP,但责任编辑如是说的更多的思想,应该能给大家一些帮助。
原初 – grep
结构设计
一已经开始接到各项任务的时候,我的小心思立刻转了起来,笔记 + 关键字 + 统计数据,我没有想不到自己写标识符同时实现,而要首先想不到了 linux 下常用的笔记统计数据指示 grep。
grep指示的用语无须多提,采用 grep keyword | wc -l 可以很方便地进行统计数据关键字投弹的信息INS13ZD,而php的 exec() 表达式允许我们直接初始化 linux 的 shell 指示,尽管这样执行危险指示时能有隐患。
标识符
上伪标识符:
foreach($word_list as$keyword){
$count = intval(exec("grep {$keyword} file.log | wc -l"));
record($keyword,$count);
}
在两台老电脑上跑的,话说老电脑效率真的差,跑了6半小时。估计最新电脑2-3半小时吧,后面的强化都采用的新电脑,所以需求又有变动,节录才就此结束。
原初,原初在设想和方法。
变异 – 二阶
结构设计
交了差之后,第二天产品又提出了捷伊设想,说以后想把某管理工具网络连接进来,最新消息以报文的形式传递,而无须是文档了。所以还明确要求了最新消息统计数据的保密性,一下把我想把数据写到文档再统计数据的设想也废黜了,为了方案的扩展性,现在的统计数据对象无须是一个整体,而要要考虑拿n个INS13ZD的最新消息来相匹配了。
这时,略懵的我只好卷土重来了最传统的工具- 二阶。二阶的同时实现也无从,各个词汇也都PCB好了二阶相匹配表达式,重点是商业模式(pattern)的构筑。
当然这儿的商业模式构筑也无从,/keyword1|keword2|.../,用|将关键字相连接即可。
二阶大坑
这儿如是说两个采用中碰到的大坑:
二阶商业模式宽度太短引致相匹配失败:PHP 的二阶有追述管制,以防止释放出来所有的进程可用栈, 最终引致 php 崩盘。太短的商业模式会引致 PHP 检测到追述过多,受阻相匹配,经测试自动更新时最小商业模式宽度为 32000 二进制 左右。php.ini 内 pcre.backtrack_limit参数为最小追述单次管制,缺省为 1000000,修改或 php.ini 或在脚本已经开始时采用 ini_set(‘pcre.backtrack_limit’, n); 将其设置为一个较大的数可以提高单次相匹配最小商业模式宽度。当然也可以将关键字分批统计数据(我用了这个=_=)。
商业模式中含有特殊字符引致大量warning:相匹配过程中发现 PHP 报出大量 warning:unknown modifier 乱码,仔细检查发现关键字中有/字符,可以采用preg_quote()表达式过滤一遍关键字即可。
标识符
上伪标识符:
$end = 0;
$step = 1500;
$pattern = array();
// 先将pattern 拆成多个小块
while($end < count($word_list)){
$tmp_arr = array_slice($word_list,$end,$step);
$end += $step;
$item = implode(|,$tmp_arr);
$pattern[] = preg_quote($item);
}
$content = file_get_contents($log_file);
$lines = explode("\n",$content);
foreach($lines as$line){
// 采用各小块pattern分别相匹配
for($i = 0;$i < count($pattern);$i++){
preg_match_all("/{$pattern[$i]}/",$line,$match);
}
$match = array_unique(array_filter($match));
dealResult($match);
}
为了完成各项任务,硬着头皮进程跑了一夜。当第二天我发现跑了近十个半小时的时候内心是崩盘的。。。太慢了,完全达不到采用明确要求,这时,我已经已经开始考虑改换方法了。
当产品又改换了关键字策略,替换了一些关键字,明确要求重新运行一遍,并表示还会继续强化关键字时,我完全否定了现有方案。绝对不能用关键字去相匹配信息,这样一条一条用全部关键字去相匹配,效率实在是不可忍受。
变异,需求和同时实现的变异
觉醒 – 拆词
结构设计
我终于已经开始意识到要拿信息去关键字里对比。如果我用关键字为键建立一个 hash 表,用信息里的词去 hash 表里查找,如果查到就认为相匹配投弹,这样不是能达到 O(1) 的效率了么?
可是一条短最新消息,我如何把它拆分为刚好的词去相匹配呢,分词?分词也是需要时间的,所以我的关键字都是些无语义的词,构筑词库、采用分词工具又是很大的难题,最终我想不到 拆词。
为什么叫拆词呢,我考虑以蛮力将一句话拆分为所有可能的词。如(我是好人)就可以拆成(我是、是好、好人、我是好、是好人、我是好人)等词,我的关键字宽度为 2-8,所以可拆词个数会随着句子宽度迅速增加。不过,可以用标点符号、空格、语气词(如的、是等)作为分隔将句子拆成小短语再进行拆词,会大大减少拆出的词量。
其实分词并没有完整同时实现就被后一个方法替代了,只是一个极具同时实现可能的构想,写这篇文章时用伪标识符同时实现了一下,供大家参考,即使不用在相匹配关键字,用在其他地方也是有可能的。
标识符
$str_list = getStrList($msg);
foreach($str_list as$str){
$keywords = getKeywords($str);
foreach($keywords as$keyword){
// 直接通过PHP数组的哈希同时实现来进行加速查找
if(isset($word_list[$keyword])){
record($keyword);
}
}
}
/**
* 从最新消息中拆出短句子
*/
functiongetStrList($msg){
$str_list = array();
$seperators = array(,,。,的,...);
$words = preg_split(/(?<!^)(?!$)/u,$msg);
$str = array();
foreach($words as$word){
if(in_array($word,$seperators)){
$str_list[] = $str;
$str = array();
}else{
$str[] = $word;
}
}
returnarray_filter($str_list);
}
/**
* 从短句中取出各个词
*/
functiongetKeywords($str){
if(count($str) < 2){
returnarray();
}
$keywords = array();
for($i = 0;$i < count($str);$i++){
for($j = 2;$j < 9;$j++){
$keywords[] = array_slice($str,$i,$j);// todo 管制一下不要超过数组最小宽度
}
}
return$keywords;
}
结果
我们知道一个 utf-8 的英文字符要占用三个二进制,为了拆分出包含中英文的每一个字符,采用简单的 split() 表达式是做不到的。
这儿采用了 preg_split(/(?<!^)(?!$)/u, $msg) 是通过二阶相匹配到两个字符之间的来将两个字符拆散,而两个括号里的 (?<!^)(?!$) 是分别用来限定捕获组不是第一个,也不是最后一个(不采用这两个捕获组限定符也是可以的,直接采用//作为商业模式会引致拆分结果在前后各多出一个空字符串项)。 捕获组的概念和用语可见我之前的博客 PHP二阶中的捕获组与非捕获组
由于没有真正同时实现,也不知道效率如何。估算每个短句宽度约为 10 字左右时,每条短最新消息约50字左右,会拆出 200 个词。尽管它会拆出很多无意义的词,但我相信效率绝不会低,由于其 hash 的高效率,甚至我觉得会可能比终极方法效率要高。
最终没有采用此方案是因为它对句子明确要求较高,拆词时的分隔符也不好确定,最重要的是它不够优雅。。。这个方法我不太想去同时实现,统计数据标识和语气词等活显得略为笨重,所以感觉拆出很多无意义的词感觉效率浪费得厉害。
觉醒,意识和思路的觉醒
终级 – Trie树
trie树
于是我又来找谷哥帮忙了,搜索大量数据相匹配,有人提出了 采用 trie 树的方式,没想不到刚学习的 trie 树的就派上了用场。我上上篇文章刚如是说了 trie 树,在空间索引 – 四叉树 里字典树这一小节,大家可以查看一下。
当然也为懒人复制了一遍我当时的解释(看过的可以跳过这一小节了)。
字典树,又称前缀树或 trie 树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而要由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。
我们可以类比字典的特性:我们在字典里通过拼音查找晃(huang)这个字的时候,我们会发现它的附近都是读音为huang的,可能是声调有区别,再往前翻,我们会看到读音前缀为huan的字,再往前,是读音前缀为hua的字… 取它们的读音前缀分别为 h qu hua huan huang。我们在查找时,根据 abc...xyz 的顺序找到h前缀的部分,再根据 ha he hu找到 hu前缀的部分…最后找到 huang,我们会发现,越往后其读音前缀越长,查找也越精确,这种类似于字典的树结构就是字典树,也是前缀树。
结构设计
那么 trie 树怎么同时实现关键字的相匹配呢? 这儿以一幅图来讲解 trie 树相匹配的过程。
其中要点:
构造trie树
将关键字用上面如是说的preg_split()表达式拆分为单个字符。如科学家就拆分为科、学、家三个字符。
在最后一个字符后添加一个特殊字符`,此字符作为一个关键字的结尾(图中的粉红三角),以此字符来标识查到了一个关键字(不然,我们不知道相匹配到科、学两个字符时算不算相匹配成功)。
检查根部是否有第一个字符(科)节点,如果有了此节点,到步骤4。 如果还没有,在根部添加值为科的节点。
依次检查并添加学、家 两个节点。
在结尾添加 ` 节点,并继续下一个关键字的插入。
相匹配
然后我们以 这位科学家很了不起!为例来发起相匹配。
首先我们将句子拆分为单个字符 这、位、...;
从根查询第一个字符这,并没有以这个字符开头的关键字,将字符“指针”向后移,直到找到根下有的字符节点科;
接着在节点科下寻找值为 学节点,找到时,结果子树的深度已经到了2,关键字的最短宽度是2,此时需要在学结点下查找是否有`,找到意味着相匹配成功,返回关键字,并将字符“指针”后移,如果找不到则继续在此结点下寻找下一个字符。
如此遍历,直到最后,返回所有相匹配结果。
标识符
完整标识符我已经放到了GitHub上:Trie-GitHub-zhenbianshu,这儿放上核心。
首先是数据结构树结点的结构设计,当然它也是重中之重:
$node = array(
depth => $depth,// 深度,用以判断已投弹的字数
next => array(
$val => $node,// 这儿借用php数组的哈希底层同时实现,加速子结点的查找
...
),
);
然后是树构筑时子结点的插入:
// 这儿要往节点内插入子节点,所以将它以引用方式传入
privatefunctioninsert(&$node,$words){
if(empty($words)){
return;
}
$word = array_shift($words);
// 如果子结点已存在,向子结点内继续插入
if(isset($node[next][$word])){
$this->insert($node[next][$word],$words);
}else{
// 子结点不存在时,构造子结点插入结果
$tmp_node = array(
depth => $node[depth] + 1,
next => array(),
);
$node[next][$word] = $tmp_node;
$this->insert($node[next][$word],$words);
}
}
最后是查询时的操作:
// 这儿也可以采用一个全局变量来存储已相匹配到的字符,以替换$matched
privatefunctionquery($node,$words, &$matched){
$word = array_shift($words);
if(isset($node[next][$word])){
// 如果存在对应子结点,将它放到结果集里
array_push($matched,$word);
// 深度到达最短关键字时,即可判断是否到词尾了
if($node[next] > 1 && isset($node[next][$word][next][`])){
returntrue;
}
return$this->query($node[next][$word],$words,$matched);
}else{
$matched = array();
returnfalse;
}
}
结果
结果当然是喜人的,如此相匹配,处理一千INS13ZD据只需要3秒左右。找了 Java 的同事试了下,Java 处理一千INS13ZD据只需要1秒。
这儿来分析一下为什么这种方法这么快:
二阶相匹配:要用所有的关键字去信息里相匹配相匹配单次是 key_len * msg_len,当然二阶会进行强化,但基础这样,再强化效率可想而知。
而 trie 树效率最差的时候是 msg_len * 9(最长关键字宽度 + 1个特殊字符)次 hash查找,即最长关键字类似 AAA,信息内容为 AAA...时,而这种情况的概率可想而知。
至此方法的强化到此结束,从每秒钟相匹配 10 个,到 300 个,30 倍的性能提升还是巨大的。
终级,却不一定是终极
他径 – 多进程
结构设计
相匹配方法的强化结束了,开头说的强化到五分钟以内的目标还没有同时实现,这时候就要考虑一些其他方法了。
我们一提到高效,必然想不到的是 并发,那么接下来的强化就要从并发说起。PHP 是单线程的(尽管也有不好用的多线程扩展),这没啥好的解决办法,并发方向只好从多进程进行了。
那么一个笔记文档,用多个进程怎么读呢?这儿当然也提供几个方案:
进程内添加笔记行数计数器,各个进程支持传入参数 n,进程只处理第 行数 % n = n的笔记,这种 hack 的反向分布式我已经用得很熟练了,哈哈。这种方法需要进程传参数,还需要每个进程都分配读取整个笔记的的内存,所以也不够优雅。
采用 linux 的 split -l n file.log output_pre 指示,将文档分割为每份为 n 行的文档,然后用多个进程去读取多个文档。此方法的缺点就是不灵活,想换一下进程数时需要重新切分文档。
采用 Redis 的 list 队列临时存储笔记,开启多个进程消费队列。此方法需要另外向 Redis 内写入数据,多了一个步骤,但它扩展灵活,所以标识符简单优雅。
最终采用了第三种方式来进行。
结果
这种方式尽管也会有瓶颈,最后应该会落在 Redis 的网络 IO 上。我也没有闲心开 n 个进程去挑战公司 Redis 的性能,运行 10 个进程三四分钟就完成了统计数据。即使再加上 Redis 写入的耗时,10分钟以内也妥妥的。
一已经开始产品对相匹配速度已经有了半小时级的定位了,当我 10 分钟就拿出了捷伊笔记相匹配结果,看到产品惊讶的表情,心里也是略爽的,哈哈~
他径,也能帮你走得更远
总结
解决难题的方法有很多种,我认为在解决各种难题之前,要了解很多种知识,即使只知道它的作用。就像一个工具架,你要先把工具尽量摆得多,才能在碰到难题时选取一个最合适的。接着当然要把这些工具用是纯熟了,这样才能采用它们去解决一些怪异难题。
工欲善其事,必先利其器,要想解决性能难题,掌握系统级的方法还略显不够,有时候换一种数据结构或算法,效果可能会更好。感觉自己在这方面还略显薄弱,慢慢加强吧,各位也共勉。
看完责任编辑有收获?请分享给更多人
高度关注「Linux 爱好者」,提升Linux技能
请立即点击咨询我们或拨打咨询热线: ,我们会详细为你一一解答你心中的疑难。项目经理在线