更有效的“删除重复项”功能

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);
  }
}

从表面上看，您正在做正确的事情：对于原始数据中的每一行，请检查新数据是否已经具有匹配的行。如果不是，请将行添加到新数据。但是，在此过程中，您需要做很多额外的工作。

例如，考虑以下事实：在任何给定的时间，in中的一行data最多只能有in 个匹配行newData。但是在内部for循环中，找到一个匹配项后，它仍然继续检查中的其余行newData。解决方案是添加一个break;after duplicate = true;来停止迭代。

还请考虑对于任何给定j，的值newData[j].join()将始终相同。假设您在中有100行data，并且没有重复（最坏的情况）。到函数完成时，您将已经计算了newData[0].join()99次，newData[1].join()98次……总共将进行近5,000次计算以获得相同的99个值。解决方案是备忘录，您可以存储计算结果，以避免以后再次进行相同的计算。

即使你做这两个改变，不过，你的代码的时间复杂度仍然是Ø（ñ ²） 。如果您有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，而是将到目前为止已看到的每一行存储为object中的键seen。然后，在每次迭代中，我们只需要检查是否seen有键匹配row，可以在几乎恒定时间内完成的操作或O（1）。^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行。