流言终结：JS字符搜索的飞雷神之术？

作为开发者，在编程时，难免要在网上查找、参考各种资料。

近日，在用JavaScript实现一个功能时，要在海量数据中查找字符。

网上一搜，发现介绍一种称为“飞雷神之术”的超快算法，其原理是：利用树状数组完成海量数据瞬间检索，据说其效率远超indexof、正则表达式等搜索方式。

飞雷神之术：在《火影忍者》中，第二代火影千手扉间开发的超高等空间忍术，利用术式达到瞬间移动，施术者会事先在目标上留下飞雷神术式，即可使施术者对接触物进行瞬间移动。

据该算法介绍，上述的快速检索算法，与此描述有一定神似，同样是事先对目标数据进行预处理，处理之后便可实现瞬间检索的效果。

真有这么神奇吗？

抱着三分期待，七分疑惑。进行了本文的测试。

直接说结果：流言。

给出测试数据：

一千万条数据中搜索，indexof用时128毫秒，正则用时，0.3毫秒，网传算法用时：9.7毫秒。最快的是正则匹配。

一万条数据中搜索，indexof用时1.1毫秒，正则用时0.2毫秒，网传算法用时2.5毫秒。正则最快、网传最慢。

中间，还测试了在其它不同量级的数据中搜索，结果都证明该网传算法毫无优势，实属流言。

以下，再附上该“飞雷神”算法，及本文测试时使用的代码：

function demo_init(count){

var str = "";

for(i=0; i<count; i++){

str = str + rnd_str() + ",";

}

var str_array = str.split("");

var tree_root = {};

var tree_sub = {};

var key;

for(var i=0; i<str_array.length; i++){

key = str_array[i];

//以,作为分隔标识

if(key == ','){

//遇到,则sub等于全部root树对象

tree_sub = tree_root;

continue;

}

if(key in tree_sub){

//某个子节点下的节点

tree_sub = tree_sub[key];

//console.log("已存在子节点",key,tree_sub);

}else{

tree_sub[key] = {};

//console.log("创建了新的节点",key);

}

}

//console.log("最终",JSON.stringify(tree_root));

return tree_root;

}

function rnd_str(){

var str = "";

var str_length = 4;

var rnd_word = new Array(1,2,3,4,5,6,7,8,9,'a','b','c','d','e','f','g','h','i','j','k','x','m','n','c','p','q','r','s','t','u','v','w','x','y','z');

for(var i = 0; i < str_length; i++){

var charNum = Math.floor(Math.random() * 32);

str += rnd_word[charNum];

}

return str;

}

function search(tree_root,content){

var tblCur;

var i = 0;

var n = content.length;

var p, v;

var arrMatch = [];

while(i < n){

tblCur = tree_root;

p = i;

v = 0;

for(;;){

//返回指定位置的字符

if(!(tblCur = tblCur[content.charAt(p++)])){

i++;

break;

}

//匹配到了

if(JSON.stringify(tblCur) == "{}"){

v = p;

}

}

if(v){

arrMatch.push(i-1, v);

i = v;

}

}

return arrMatch;

}

console.log("一千万条数据中搜索");

var str = "";

for(i=0; i<10000000; i++){

str = str + rnd_str() + ",";

}

console.time("indexof用时");

var indexof_result = str.indexOf("abcd");

console.log(indexof_result)

console.timeEnd("indexof用时");

console.time("regexp用时");

var test_result = /abcd/.test(str);

console.log(test_result);

console.timeEnd("regexp用时");

var tree = demo_init(10000000);

console.time("飞雷神用时");

var serach_result = search(tree,"abcd");

console.log(serach_result);

console.timeEnd("飞雷神用时");

九七分享吧所有文章来源于网络收集整理，如有侵权请联系QQ2387153712删除，如果这篇文章对你有帮助或者还不错的请给小编点个小赞(◠‿◠)，小编每天整理文章不容易(ಥ_ಥ)！！！