Open YBFACC opened 4 years ago
以这题为参考,频繁的开数组带来巨量的时间消耗
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语言的数组?)。在使用数组的时候,可以考虑使用类型化数组代替普通数组。
js创建数组耗时的思考
我在写这题(123. 买卖股票的最佳时机 III )时产生的问题 :
时间复杂度N\^2,空间N\^1(官方加了测试用例N\^2已经不能通过)
时间复杂度N\^1,空间N\^1
为什么N\^2 和N^1的耗时结果差距这么小?
当时真的百思不得其解,因为这题的数据也足够大,这时间差距应该有显著差距。
直到我再次优化将3维数组变成常数空间。
这才是N\^1的算法才有的速度。
对比
观察这2个算法,差别就在于创建数组。
我在常数空间算法中,使他创建1维数组
我在常数空间算法中,使他创建2维数组
我在常数空间算法中,使他创建3维数组
乖乖!可以看到创建数组的耗时远比算法本身的运行时间长太多。
和java进行对比
相同的算法,java的耗时就没有这么夸张。
java3维耗时
java2维耗时
java常数耗时
总结
js在创建多维数组上性能很差,拿来写算法避免创建多维数组