逛贴吧看到一个关于数组的题目。简单概括需求就是翻转矩阵,xy轴交换。
// 随机填充定长数组
function randArr(n) {
const a = [];
while (n--)
a.push(Math.floor(Math.random() * 10));
return a;
}
// 测试目标
const arr = []
// 准备x轴随机长度的矩阵
function start(n) {
const m = n;
while (n--) {
arr.push(randArr(Math.ceil(m / 2 + Math.random() * m / 2)))
}
}
然后思路最常见的就是双循环遍历交换:
function rotateMatrix2(matrix) {
const a = [];
matrix.forEach((row, y) =>
row.forEach((cell, x) =>
(a[x] = a[x] || [])[y] = cell));
return a;
}
通常来说 磨刀不误砍柴工,我们应该尽量减少循环过程中的步骤。这里初始化数组就是一个消耗操作。所以我这里将其移出到外面:
function rotateMatrix(matrix) {
const lenArr = matrix.map(c => c.length);
const arr = Array(Math.max(...lenArr)).fill().map(() => []);
lenArr.forEach((x, y) => {
const v = matrix[y];
while (x--) arr[x][y] = v[x];
});
return arr;
}
function test(fn, n, arr) {
const label = fn.name;
console.time(label)
while (n--) {
fn(arr)
}
console.timeEnd(label)
}
start(300)
const times = 1000
test(rotateMatrix, times, arr)
test(rotateMatrix2, times, arr)
rotateMatrix: 448.126ms
rotateMatrix2: 590.113ms
只有一丢丢的优化,好,现在我们现在再修改下:
function rotateMatrix(matrix) {
const len = matrix.length
const lenArr = matrix.map(c => c.length);
//这里预分配的长度空间
const arr = Array(Math.max(...lenArr)).fill().map(() => Array(len));
lenArr.forEach((x, y) => {
const v = matrix[y];
while (x--) arr[x][y] = v[x];
});
return arr;
}
运行输出:
rotateMatrix: 206.414ms
rotateMatrix2: 609.477ms
可以看到很明显的优化。
改变样本数据再试一下
start(1e4)
const times = 2
输出:
rotateMatrix: 6.440s
rotateMatrix2: 12.219s
由上面测试结果可以知道 除了可见的步骤会影响性能 程序背后底层的不可见操作也对性能有很大的影响。
我们不能因为js是一个宽松语言而忽视了底层的操作。
分配空间是一个消耗操作,虽然我们看不到,但可以猜想到当数组长度变化时候,底层会对数组内存空间做调整。而预先指定了长度,则会减少内存分配次数,减少一笔可观的开销。