Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 27.09.2012, 23:56
Новичок на форуме
Отправить личное сообщение для Аня C Посмотреть профиль Найти все сообщения от Аня C
 
Регистрация: 25.09.2012
Сообщений: 5

Оценка сложности RegExp
На чём эффективнее в js реализовать разбор большого текста? В большом количестве вложенных RegExp/split (на небольшом количестве данных работает отлично) - получается 3 или 4 вложенных цикла или написать автомат? Подскажите, пожалуйста, в O-нотации сложность реализованных алгоритмов в js для split и RegExp.
Ответить с цитированием
  #2 (permalink)  
Старый 28.09.2012, 00:33
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

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

Сообщение от Аня C
На чём эффективнее в js реализовать разбор большого текста?
думаю, тут в первую очередь важен правильный алгоритм. Те же объекты (регэкспы) по многу раз создавать вовсе не обязательно.

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

Еще можете привести пример
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Ответить с цитированием
  #3 (permalink)  
Старый 30.09.2012, 18:00
Новичок на форуме
Отправить личное сообщение для Аня C Посмотреть профиль Найти все сообщения от Аня C
 
Регистрация: 25.09.2012
Сообщений: 5

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

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

Сообщение от nerv_ Посмотреть сообщение
Еще можете привести пример
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, поскольку именно его считаю слабым местом)?
Или всё-таки лучше будет сделать автомат? Сейчас попробую, конечно.
Ответить с цитированием
  #4 (permalink)  
Старый 30.09.2012, 18:05
х.з
Посмотреть профиль Найти все сообщения от dmitriymar
 
Регистрация: 21.11.2010
Сообщений: 4,588

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

Последний раз редактировалось dmitriymar, 30.09.2012 в 18:10.
Ответить с цитированием
  #5 (permalink)  
Старый 01.10.2012, 20:40
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

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

для начала
var re1 = /\.|\?|\!/;    // [?!.]
var re2 = /\,|\:|\—|\;/;    // [:;,—]
var re3 = /\s{1,}/;    // \s+
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук

Последний раз редактировалось nerv_, 01.10.2012 в 20:52.
Ответить с цитированием
  #6 (permalink)  
Старый 06.10.2012, 00:04
Новичок на форуме
Отправить личное сообщение для Аня C Посмотреть профиль Найти все сообщения от Аня C
 
Регистрация: 25.09.2012
Сообщений: 5

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

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



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
regexp не работает экранирование точки Spice Общие вопросы Javascript 2 10.11.2011 13:41
dom и regexp KOLANICH Events/DOM/Window 6 16.01.2010 22:51
мааленький вопрос по Regexp:) mirniy Общие вопросы Javascript 1 22.01.2009 20:47
RegExp & Mozilla (быстродействие) tau Общие вопросы Javascript 9 24.11.2008 16:35
RegExp и unicode Yury900 Общие вопросы Javascript 7 13.05.2008 00:19