首页 > 代码库 > 变位词的查找(下)

变位词的查找(下)

本文也同步发表在我的公众号“我的天空

 

技术分享

实现方案优劣的思考

 

之前我们的实现方案的优点是一旦目标词库的签名建立后,则变位词的查找会变得简单而快速;缺点是由于在生成目标词库时,要为每个词都生成签名,导致生成词库的时间会变慢,同时会消耗空间。对于那些没有被查找到的字符串的签名实际上是浪费的。

 

测试结果:在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

变位词的查找(下)