插入数据

有如下两个方法:

  1. /**
  2.  * 从队首插入数据
  3.  */
  4. function unshiftFn() {
  5.     const a = []
  6.     console.time('unshift')
  7.     for (var i=0;i<100000;i++) {
  8.         a.unshift(1);
  9.     }
  11.     console.timeEnd('unshift')
  12. }
  14. /**
  15.  * 从队尾添加数据
  16.  */
  17. function pushFn() {
  18.     const a = []
  19.     console.time('push')
  20.     for (var i=0;i<100000;i++) {
  21.         a.push(1);
  22.     }
  24.     console.timeEnd('push')
  25. }
  27. unshiftFn()
  28. pushFn()

其中 unshiftFn 是使用unshift方法从队列头部方向添加元素，
pushFn 使用push从队列尾部添加元素。执行两个方法打印出它们的执行时长如下：
image.png

push VS unshift

可以看出两种方法的执行效率相差之大，为什么相比于push unshift的效率差这么多？

push做了两件事：

  1. 为栈（数组）分配新的内存空间
  2. 向新的内存空间中拷贝数据

unshift除了需要做push完成的两件事外，还需要做另外一件事：

更新元素索引，将位置N更新为N+1、将N1更新为N1+1、将N2更新为N2+1，循环次数越多速度就越慢，因为向后移动的元素在不断地增多

连续内存

push与unshift的效率差异是由于连续内存导致的，连续内存是指数组被存储为一段连续的内存，这样就不可避免地造成向数组中间插入或删除元素性能会比较差，因为为了让其它元素保持一块连续的内存不得不进行大量的元素位移，性能主要消耗在这里。

非连续内存

看样子JavaScript数组是连续内存，但真是这样么？

思考一个问题，JavaScript数组可以存储不同的数据类型的元素，如果是连续内存的话，那么这种情况下系统怎么为元素分配固定的内存呢？因为其中的元素内存是动态无法固定的。这不是与之前描述的连续内存相矛盾么？因为JavaScript数组有它自己的特殊性。

JavaScript的数组是否连续分配取决于数组成员的类型，如果是统一单一类型的数据那么会连续分配内存，如果包含各种不同类型的元素，那么会是非连续内存。

非连续内存的数组是用类似哈希映射的方式存在，比如分配一个数组，他被分配给了1001、2011、1088、1077四个非连续的内存地址，它们通过指针连接起来形成一个线性结构，所以查询某个元素就是遍历这个线性链表的过程，所以比较消耗性能。

如下代码测试：

  1. const total = 1000000
  3. function unshiftContinuity() {
  4.     const arr = new Array(total)
  5.     arr.push({name: 'xiaomuzhu'});
  6.     console.time('unshiftContinuity')
  7.     for(let i=0;i<total; i++){
  8.         arr[i]=i
  9.     }
  10.     console.timeEnd('unshiftContinuity')
  11. }
  13. function unshiftUncontinuity() {
  14.     const arr = new Array(total)
  15.     console.time('unshiftUncontinuity')
  16.     for (let i=0;i<total;i++) {
  17.         arr[i]=i
  18.     }
  20.     console.timeEnd('unshiftUncontinuity')
  21. }
  23. unshiftContinuity()
  24. unshiftUncontinuity()

执行结果如下：
image.png
可以看到unshiftContinuity运行效率明显低于unshiftUncontinuity，两个方法是主要区别在于unshiftContinuity方法在遍历数组前向数组中插入了一个对象，这将会导致系统无法为数组中每个元素提供固定的内存空间，所以遍历数组时需要通过链表的形式进行查找。而unshiftUncontinuity方法中遍历数组通过a[k]_address = base_address + k * type_size的方式直接找到相应的元素，所以效率会高很多。

总结

综上案例影响数组操作效率有两个原因：

  1. 对于连续内存数组会导致元素位移的操作将会导致较大的性能消耗；
  2. 非连续内存数组会按照线性链表的方式查找元素，速度慢于连续内存数组的公式寻址的查找方式；

知晓原因，我们就可以在实际工作中尽量避免不必要性能损耗：

  1. 尽量避免会造成连续内存数组元素位移的操作
  2. 尽量使用连续内存数组，因为它的遍历效率更高