从shuffle函数看性能

假设现在我们有一个数组，我们需要打乱它的次序。

思路：遍历数组，不断交换当前位置的数字和其他位置数字。

Array.prototype.shuffle = function(){
  var i = this.length
  if (i<2){
    return
  }
  while (--i){
    j = Math.floor(Math.random() *(i+1))
    temp = this[i]
    this[i] = this[j]
    this[j] = temp
  }
  return
}

var a = [1,2,3,4,5]
a.shuffle()
console.log(a)

另一种情况

上面的算法改变了原来的数组。但是有时候我们希望返回shuffle后的数组，但是不改变原数组。我们可以使用在之前讲到过的deepcopy函数来帮助我们

function deepcopy(obj, res){
  var res = res || {};
  for(var i in obj){
    if(! obj.hasOwnProperty(i){
      continue
    })
    if(typeof obj[i] === 'object'){
      res[i] = (obj[i] instanceof Array) ? [] : {};
      deepcopy(obj[i], res[i])
    }else{
      res[i] = obj[i]
    }
  }
  return res
 }

注意，for in 遍历对象时会遍历原型链，而我们在拷贝时排除了原型链上的属性。

function shuffle(arr){
  var res = deepcopy(arr, [])
  res.shuffle()
  return res
}
console.log(shuffle(a))
console.log(a)

我们在调用这个shuffle函数时，先复制了一份原数组，然后再进行shuffle算法。

很显然，第二种方法在空间和时间上都比第一种差很多。我们可以写一个函数来测试一下。

timeit

var timeit = function(fn){
  var start = Date.now()
  fn()
  console.log(Date.now()-start)
}

var a = []
for (var i=0; i<10000000;i++){
  a.push(i)
}

timeit(function(){
  a.shuffle()
})

上面的代码返回运行时间为383毫秒

timeit(function(){
  shuffle(a)
})

运行时间为5791毫秒，高下立判！

看上去，方法一和二之间只是相差了一次对象复制操作，但是带来的性能差异非常明显。