首页 > 代码库 > 变位词的查找(下)
变位词的查找(下)
本文也同步发表在我的公众号“我的天空”
实现方案优劣的思考
之前我们的实现方案的优点是一旦目标词库的签名建立后,则变位词的查找会变得简单而快速;缺点是由于在生成目标词库时,要为每个词都生成签名,导致生成词库的时间会变慢,同时会消耗空间。对于那些没有被查找到的字符串的签名实际上是浪费的。
测试结果:在CPU为Inter Core i3-2328M,内存为6GB的PC上生成数量为1万的目标词库平均时间为377毫秒,查找变位词的平均时间为11毫秒。
第二种方案
在生成目标词库的时候并不生成签名,而是在查找的时候生成签名。
function search(str){
var mathstr="";
for(var x in array_str){
//查找时生成签名,再判断签名是否相同
if(get_sign(str)==get_sign(array_str[x])){
mathstr+=mathstr.length==0?array_str[x]:","+array_str[x];
}
}
return mathstr; //返回找到的变位词}
测试结果:生成数量为1万的目标词库平均时间为130毫秒,查找变位词的平均时间为530毫秒。
该方案虽然提高了生成目标词库的速度,并节省空间,但是查找的速度太慢,与第一种方案相比较慢了约50倍。分析代码发现每次查找都需要为目标词库重新建立一遍签名,效率太过低下,考虑优化。
第二种方案的优化
针对第二种方案的不足之处,考虑做如下优化:如果两个词互为换位词,那么这两个词的长度必定相同,同时组成这两个词的字母的asscii编码之和也必定相同,因此在遍历目标词库时,首先判定这两个条件,如果满足则再获取其签名来作比较。获取字母的ascii编码采用charCodeAt()函数。
function search(str){
var mathstr="";
for(var x in array_str){
//如果两个词互为变位词,那么这两个词的长度和各字母的asciicode之和必须相同
if(str.length==array_str[x].length && get_asciicode_total(str)==get_asciicode_total(array_str[x])){
//查找时判断签名是否相同
if(get_sign(str)==get_sign(array_str[x])){
mathstr+=mathstr.length==0?array_str[x]:","+array_str[x];
}
}
}
return mathstr;
}
//获得字符串的ascii码之和
function get_asciicode_total(str){
var data=http://www.mamicode.com/str.split("");
var i=0;
for(var x in data){
i+=data[x].charCodeAt();
}
return i;
}
经测试,优化后的查找速度平均为43毫秒,速度提升还是很有效果的!
总结
该题主要是偏向于对问题的思考、解决方案的制定、实现与选择、代码优化等方面,在实际工作中,往往一个问题的解决会有多套方案,大家应该学会从各方面来衡量、测试,最终选择解决的问题的最优方案。该题主要涉及到随机数的操作、排序算法的掌握、ascii编码的掌握。
当然,以上两种方案仍有优化的空间,对于第一种,可以考虑将签名数组按照签名来排序,这样就无需每次都遍历整个签名数组,如果生成的目标词库数量巨大,还可以考虑将签名数组分段索引,以便能更快的找到签名;对于第二种,可以将查找中已生成的签名保存下来,这样下次查找再遇到该字符串该就无需再生成签名了,因为在整个程序中,最影响性能的就是生成签名,我们应尽量减少生成签名的操作。
示例代码
https://github.com/panyongwow/anagram
变位词的查找(下)