js创建数组耗时的思考

[YBFACC]

js创建数组耗时的思考

我在写这题（123. 买卖股票的最佳时机 III ）时产生的问题 ：

var maxProfit = function (prices) {
  if (prices.length === 0) return 0
  const Len = prices.length
  const dp = Array.from({ length: Len }, () => 0)

  let res = 0
  for (let i = 1; i < Len; i++) {
    dp[i] = dp[i - 1]
    for (let j = 1; j <= i; j++) {
      const curr = prices[i] - prices[j - 1]
      res = Math.max(res, curr)
      dp[i] = Math.max(dp[i], curr)
      if (j - 2 >= 0) {
        res = Math.max(res, curr + dp[j - 2])
      }
    }
  }
  return res
}

时间复杂度N^2，空间N^1（官方加了测试用例N^2已经不能通过）

var maxProfit = function (prices) {
  if (prices.length === 0) return 0
  const Len = prices.length
  const dp = Array.from({ length: Len }, () =>
    Array.from({ length: 3 }, () => Array.from({ length: 2 }, () => 0))
  )

  dp[0][0][1] = -prices[0]
  dp[0][1][1] = -prices[0]

  for (let i = 1; i < Len; ++i) {
    dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i])
    dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][0][1] + prices[i])
    dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][1][0] - prices[i])
    dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][1][1] + prices[i])
  }

  return Math.max(
    dp[Len - 1][0][1],
    dp[Len - 1][1][0],
    dp[Len - 1][1][1],
    dp[Len - 1][2][0]
  )
}

时间复杂度N^1，空间N^1

为什么N^2 和N^1的耗时结果差距这么小？

当时真的百思不得其解，因为这题的数据也足够大，这时间差距应该有显著差距。

直到我再次优化将3维数组变成常数空间。

var maxProfit = function (prices) {
  if (prices.length === 0) return 0
  const Len = prices.length

  let dp0 = 0
  let dp1 = -prices[0]
  let dp2 = 0
  let dp3 = -prices[0]
  let dp4 = 0

  for (let i = 1; i < Len; i++) {
    dp1 = Math.max(dp1, dp0 - prices[i])
    dp2 = Math.max(dp2, dp1 + prices[i])
    dp3 = Math.max(dp3, dp2 - prices[i])
    dp4 = Math.max(dp4, dp3 + prices[i])
  }

  return Math.max(dp0, dp1, dp2, dp3, dp4)
}

这才是N^1的算法才有的速度。

对比

观察这2个算法，差别就在于创建数组。

我在常数空间算法中，使他创建1维数组

  const dp = Array.from({ length: Len }, () => 0）

我在常数空间算法中，使他创建2维数组

 const dp = Array.from({ length: Len }, () =>
    Array.from({ length: 3 }, () => 0)
  )  

我在常数空间算法中，使他创建3维数组

  const dp = Array.from({ length: Len }, () =>
    Array.from({ length: 3 }, () => Array.from({ length: 2 }, () => 0))
  )

乖乖！可以看到创建数组的耗时远比算法本身的运行时间长太多。

和java进行对比

相同的算法，java的耗时就没有这么夸张。

java3维耗时

java2维耗时

java常数耗时

总结

js在创建多维数组上性能很差，拿来写算法避免创建多维数组

[YBFACC]

使用类型化数组来加速

以这题为参考，频繁的开数组带来巨量的时间消耗

1601. 最多可达成的换楼请求数目

function maximumRequests(n: number, requests: number[][]): number {
  const Len = requests.length
  let res = 0
  function check(list: number[][]): boolean {
    const hash = Array.from({ length: n }, () => 0)
    for (const [from, to] of list) {
      hash[from]--;
      hash[to]++
    }
    for (let i = 0; i < n; i++) {
      if (hash[i] !== 0) return false
    }
    return true
  }

  const dfs = function (temp: number[][], index: number): void {
    if (index < Len) {
      temp.push(requests[index])
      if (check(temp)) res = Math.max(res, temp.length)
      dfs(temp, index + 1)
      temp.pop()
      dfs(temp, index + 1)
    }
  }
  dfs([], 0)
  return res
};

现在使用类型化数组 const hash = new Int16Array(n)

可以看到使用类型化数组带来的收益巨大。直接操作内存，不需要进行类型转换（类似于C语言的数组？）。在使用数组的时候，可以考虑使用类型化数组代替普通数组。

使用注意点

• 在多维数组中，只能在最后一维中使用。
• 成员都为同一种类型（只能包含number）
• 成员默认值为0