javascript - 更高效的 'remove duplicates' 函数

Question

我管理的 Google 表格列表有时会超过 10,000 行。对于行数最多为 5,000 行的工作表，下面提到的删除重复项功能效果很好。但对于超过 5,000 的任何内容，我都会收到“超出最大执行时间”错误。如果能提供一些有关如何使代码更高效以使其即使对于 10k+ 行的工作表也能顺利运行的说明，我将不胜感激。

function removeDuplicates() {
  var sheet = SpreadsheetApp.getActiveSheet();
  var data = sheet.getDataRange().getValues();
  var newData = new Array();
  for(i in data){
    var row = data[i];
    var duplicate = false;
    for(j in newData){
      if(row.join() == newData[j].join()){
        duplicate = true;
      }
    }
    if(!duplicate){
      newData.push(row);
    }
  }
  sheet.clearContents();
  sheet.getRange(1, 1, newData.length, newData[0].length).setValues(newData);
}

Answer 1

有几件事会使您的代码变慢。让我们看看您的两个 for 循环:

for (i in data) {
  var row = data[i];
  var duplicate = false;

  for (j in newData){
    if (row.join() == newData[j].join()) {
      duplicate = true;
    }
  }

  if (!duplicate) {
    newData.push(row);
  }
}

从表面上看，您的做法是正确的:对于原始数据中的每一行，检查新数据中是否已有匹配行。如果不是，则将该行添加到新数据中。然而，在此过程中，您需要做很多额外的工作。

例如，考虑这样一个事实，即在任何给定时间，data 中的一行在 newData 中不会有超过一个匹配行。但在您的内部 for 循环中，在您找到一个匹配项后，它仍会继续检查 newData 中的其余行。解决方案是在 duplicate = true; 之后添加一个 break; 以停止迭代。

还要考虑对于任何给定的 j，newData[j].join() 的值将始终相同。假设您在 data 中有 100 行，并且没有重复项(最坏的情况)。当您的函数完成时，您将计算 newData[0].join() 99 次，newData[1].join() 98 次...总而言之，您将完成近 5,000 次计算以获得相同的 99 个值。一个解决方案是 memoization ，从而存储计算结果以避免以后再次进行相同的计算。

即使您进行了这两项更改，您的代码的 time complexity还是O(n²) .如果您有 100 行数据，在最坏的情况下，内部循环将运行 4,950 次。对于 10,000 行，这个数字约为 5000 万。

但是，如果我们去掉内循环并像这样重新构造外循环，我们可以用 O(n) 时间代替:

var seen = {};

for (var i in data) {
  var row = data[i];
  var key = row.join();

  if (key in seen) {
    continue;
  }
  seen[key] = true;
  newData.push(row);
}

在这里，我们不是在每次迭代中检查 newData 的每一行是否有匹配 row 的行，而是将我们目前看到的每一行存储为对象看到。然后在每次迭代中，我们只需要检查 seen 是否有匹配 row 的键，我们可以在几乎恒定的时间内完成该操作，或者 O (1). ¹

作为一个完整的函数，它是这样的:

function removeDuplicates_() {
  const startTime = new Date();
  const sheet = SpreadsheetApp.getActiveSheet();
  const data = sheet.getDataRange().getValues();
  const numRows = data.length;
  const newData = [];
  const seen = {};

  for (var i = 0, row, key; i < numRows && (row = data[i]); i++) {
    key = JSON.stringify(row);
    if (key in seen) {
      continue;
    }
    seen[key] = true;
    newData.push(row);
  }

  sheet.clearContents();
  sheet.getRange(1, 1, newData.length, newData[0].length).setValues(newData);

  // Show summary
  const secs = (new Date() - startTime) / 1000;
  SpreadsheetApp.getActiveSpreadsheet().toast(
    Utilities.formatString('Processed %d rows in %.2f seconds (%.1f rows/sec); %d deleted',
                           numRows, secs, numRows / secs, numRows - newData.length),
    'Remove duplicates', -1);
}

function onOpen() {
  SpreadsheetApp.getActive().addMenu('Scripts', [
    { name: 'Remove duplicates', functionName: 'removeDuplicates_' }
  ]);
}

您会看到，这段代码没有使用 row.join()，而是使用了 JSON.stringify(row)，因为 row.join() 是脆弱的(例如，['a,b', 'c'].join() == ['a', 'b,c'].join())。 JSON.stringify 不是免费的，但对于我们的目的来说这是一个很好的折衷方案。

在我的测试中，这会在 8 秒多一点的时间内处理一个包含 50,000 行和 2 列的简单电子表格，即每秒大约 6,000 行。