打印

[奇招怪招专题]JS暴虐查找法

[奇招怪招专题]JS暴虐查找法

有过相关经验的朋友都知道,Jscript的效率毕竟有限,在数组中查找数据时如果用常规的算法来做执行起来会很慢。

例如在一个含500个字符串的data数组里,我们想要找到一个指定的字符(key),返回它的数组下标,如果用这样的算法:
复制内容到剪贴板
代码:
function usual_search(data,key)
{
var m=data.length
for(i=0;i<m;i++)
{if(data[i]==key)return i}
}
由于需要做多次的比较,运算起来会相当的慢。


本主题要介绍的是一种充分利用Jscript内置方法来实现在数组中查找数据的方法,由于借助Jscript内置方法,其效率要远优于上述常规算法。为了(诙谐|唬人)起见,我命其名为“JS暴虐查找法”。


这种查找法对于数组元素有一个要求:就是数组元素的内容不得包含半角逗号(,)及我们指定的某一个代置符号(例如,在下面的示例中,我们指定代置符号为一个制表符“┢”)。在事先构建、维护数组时要注意满足这一要求。


JS暴虐查找法的思路是非常简单的,原则只有一个,就是要“充分利用Jscript内置方法”:

       我们首先利用 Array 对象的 toString() 方法产生一个包含数组元素的字符串,在这个字符串中各数组元素由半角逗号(,)分隔的,所以我们事先要求数组元素的内容不得包含半角逗号。

       随后利用 String 对象的 replace() 方法将这个字符串中所包含的我们要找的关键字符串替换成我们指定的一种特殊符号(代置符号),一般选择一个不常用的字符来充当代置符号,在下面示例中我使用了一个制表符(┢),只要是能够确保不会在数组元素中出现的符号都可以充当代置符号。

       接下来就是我们最暴虐的一步了,还是用 replace() 方法,去除半角逗号(,)和代置符号(┢)以外的所有字符。统统去干净以后这个字符串就变成了一串半角逗号之中包含着一个代置符号(这模样:,,,,,,,,,,,,,,,,┢,,,,,,,,,)。

       最后,用 String 对象的 indexOf() 方法返回代置符号在这个字符串中的位置,而这个位置恰恰也就是在原来数组中的数组下标。

Jscript示例程序

 提示:您可以先修改部分代码再运行
不应该忽略的是:是脚本执行非内置算法代码的低效率使得这个JS暴虐查找法有意义。
本帖最近评分记录
[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群:45274013
这种思路不错。
Myjs(唉!)
我靠!厉害的。很搞笑的查找方法!!佩服
不错,此外那个话题列表很有价值。

BLUEIDEA不愧是国内No1!!!!

TOP

还在为头像烦恼?还在为不能关注好友动态烦忧?快来蓝色理想家园吧!
牛X~
UpUpCN 中国团购 参与组织团购的凝聚地√

TOP

子乌版JS暴虐查找:

 提示:您可以先修改部分代码再运行
---------------------------
2006.02.16 update:
原来的代码没进行边界测试。。。现在改了一下,暂时无错~
by Sheneyan
子叶:子乌的叶子
帅哥们,美女们,新的一年终于来了,祝贺你们...终于又老了一岁~

TOP

子乌的更暴虐!!

省掉了正则,减少了一个附加条件(代置符号)。
[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群:45274013

TOP

有没有统计在什么条件下效率好?好多少?

TOP

试了一下,的确是快了不少,含3000个字符串的数组,平均快了800ms。bound0版和Sheneyan版的效果差不多。
熟红

TOP

这样限制少一些 ...:P
复制内容到剪贴板
代码:
<script>
var testdata =
['就在','你的','目光','尽头,','懵懂','的天','使单',
'纯如','旧,挣','扎着','不肯','涉入','俗流,','鸿鹄','借走','了他','的翅','膀,可',
'有谁','能助','他','飞翔?'];
var _idx = testdata.join('┢').split('┢鸿鹄')[0].split('┢').length;
alert(_idx);
</script>

TOP

谁能做一个比较呢,用这两种和原始的方法,把时间统计出来。
给出一个这种方法的的选用范围,因为数组不太长的话,就没必要用它了。

TOP

这样的算法有什么应用价值吗?各位高人能不能列举一二。

TOP

先收下,以后慢慢研究

TOP

参杂了人为因素
使用起来并不那么应手

TOP



 提示:您可以先修改部分代码再运行
没看清楚是老帖.....

[ 本帖最后由 让你笑了 于 2006-11-28 10:41 编辑 ]
桃花运啊桃花劫...

TOP

JS暴虐查找法 最终改良版

10楼、和15楼和子乌的方法原理一样,改良了分隔符号,但忽略了要保证匹配内容完整的问题,在查找数组内容的子字符串时也会返回位置。

最终改良版

 提示:您可以先修改部分代码再运行
因为JavaScript执行很慢,用穷举搜索的话,如果数组相当大就会运行比较久的时间。然而JavaScript的内置方法相对来说速度很快。所以对于大数组来说就可以采用这种称为“JS暴虐查找”的技巧。

P.S.例子里这首诗是我的原创,某个时期的心情写照啊。还有若干句来着,已然不记得了……

[ 本帖最后由 bound0 于 2008-7-17 20:42 编辑 ]
[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群:45274013

TOP

很好很强大的思路.
ps: 那首诗貌似读着没意境...

TOP

为什么gecko引擎的浏览器没有反应呀,IE和opera正常,是gecko引擎的错。

TOP