转:比较JavaScript中的集合及其检索效率

转自:鸟食轩

数组是JavaScript提供的一个内部对象,它是一个标准的集合,我们可以添加(push)、删除(shift)里面元素,我们还可以通过for循环遍历里面的元素,那么除了数组我们在JavaScript里还可以有别的集合吗?

由于JavaScript的语言特性,我们可以向通用对象动态添加和删除属性。所以Object也可以看成是JS的一种特殊的集合。下面比较一下Array和Object的特性:

Array:

新建:var ary = new Array(); 或 var ary = [];
增加:ary.push(value);
删除:delete ary[n];
遍历:for ( var i=0 ; i <ary.length ; ++i ) ary[i];

Object:

新建:var obj = new Object(); 或 var obj = {};
增加:obj[key] = value; (key为string)
删除:delete obj[key];
遍历:for ( var key in obj ) obj[key];

从上面的比较可以看出Object完全可以作为一个集合来使用,在使用Popup窗口创建无限级Web页菜单(3)中我介绍过Eric实现的那个__MenuCache__,它也就是一个模拟的集合对象。

如果我们要在Array中检索出一个指定的值,我们需要遍历整个数组:

var keyword = ;
for ( var 
i=ary.length ; ++)
{
    if ( 
ary[i] == keyword )
     {
         
// todo
    
}

而我们在Object中检索一个指定的key的条目,只需要是要使用:

var key '';
 var 
value obj[key];
 
// todo 

Object的这个特性可以用来高效的检索Unique的字符串集合,遍历Array的时间复杂度是O(n),而遍历Object的时间复杂度是O (1)。虽然对于10000次集合的for检索代价也就几十ms,可是如果是1000*1000次检索或更多,使用Object的优势一下就体现出来了。在此之前我做了一个mapping,把100个Unique的字符mapping到1000个字符串数组上,耗时25-30s!后来把for遍历改成了 Object模拟的集合的成员引用,同样的数据量mapping,耗时仅1.7-2s!!!

对于集合的遍历效率(从高到低):var value = obj[key]; > for ( ; ; ) > for ( in )。效率最差的就是for( in )了,如果集合过大,尽量不要使用for ( in )遍历。

4 Comments »

  1. autoinsurance said,

    December 20, 2006 @ 12:41 pm

    postprocess!exacerbates,petitioning barometer insuring layman mountaineer

  2. auto insurance austin auto insurance comparisons said,

    December 23, 2006 @ 6:34 pm

    necking.coyote.spooled:averred Negroization shrinkage responsibleness .

  3. login said,

    December 25, 2006 @ 11:29 am

    My English not so good but thank for lovely site with information I looking for and need also.

  4. ESSAM said,

    June 14, 2010 @ 7:08 pm

    I am interested for the upu-0.21 uploader but can’t read the readme file because it was in china language can u translate it to english & send it to my e-mail ?

    功能列表
    - 理论上可以上传无限大的文件
    - 实时显示上传状态、进度
    - 支持多文件上传以及与表单混合上传
    - 方便的用户调用接口
    - 兼容不同浏览器
    - …

    调用方法:
    1.下载upub0.2.rar, 将里面的upu目录解压到网站某一目录下。将upu/temp/, upu/files
    的目录权限改为755

    2.打开upu/misc/upu.js, 修改var basePath = “/upload/upu/”; 为upu相对于网站根目
    录的路径

    3.然后在包含上传表单的页面中加入
    ,这里的
    upu/misc/upu.js为upu.js的路径,然后在标签中加入
    onsubmit=”return upuInit(this)”

    4.在你文件上传后处理的页面中使用$_POST来获取表单数据

    注意:
    1. UPU需要php4.3.0及其以上版本,并打开socket扩展

    2. upu/temp为上传临时文件存放目录, upu/files为文件存放目录,这两个目录可以在
    upu.class.php中指定。

    3. 你的中要有enctype=”multipart/form-data”这个属性,action为文件上传成功后
    的处理页面,也就是说你的完全按照正常的思路来写就可以了,唯一不同的是需
    要加入onsubmit=”return upuInit(this)”

    4. 上传成功后,可以使用$_POST来获取表单数据,如果是普通表单,直接
    $_POST['表单名称']即可获得其值,如果是一个文件,则返回这样一个数组
    $_POST['表单名字'] = Array (
    [filename] =>
    [clientpath] =>
    [savepath] =>
    [filetype] =>
    [filesize] =>
    [extension] =>
    )

    4. 本程序为自由软件;您可依据自由软件基金会所发表的GNU通用公共授权条款规定,就本
    程序再为发布与/或修改.本程序是基于使用目的而加以发布,然而不负任何担保责任;
    亦无对适售性或特定目的适用性所为的默示性担保。详情请参照GNU通用公共授权。
    http://gnu.freehostingguru.com/gpl/

    author: legend
    website: http://www.ugia.cn

RSS feed for comments on this post

Leave a Comment