时间戳

首页 > 解决方案 > 在 JavaScript 中设置矩阵归零性能

javascript - 在 JavaScript 中设置矩阵归零性能

问题描述

我在 JavaScript 中构建了 Set Matrix Zeroes 算法。我的代码中有很多循环，所以想知道是否有更好的方法来实现这个算法。

给定 amxn 矩阵，如果一个元素为 0，则将其整行和整列设置为 0。就地执行。

我循环矩阵，当我找到一个 0 时，我将它的整个行和列设置为一个标志（'X'）。如果位置为 0，我不会设置“X”，因为我将来可能需要检查这个位置。最后，我将所有“X”替换为 0。

var setZeroes = function(matrix) {
    if(matrix === null || matrix.length === 0)
        return [];
    
    for(let i=0; i<matrix.length; i++){
        for(let j=0; j<matrix[i].length; j++){
            if(matrix[i][j] === 0){
                setFlag(matrix, i, j);
            }
        }
    }
    
    for(i=0; i<matrix.length; i++){
        for(j=0; j<matrix[i].length; j++){
            if(matrix[i][j] === 'X')
                matrix[i][j] = 0;
        }
    }
};

const setFlag = function(matrix, i, j) {
    matrix[i][j] = 'X';
    let tempI = i+1;
    while(tempI < matrix.length){
        if(matrix[tempI][j] !== 0)
            matrix[tempI][j] = 'X';
        tempI++;
    }
    tempI = i-1;
    while(tempI >= 0){
        if(matrix[tempI][j] !== 0)
            matrix[tempI][j] = 'X';
        tempI--;
    }
    let tempJ = j+1;
    while(tempJ < matrix[i].length){
        if(matrix[i][tempJ] !== 0)
            matrix[i][tempJ] = 'X';
        tempJ++;
    }
    tempJ = j-1;
    while(tempJ >= 0){
        if(matrix[i][tempJ] !== 0)
            matrix[i][tempJ] = 'X';
        tempJ--;
    }
}

标签： javascriptperformance

解决方案

这是一个更具声明性的实现，Jsperf 更喜欢它。

let replaceRowCol = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // An array to hold all replacements that need to be made
  let replaceArr = [];
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) replaceArr.push({ x, y });
  }}
  
  // Perform all replacements
  for (let { x, y } of replaceArr) {
    for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
    for (let yy = 0; yy < h; yy++) matrix[x][yy] = val;
  }
  
  return matrix;
  
};

let matrix = replaceRowCol([
  [ 0, 2, 3, 4 ],
  [ 1, 2, 3, 4 ],
  [ 1, 2, 0, 4 ],
  [ 1, 2, 3, 4 ]
]);

for (let row of matrix) console.log(row.join(' '));

这种方法不是将临时占位符值插入到矩阵中，而是执行第一遍以记住所有零的位置，然后在这些记住的位置上执行第二遍以替换行和列。

速度是避免回调和函数调用的结果，除了Array.prototype.push（请注意，如果我们使用简单的链表可以避免这种情况）。尽管回调被编译并且在任何像样的 javascript VM 下都非常快，但它们仍然不如上面的旧程序代码那么快。

值得一提的是非常厚颜无耻的加速的可能性：如果需要替换多行，您可以将第一行中的每个项目设置为零，但对于之后的每一行，您可以引用第一个归零的行。这将完全跳过迭代后面行的需要。当然，生成的矩阵会有多行都引用同一个数组，这可能会在未来的操作中导致非常意外的结果。

这种厚颜无耻的加速看起来像这样：

let replacedX = null;
for (let { x, y } of replaceArr) {
  // We still need to replace the column, as usual
  for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
  if (replacedX === null) {
    replacedX = matrix[x] = Array(w).fill(val); // This has O(w) runtime
  } else {
    matrix[x] = replacedX;                      // This has O(1) runtime
  }
}

编辑：链表实现。它包含在 jsperf 中，而且速度更快！

let replaceRowColLinkedList = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // A linked list
  let replacements = null;
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) {
      let next = replacements;
      replacements = { x, y, next };
    }
  }}
  
  // Perform all replacements
  let llNode = replacements;
  while (llNode) {
    let { x, y, next } = llNode;
    for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
    for (let yy = 0; yy < h; yy++) matrix[x][yy] = val;
    llNode = next;
  }
  
  return matrix;
  
};

let matrix = replaceRowColLinkedList([
  [ 0, 2, 3, 4 ],
  [ 1, 2, 3, 4 ],
  [ 1, 2, 0, 4 ],
  [ 1, 2, 3, 4 ]
]);

for (let row of matrix) console.log(row.join(' '));

编辑：对于具有许多冲突的大型矩阵（许多零共享同一行或列）可能值得使用Set以避免重新归零行/列。当然，不利的一面是，无论实现如何，Set.prototype.add它的运行时都必须比. O(1)然而，总的来说，Set.prototype.add对于较小的矩阵，运行时间可以忽略不计，而对于较大的矩阵，避免碰撞可以带来显着的好处。这种方法在jsperf中一直是最快的，也是我整体推荐的方法！

let replaceRowCol = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // Store columns and rows to replace
  let replaceX = new Set();
  let replaceY = new Set();
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) {
      replaceX.add(x);
      replaceY.add(y);
    }
  }}
  
  // Perform all replacements
  for (let x of replaceX) for (let y = 0; y < h; y++) matrix[x][y] = val;
  for (let y of replaceY) for (let x = 0; x < w; x++) matrix[x][y] = val;
  
  return matrix;
  
};

let matrix = replaceRowCol([
  [ 0, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 0, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ]
]);

for (let row of matrix) console.log(row.join(' '));

推荐阅读