0
0

记一个工作中遇到的问题

杨靖 发表于 2014年09月23日 19:30 | Hits: 2287

一年没有写博客了,写一个我今年在工作中遇到的问题吧。

首先有一个字符串集合A(母串集),A中大概有1.6x1010个字符串。这些字符串大部分都比较短,长度小于100。最长的字符串有216个字符。

还有一个比较小的字符串集合B(子串集)。B里的每个字符串都是A里某个字符串的前缀,共有2.4x107个前缀。B中的每个字符串都与一个非负整数相关联。

现在对于A中的每个字符串a_i,求一个整数。这个整数等于B中所有a_i的前缀所对应的整数的最大值。

(之前已经听我白话过这个问题的同学们:是的,问题规模又扩大了。)

背景:A是数据的key集合,B是用户的删除数据请求,删除被匹配的key和它对应的数据。因此,最后A中被匹配到的字符串不会特别多,大约是B的大小的若干倍。可以认为远小于100倍。

看到这个问题的规模,我们就知道只能跑在一台机器上的算法是不行的。必须设计一个能并行地跑在许多台机器上的算法。

这个问题的规模如果小一点,就相当容易解决。例如,如果B中的字符串少一点,少到2.4x104个。我们就可以把B做成一个Trie直接扔到内存里。准备若干台机器,每台机器都复制一份。给每台机器分配A的一段,各自扫描就好了。这样的复杂度是length(sigma A + sigma B)的。可能会比较占内存,但是现在内存都是白菜价了, who cares。

如果B再大一点点,大到2.4x106,问题也不是那么难。我们可以:

  1. 把B分成一百份,每次用上述方法处理一份,处理一百次;
  2. 或者,找一份可以放在硬盘上的Trie实现(假设能找得到)。Trie的每次查询只用到整个Trie的很小一部分。实现时只需要把查询时能访问到的部分装载到内存里,访问不到的swap到硬盘上就可以了。如果性能不足,还可以把4个byte压缩成一个long,既减少硬盘读写又减少空间浪费。
  3. 再或者两种方案结合,把B分成10份,每次用硬盘Trie处理一份。即使用最烂的(我的)实现,Trie文件的大小也不过几十G,可以接受。

但是拆分B的方案不能把B拆成太多份。因为每拆一份B都要把A复制一份,也就意味着多一份的数据读写。不幸的是我司的storage层对许多个并行读者的支持并不好,过多读者会导致大家都读得更慢。B如果再大,拆分的方法就不好用了。

大家有什么想法?我的答案在下面,不要偷看哦。




答案分割线



解决方案其实很简单,相信大家也都想到了:hash。

对集合B里的每一个子串,hash它长度为2的整数次幂的最长前缀 。如果一个串的长度为19,就hash前16个字符;如果长度是32,就hash所有字符。这样我们得到了2.4x107个long,大约占192M内存(我是不是算错了….对这个数字没什么信心)。

把这些hash值扔到一个数组b_hash_set里,排序之。

对于集合A里的每个母串,hash它的每个 长度为2的整数次幂的前缀 。对于每个字符串a_i,我们会得到log(length(a_i))个数字。称这些hash值的集合为a_hash_set。 如果a_hash_set和b_hash_set中的某一对数字a_hash和b_hash相等,他们分别对应的母串和子串才有可能 前缀匹配。就不证明了,结论非常明显。

这时再暴力匹配有可能的字符串对,运行时间就完全可以接受了。

一个小优化:在生成a_hash_set的一个值的时候,可以直接在b_hash_set里二分查找这个值。如果不存在,就不用把它放到a_hash_set里了。这样可以显著减小a_hash_set(以及和它关联的数据)的体积。在实践中,优化后a_hash_set的体积缩小了三百倍。

如何找到所有相等的a_hash和b_hash对?把它们扔到一起sort就可以了。a_hash_set的体积可能会特别大,但是我们也有分布式排序算法嘛。

后话

上次在群里跟大家讨论的时候,范神@ronaflx提到,他们判断整个字符串相等的时候都会先算hash,然后暴力匹配。我当时还觉得,暴力就暴力吧,hash能有什么作用?仔细一想,使用hash,子串和母串都只需要扫描一遍;而且hash本身的体积比字符串小很多,比较容易传递。在这里顺便感谢范神给我普及字符串匹配基础知识。

但是hash只能判断相等(严格来说,只能确定不等),不能判断前缀。一个常见的workaround是把母串的所有前缀都hash了,再和子串的hash比。这样的方案在母串都不长的情况下很适用。但是在这个问题上,这样做会在时间复杂度上乘一个一百左右的常数。要减小常数,只处理2的整数次幂也是常见workaround:牺牲部分精度(子串的一部分被忽略了),但是可以把常数从100减少到6。

最后,欢迎大家提出更好的方法来打脸!

吐槽

Java的TreeSet存2.4x107个数,居然要占用10多G内存!你丫是暴力数组实现的Trie吧!

下次给自己的service设计功能的时候,一定要先想想到底能不能高效实现。堂堂大Google,若干M个请求都处理不好,混不混了!

感慨

本文就是我今年工作最大的成绩了。进入Google一年,蹉跎一年,一事无成,Todo List 基本没有刷,能力进步为零。

逆水行舟,不进则退。与君共勉!

原文链接: http://ditsing.com/blog/2014/09/23/ji-yi-ge-gong-zuo-zhong-yu-dao-de-wen-ti/

0     0

评价列表(0)