javascript indexOf 有数百万个匹配项

Question

我正在尝试从文件中提取代表某些 XML 元素的几行。用户使用简单的 <input type="file"> 标签提供一个文件，然后使用 FileReader 将该文件读取为文本，并作为此函数的参数提供：

var relevantDelimiters = [{"begin":"<header>","end":"</header>"}
,{"begin":" <someElement>","end":"</someElement>"}];

function dealWithString(invalidXML) {
  var validXML = "";
  for (var i=0; i<relevantDelimiters.length; i++) {
    delimiter = relevantDelimiters[i];
    while (invalidXML.indexOf(delimiter.begin) != -1) {
      //while there are relevant elements of this kind left: 
      startPos = invalidXML.indexOf(delimiter.begin);
      endPos = invalidXML.indexOf(delimiter.end); 
      //append to end result:
      validXML+=invalidXML.substring(startPos,endPos+delimiter.end.length)+"\n";
      //take this item out of the input to process next item
      invalidXML = invalidXML.replace(invalidXML.substring(startPos,endPos+delimiter.end.length),"");
    }
  }
  //return fixed data
  return validXML;
}

这种方法似乎适用于输入文本文件中的少量匹配项，但给定一个 1.5MB 的文件，脚本会卡住（运行 Google Chrome，使其标签无响应）。此文件包含大约一百万 "relevant elements"，这意味着来自 relevantDelimiters.

的匹配项

我该如何优化它？

Answer 1

与其通过调用 replace 重复 "taking the item out of the input"，您应该使用 indexOf 的第二个参数：fromIndex。这样，它将搜索给定索引之后的下一个事件，并且您可以循环遍历非常大的输入而无需触摸它。

function dealWithString(invalidXML) {
  var validXML = "";
  for (var i=0; i<relevantDelimiters.length; i++) {
    var delimiter = relevantDelimiters[i],
        pos = 0,
        startPos;
    while ((startPos = invalidXML.indexOf(delimiter.begin, pos)) != -1) {
      //while there are relevant elements of this kind left:
      var endPos = invalidXML.indexOf(delimiter.end, startPos);
      // assert(endPos != -1) - otherwise this could go horribly wrong
      pos = endPos+delimiter.end.length;
      //append to end result:
      validXML += invalidXML.slice(startPos, pos) + "\n";
    }
  }
  return validXML;
}

Answer 2

时间都花在哪儿了？我假设您可以将这个大的同步操作分解为几个异步操作。（每隔几次 while 迭代，您可以在恢复之前存储您的索引和设置超时。这样您就不会锁定 UI 线程。

javascript indexOf 有数百万个匹配项

javascript indexOf with millions of matches

javascript

google-chrome

indexof