开了一天会,合作伙伴、项目申请、科研基金、最新动态、工程测试、专利申请、域名抢注、软件版权、人员调整、财务状况、未来进度……一大堆问题搞得身心疲惫,快下班时,大伙无意间议论起一个算法问题,这才感觉好玩起来,放松起来,记录之。(晚上又是应酬,给领导敬酒啊什么的,似乎这一整天,就这个问题的思考是个快乐的瞬间)
zf帮Boss H统计蛋白质数据库的数据分布情况,从上T数目的肽里,把拥有相同元素分子式的肽序列都归到一组(蛋白质或肽都是由碳、氢、氮、氧、硫五种元素组成的)。
以往zf是用哈希表做的,最初用前两位当key,后来进一步优化,用五种元素原子个数组成的向量来降维,但这样对付海量数据,速度还是太慢,程序一跑好几天。Boss H希望干脆把哈希变成一个map,也就是说,设计一种key,相同的元素分子式,有且只对应唯一个key。
Boss H是数学出身,所以首先想到一种很“数学”的办法,用五个素数作为基,例如2、3、5、7、11,然后取对应原子的个数的指数幂再连乘起来。例如,某个肽含有的碳、氢、氮、氧、硫原子数目依次有N1,N2,N3,N4,N5个,那么算出来的key就是2的N1次方,乘以3的N1次方,乘以5的N3次方,乘以7的N4次方,最后乘以11的N5次方。得到的每种不同的数字,自然就唯一代表着一种独特的元素组合方式。更妙的是,为防止这个数据过大,上溢,导致计算机无法处理,可以给它取log,连乘变成了连加,缺点是,对应的结果不再是整数,浮点判等会稍微麻烦一点。
俺是软件工程师,自然用很“工程”的办法,就是把碳、氢、氮、氧、硫的个数都变成0101的二进制串,然后依次排列起来(本质上,就是把N1,N2,N3,N4,N5依次乘以2的32、64、96、128、160次方,或者说把他们各自对应的0101二进制串依次左移动到合适的位置,再加起来),类似IP地址那样,比对是否相等时,直接用二进制掩码方式就能处理了。存在的小问题是,需要预先进行一个统计,搞清楚自然界里蛋白质分子中,碳、氢、氮、氧、硫各元素的原子数目的最大上限是多少,蛋白质是大分子,动不动成千上万的氨基酸链起来,必须保证二进制位数足够,不过这不算什么大问题,不够加长二进制串的长度就是了。
fy大侠匆忙间刚够听明白问题的确切意思,于是在最短时间里想出个最直观的办法,那就是用ASCII码文本连起来组成一个字符串作为 key,不同元素的原子个数之间用一个符号隔开,例如“31@24@11@13@1”,然后用字符串比对,现有的高效库和高效算法很多,还可以用后缀树这种经典的文本分析数据结构来进一步优化存储和增删改方式。
这么一个小问题,原来有这么多不同的招数,条条大路通罗马。思考是一件非常有乐趣的事。