Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
#1

с++11. Сильно тормозят регулярные выражения - C++

29.11.2012, 20:37. Просмотров 1632. Ответов 19
Метки нет (Все метки)

Добрый день!

Есть файл "словарь.txt", нужно прочитать его построчно и вывести в файл "результат.txt" только те строки, которые удовлетворяют регулярному выражению. Пишу:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "stdafx.h"
#include <fstream>
#include <sstream>
#include <istream>
#include <iostream>
#include <regex>
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    string line;
    regex re1("^[а-я]{3}$", std::regex::optimize);
 
    ifstream infile("c:\\!\\словарь.txt");
    ofstream outfile("c:\\!\\результат.txt");
 
    ofstream program3data;
    for( std::string line; getline(infile, line ); )
    {
        if (regex_match(line, re1))
        {
            outfile << line + "\n";
        }
    }
 
    infile.close();
    outfile.close();
 
    return 0;
}
Маленький файл в мегабайт обрабатывает секунд 10-15! На Perl аналогичный скрипт отрабатывает за долю секунды. В чем может быть проблема, где код тормозит?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2012, 20:37
Я подобрал для вас темы с готовыми решениями и ответами на вопрос с++11. Сильно тормозят регулярные выражения (C++):

Регулярные выражения
Составить регулярное выражение, пропускающее строки, содержащие хотя бы по разу...

Регулярные выражения
Может кто нибудь подсказать реализацию регулярных выражений на С/С++?

Регулярные выражения на C++
Здраствуйте, возникла необходимость использовать регурные выражения в Си++....

Регулярные выражения
Ребят, у меня тут проблемы. В файле input.txt есть строчки, в которых нужно...

Регулярные выражения.
Здравствуйте всем! Имеется массив строк. Надо написать программу с функцией...

Регулярные выражения
Здравствуйте, Надо заменить в тексте номер телефона формата (012) 345-67-89...

19
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
29.11.2012, 21:22 #2
Suppir, boost::regex попробуйте, вполне возможно что стандартные регексы еще не оптимизированы. А так регекс в С++ вообще не быстрая штука, если что.
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 12:57  [ТС] #3
Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 15:15 #4
Цитата Сообщение от Suppir Посмотреть сообщение
Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).
Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 16:40  [ТС] #5
Цитата Сообщение от diagon Посмотреть сообщение
Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.
Пользуюсь Visual Studio 2012 for Desktop (бесплатная версия).
0
I.M.
566 / 549 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 16:59 #6
Suppir, компилите в релизе или дебаге?
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 22:15  [ТС] #7
В релизе немного побыстрей, но все равно медленней, чем Perl на порядок.
0
I.M.
566 / 549 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 22:20 #8
Suppir, поищите на верхней панели инструментов слово Debug. и поменяйте его на релиз
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 22:22  [ТС] #9
Скорость программки на с++ получилась как у медленных скриптовых языков: Ruby или AutoIt.
0
I.M.
566 / 549 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 22:24 #10
Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 22:25 #11
Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 22:30  [ТС] #12
Цитата Сообщение от I.M. Посмотреть сообщение
Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?
Да, тоже построчно! Аналогичный скрипт на Perl:

Perl
1
2
3
4
5
open(IN, "c:\!\словарь.txt");
open(OU, ">c:\!\результат.txt");
while(<IN>){
    print OU if /^[а-я]{3}$/
}
Он работает на порядок быстрее (в 10 - 15 раз).
0
MrGluck
Модератор
Эксперт CЭксперт С++
8022 / 4865 / 1425
Регистрация: 29.11.2010
Сообщений: 13,251
30.11.2012, 22:33 #13
Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:
C++
1
2
3
4
5
6
7
8
9
10
std::ifstream ifstext("text.txt");
if (!ifstext)
{
    std::cerr<< "No file\n";
    return 1;
}
std::string text;
ifstext >> std::noskipws; // clears the scipws flag for the str stream
std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), 
       std::back_inserter(text) );
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 22:34  [ТС] #14
Цитата Сообщение от diagon Посмотреть сообщение
Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.
Но Perl же написан на том же си/с++, к тому же является интерпретатором (т.о. он должен быть медленней, чем скомпилированная программа).
Кстати, я пишу еще на c# около года. Так вот, на c# (.NET Framework 2.0) после всевозможных ухищрений удалось добиться скорости (в области обработки текста) в 2 раза меньше, чем у Perl. Я надеялся, что с++ пошустрее будет.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 22:36 #15
Кстати, есть такой бенчмарк.
Как видно из него бусторегексы более чем в 3 раза уступают по скорости гугловой либе(кстати, на первом месте тоже детище гугла), но все же почти в 2 раза быстрее перловых.
Это я к тому, что стоит использовать нормальные либы для регексов.
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 22:36  [ТС] #16
Цитата Сообщение от MrGluck Посмотреть сообщение
Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:
C++
1
2
3
4
5
6
7
8
9
10
std::ifstream ifstext("text.txt");
if (!ifstext)
{
    std::cerr<< "No file\n";
    return 1;
}
std::string text;
ifstext >> std::noskipws; // clears the scipws flag for the str stream
std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), 
       std::back_inserter(text) );
А как мне теперь пробежаться по каждой строке? Нужно ж еще разсплитить этот файл в массив.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8022 / 4865 / 1425
Регистрация: 29.11.2010
Сообщений: 13,251
30.11.2012, 22:36 #17
Кстати, реализация регексов на VS может отличаться от реализации на gcc. Можно MinGW попробовать посмотреть, мб шустрее будет.

И да, буст регекс наверняка лучше реализован.
0
Suppir
24 / 24 / 10
Регистрация: 08.08.2011
Сообщений: 1,155
30.11.2012, 23:04  [ТС] #18
Цитата Сообщение от diagon Посмотреть сообщение
Кстати, есть такой бенчмарк.
Как видно из него бусторегексы более чем в 3 раза уступают по скорости гугловой либе(кстати, на первом месте тоже детище гугла), но все же почти в 2 раза быстрее перловых.
Это я к тому, что стоит использовать нормальные либы для регексов.
Гуглолиба, вроде, имеет стандарт, аналогичный POSIX, т.е. не поддерживает обратных ссылок. А они жизненно необходимы для обработки текста (поиска-замен).

Добавлено через 5 минут
Еще пару слов насчет регулярных выражений в с#.
Они сделаны по стандарту Perl, но очень неудобны. Дело в том, что Perl автоматически компилирует (оптимизирует) регулярное выражение, которое не имеет интерполируемых переменных. Если регулярка встречается в цикле, то Perl компилирует его один раз (а не каждый раз, как пытается сделать c#). В с# приходится сначала создавать регулярку с флагом "компилировать", а только потом ее использовать. Причем, создавать регулярки приходится вне цикла, где идет обработка текста. Таким образом получается, что регулярки у вас определены в одной части экрана, а применяются в другой. Это очень неудобно.

Добавлено через 6 минут
"Таким образом получается, что регулярки у вас определены в одной части экрана, а применяются в другой. Это очень неудобно."

Собственно, как и в программе, которую я привел в сабже.

Добавлено через 11 минут
Кстати, насчет бенчарка. Там сразу видно несколько критичных ошибок в коде Perl. Например, в регулярных выражения используется альтернация квантифицируемых символов (конструкции вроде /a+|b*/). При этом регулярка будет нещадно тормозить. Это общая проблема регулярок на недетерминированных конечных автоматах. Хуже только двойные квантификаторы /([a-z]*)+/ - тогда время поиска вообще взлетает по экспоненте. Нужно альтернацию убирать в код: /a+/ || /b*/. Так будет реально на порядок быстрее. Код для бенчмарка писал человек, который Perl вчера увидел.
0
gromo
372 / 271 / 30
Регистрация: 04.09.2009
Сообщений: 1,214
26.11.2013, 21:35 #19
Цитата Сообщение от MrGluck Посмотреть сообщение
Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:
А поСимвольное считыавание должно быть быстрее?
0
MrGluck
26.11.2013, 22:12     с++11. Сильно тормозят регулярные выражения
  #20

Не по теме:

не прошло и года

0
26.11.2013, 22:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2013, 22:12
Привет! Вот еще темы с ответами:

Регулярные выражения
Помогите написать регулярку. Пишу на RE2. Если в тексте встречается...

[C++] Регулярные выражения
Знаю что в стандарте С нет регулярных выражений. Хочу попробывать собрать...

Регулярные выражения
Можете подсказать что это значит? &quot;Max-Forwards*(\d{3,}|7)&quot; я без понятия...

регулярные выражения
прочитал статю http://www.opennet.ru/base/dev/pcre_cpp.txt.html про регулярные...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru