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, что делает его вкладчиком неактивным). Этот файл содержит около миллиона «релевантных элементов», что означает совпадения от relevantDelimiters.

Как это можно оптимизировать?

Answer 1

Вместо того, чтобы повторно «брать элемент из ввода», позвонив по нему replace, вы должны использовать второй аргумент для 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-iterations, вы можете сохранить свой индекс и установить тайм-аут до возобновления. Таким образом, вы не блокируете поток пользовательского интерфейса.