从数据结构分析看:用foreach...in比for...in要快些
之前听说火狐的JS引擎支持foreachin的语法,例如下述的代码:
vararr=[10,20,30,40,50];
foreach(varkinarr)
console.log(k);
即可直接遍历出arr数组的内容。
由于只有FireFox才支持,所以几乎所有的JS代码都不用这一特征。
不过在ActionScript里天生就支持foreach的语法,不论Array还是Vector,还是Dictionary,只要是可枚举的对象都可以forin和foreachin。
之前并没有感觉有太大的差异,为了懒得敲一个each单词,一直用熟悉的forin来遍历。
不过今天仔细琢磨了会,从数据结构的角度分析了下,觉得forin和foreachin效率上有着本质的区别,无论是JS还是AS。
原因很简单:Array不是真正意义上的数组!
何为真正意义的数组?当然就是传统语言里type[]定义的数据类型,所有元素都是连续保存的。
“Array”虽然也是数组的意思,但熟悉JS的都知道,它其实是个非线性的伪数组,下标可以是任意数字。写入arr[1000000]并非真正申请容纳一百万个元素的空间,而是把1000000转换成相应的哈希值,对应到很小一块储存空间里,从而节省了大量内存。
例如有如下数组:
vararr=[];
arr[10]=1000;
arr[20]=2000;
arr[30]=5000;
arr[40]=8000;
arr[200]=9000;
用for...in遍历Array,是个很累赘的过程:
遍历时每次访问arr[k],都要进行一次Hash(k)计算,根据散列表的容量取模,最终在冲突链表里找到结果。
如果支持foreach...in的语法,其内部的数据结构就决定了会快很多:
Array里储存存了keys的列表,也把每个values值作为链表关联起来。每当有值添加或删除,就更新其链接关系。
当foreach...in遍历时,只需从第一个节点往后迭代即可,无需任何Hash计算。
当然,对于AS3里Vector这样的线性数组来说,两者相差不大;同理,HTML5里支持二进制的数组ArrayBuffer也是如此。不过从理论上来看,即使arr是个连续的线性数组,foreachin还是要快一点:
for...in遍历时,每次访问arr[k]都要进行下标越界检查;而foreachin则根据内部链表,直接从底层反馈出迭代变量,节省了越界检查的过程。
相关文章
- redis数据结构基本语法
- 【数据结构其实真不难】算法分析
- 数据库系列 | MySQL索引数据结构算法
- 数据结构实验之求二叉树后序遍历和层次遍历(SDUT 2137)
- 数据结构实验之二叉树四:(先序中序)还原二叉树 (SDUT 3343)
- 【EventBus】EventBus 源码解析 ( 注册订阅者总结 | 从封装的数据结构角度分析 EventBus )
- 【Linux 内核 内存管理】内存映射相关数据结构 ② ( vm_area_struct 结构体成员分析 | vm_mm 成员 | vm_page_prot 成员 | vm_flags 成员 )
- 【Linux 内核 内存管理】内存映射相关数据结构 ③ ( vm_area_struct 结构体成员分析 | shared 成员 | anon_vma_chain 成员 | anon_vma 成员 )
- Redis数据结构之链表与字典的使用
- Spark项目之电商用户行为分析大数据平台之(七)数据调研–基本数据结构介绍详解大数据
- [C语言] 数据结构-算法效率的度量方法-事前分析估算方法详解编程语言
- 精通Redis:常用数据结构专题解析(redis常用数据结构)
- 形结构SQL Server查询树形数据结构的技巧分析(sqlserver查询树)
- 极致性能Redis高效数据结构图分析(redis高效数据结构图)
- Redis中集合数据结构的遍历实现(redis 集合遍历)