Оценка сложности RegExp
 

На чём эффективнее в js реализовать разбор большого текста? В большом количестве вложенных RegExp/split (на небольшом количестве данных работает отлично) - получается 3 или 4 вложенных цикла или написать автомат? Подскажите, пожалуйста, в O-нотации сложность реализованных алгоритмов в js для split и RegExp.

я, конечно, могу ошибаться, но во всех браузерах по разному работает. Взять тот же IE. Там вообще JScript...

думаю, тут в первую очередь важен правильный алгоритм. Те же объекты (регэкспы) по многу раз создавать вовсе не обязательно.

Насчет сложности. Думаю, если вы посмотрите реализацию на mdsn и mdn нужных вам инструментов (функций), то сами разберетесь.

Еще можете привести пример :)

Я про тоже думаю.

Обязательно посмотрю на msdn и mdn. Спасибо.

function trim( str, charlist ) {
// Strip whitespace (or other characters) from the beginning and end of a string
    //
    // +   original by: Kevin van Zonneveld ([url]http://kevin.vanzonneveld.net[/url])
    // +   improved by: mdsjack ([url]http://www.mdsjack.bo.it[/url])
    // +   improved by: Alexander Ermolaev ([url]http://snippets.dzone.com/user/AlexanderErmolaev[/url])
    // +      input by: Erkekjetter
    // +   improved by: Kevin van Zonneveld ([url]http://kevin.vanzonneveld.net[/url])
    charlist = !charlist ? ' \\s\xA0' : charlist.replace(/([\[\]\(\)\.\?\/\*\{\}\+\$\^\:])/g, '\$1');
    var re = new RegExp('^[' + charlist + ']+|[' + charlist + ']+$', 'g');
    return str.replace(re, '');
}

            function parser() {
                var text=document.getElementById("in").value;
                var out=document.getElementById("out");
                var re0=/\n/;
                text=text.split(re0);
                for(var i in text) {
                   var re1 = /\.|\?|\!/;
                   text[i]=text[i].split(re1);
                   for(var j in text[i]) {
                     text1=trim(text[i][j]);
                     var re2 = /\,|\:|\—|\;/;
                     text[i][j]=text[i][j].split(re2);
                     for(var k in text[i][j]){
                       text[i][j][k] = trim(text[i][j][k]);
                       var re3 = /\s{1,}/;
                       text[i][j][k] = text[i][j][k].split(re3);
                       if (text[i][j][k][2])
                       out.value+='В абзаце '+i+' в предложении '+j+'\n'+
                       '\"'+text1+'\"\nв части '+ k +' есть третье слово: '+text[i][j][k][2]+'\n\n';
                       }
                   }
                }
            }

<input type="button" onclick="parser()" value="Парсим!"/>
         <textarea id="in"></textarea>
         <textarea id="out"></textarea>

Это простой вариант. Кавычки и прямую речь не учитываем. Что делает? Разбивает текст на абзацы, абзацы на предложения, предложения на части. В каждой части вырезает третье слово. Показывает/запоминает номер абзаца, номер строки, номер части, начиная с нуля. На тексте 90 000 слов задумывается (правда, ненадолго). IE6, Хром.
Как можно улучшить алгоритм (хм... в реальности там и регэкспы накручены, но спрашиваю пока про split, поскольку именно его считаю слабым местом)?
Или всё-таки лучше будет сделать автомат? Сейчас попробую, конечно.

оптимизировать регулярки однозначно-читать про возвраты
тоже касается и оптимизации алгоритма в целом и т.д. -зачем всякий раз это в цикле создавать?
да и строки..
в общем всё здесь-
http://rutracker.org/forum/viewtopic.php?t=4198867

dmitriymar, а еще ссылки на полезные книжки могёшь? ) Можно в личку...

для начала

var re1 = /\.|\?|\!/;    // [?!.]
var re2 = /\,|\:|\—|\;/;    // [:;,—]
var re3 = /\s{1,}/;    // \s+

Большое спасибо!
Для того, чтобы запомнить номер абзаца-строки-числа. Собственно видела два пути - написать свой автомат (ДКА), тогда будет линейное время. Либо циклами. Сейчас вижу, что автомат и так уже реализован (хорошо описано у Фриддла), но не ДКА, а НКА. Отсюда стали ясны тонкости. Почему нельзя ставить |, а вместо этого нужно создавать символьные классы. Попробую двумя способами ДКА и оптимизировать регулярки, посмотрю, что быстрее. Ещё раз спасибо за указания на ошибки!

Нашла замечательную книгу, где всё прекрасно расписано - http://www.ozon.ru/context/detail/id/1379940/ - теория регулярных выражениях, которой мне так не хватало, к JS отношения имеет мало. После прочтения стало понятно, почему надо делать так, как вы написали, а не иначе.
Спасибо за помощь!