javascript - js数组插入，有比splice更快的吗？

问题描述

问 题

index_ids.splice(idx, 0, id);

我发现执行一万条数据，注释掉这行代码，整个程序执行减少了10秒钟的时间。我的代码有两行这样的，总共多花了20秒的时间，如果有比这个更快的插入方式，我可以省下好多时间。

解决方案

var arrInsert = [5, 6, 7];

var newArray = [];

var index = 0;
for(var i in index_ids){
    var now = index_ids[i];
    if(index < arrInsert.length && index_ids[i] < arrInsert[index]){
        newArray.push(index_ids[i]);
    }else{
         if(index < arrInsert.length){
            newArray.push(arrInsert[index]);
            index++;
        }
        newArray.push(index_ids[i]);
    }
}

大概就是这个意思吧，可能语法有错误。
还要注意数组别越界。

假设你原来的代码是:

for(var i in index_ids){                //这里一个循环，是n次(2)
    var idx = index_ids.find_somthing(id);
    index_ids.splice(idx, 0, id);        //这个算法的复杂度是O(n)的(1)
}

splice()是O(n)的，原因是，当你在中间插入一个，插入位置之后的元素都要集体向后移动一个位置，这就相当于你先找到了第x位置，插入了一个元素，而后面n-x个元素为了空出这个空，都往后移动了一个，这就是遍历所有的n个元素了，所以这个for会特别慢。

但如果，你将id排成有序的，你只需要在index_ids中循环一遍，找到每个id所应该插入的位置，然后为了不进行所有元素位移，那就用新的数组存放id和index_ids，这样计算次数只是id和index_ids的数量之和，也不用先查找到idx。

两个有序链表合并为一个有序链表也是这个方法。但链表的好处是插入不用移动元素。但即便如此，链表的插入在查找的时候就是得遍历部分的元素或者所有的元素。

既然arrInsert没办法一次行算出来，那这个问题已经不是有序链表合并的问题了。

平衡树能解决这个问题，{}对象就是个平衡树。但这个平衡树的问题是，应用在前面的方案上，你会处于一个平衡树与数组之间不断来回转换，如果转换次数太多，那只能是解决当前问题又会出新的问题。

我想到一个可能可行的方法：每当一个数据insert的时候，你把这个数据的索引存到{}中，然后呢，当{}对象的大小达到1w个(10w也行，时间越长，回滚越麻烦，但不能1k，100，越晚执行约节省计算)的时候，你把{}中的元素挨个取出来存到val数组里(在取的过程中，{}不能进行插入了，你需要给它加上锁；此时如果有新的insert来了，你得需要用备用{}来存储，当{}取完了，把备用的放进去)，然后再清空{}，这是防止在合并val与index_ids时又有insert数据来，然后给val数组排序，执行:

function array_insert(val, index_ids){
   var newArray = [];
   let arrInsert = val;
   var index = 0;
   for(var i in index_ids){
      var now = index_ids[i];
      if(index < arrInsert.length && index_ids[i] < arrInsert[index]){
          newArray.push(index_ids[i]);
      }else{
          if(index < arrInsert.length){
              newArray.push(arrInsert[index]);
              index++;
        }
        newArray.push(index_ids[i]);
     }
   }
   return newArray;
}

然后清空val，把返回的newArray赋值给index_ids，继续用{}装接下来的insert请求。

这篇关于javascript - js数组插入，有比splice更快的吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！