X

js 数组操作优化

2022/3/26

逛贴吧看到一个关于数组的题目。简单概括需求就是翻转矩阵,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是一个宽松语言而忽视了底层的操作。

分配空间是一个消耗操作,虽然我们看不到,但可以猜想到当数组长度变化时候,底层会对数组内存空间做调整。而预先指定了长度,则会减少内存分配次数,减少一笔可观的开销。

Commit