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

@Suppir · Регистрация: 08.08.2011

Добрый день!

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

C++

#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 аналогичный скрипт отрабатывает за долю секунды. В чем может быть проблема, где код тормозит?

@ForEveR · 29.11.2012, 21:22

Suppir, boost::regex попробуйте, вполне возможно что стандартные регексы еще не оптимизированы. А так регекс в С++ вообще не быстрая штука, если что.

@Suppir · 30.11.2012, 12:57 **[ТС]**

Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).

@diagon · 30.11.2012, 15:15

Сообщение от Suppir

Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).

Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.

@Suppir · 30.11.2012, 16:40 **[ТС]**

Сообщение от diagon

Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.

Пользуюсь Visual Studio 2012 for Desktop (бесплатная версия).

@I.M. · 30.11.2012, 16:59

Suppir, компилите в релизе или дебаге?

@Suppir · 30.11.2012, 22:15 **[ТС]**

В релизе немного побыстрей, но все равно медленней, чем Perl на порядок.

@I.M. · 30.11.2012, 22:20

Suppir, поищите на верхней панели инструментов слово Debug. и поменяйте его на релиз

@Suppir · 30.11.2012, 22:22 **[ТС]**

Скорость программки на с++ получилась как у медленных скриптовых языков: Ruby или AutoIt.

@I.M. · 30.11.2012, 22:24

Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?

@diagon · 30.11.2012, 22:25

Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.

@Suppir · 30.11.2012, 22:30 **[ТС]**

Сообщение от I.M.

Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?

Да, тоже построчно! Аналогичный скрипт на Perl:

Perl

open(IN, "c:\!\словарь.txt");
open(OU, ">c:\!\результат.txt");
while(<IN>){
    print OU if /^[а-я]{3}$/
}

Он работает на порядок быстрее (в 10 - 15 раз).

MrGluck · 30.11.2012, 22:33

Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:

C++

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) );

@Suppir · 30.11.2012, 22:34 **[ТС]**

Сообщение от diagon

Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.

Но Perl же написан на том же си/с++, к тому же является интерпретатором (т.о. он должен быть медленней, чем скомпилированная программа).
Кстати, я пишу еще на c# около года. Так вот, на c# (.NET Framework 2.0) после всевозможных ухищрений удалось добиться скорости (в области обработки текста) в 2 раза меньше, чем у Perl. Я надеялся, что с++ пошустрее будет.

@diagon · 30.11.2012, 22:36

Кстати, есть такой бенчмарк.
Как видно из него бусторегексы более чем в 3 раза уступают по скорости гугловой либе(кстати, на первом месте тоже детище гугла), но все же почти в 2 раза быстрее перловых.
Это я к тому, что стоит использовать нормальные либы для регексов.

@Suppir · 30.11.2012, 22:36 **[ТС]**

Сообщение от MrGluck

Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:

C++

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) );

А как мне теперь пробежаться по каждой строке? Нужно ж еще разсплитить этот файл в массив.

MrGluck · 30.11.2012, 22:36

Кстати, реализация регексов на VS может отличаться от реализации на gcc. Можно MinGW попробовать посмотреть, мб шустрее будет.

И да, буст регекс наверняка лучше реализован.

@Suppir · 30.11.2012, 23:04 **[ТС]**

Сообщение от diagon

Кстати, есть такой бенчмарк.
Как видно из него бусторегексы более чем в 3 раза уступают по скорости гугловой либе(кстати, на первом месте тоже детище гугла), но все же почти в 2 раза быстрее перловых.
Это я к тому, что стоит использовать нормальные либы для регексов.

Гуглолиба, вроде, имеет стандарт, аналогичный POSIX, т.е. не поддерживает обратных ссылок. А они жизненно необходимы для обработки текста (поиска-замен).

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

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

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

Добавлено через 11 минут
Кстати, насчет бенчарка. Там сразу видно несколько критичных ошибок в коде Perl. Например, в регулярных выражения используется альтернация квантифицируемых символов (конструкции вроде /a+|b*/). При этом регулярка будет нещадно тормозить. Это общая проблема регулярок на недетерминированных конечных автоматах. Хуже только двойные квантификаторы /([a-z]*)+/ - тогда время поиска вообще взлетает по экспоненте. Нужно альтернацию убирать в код: /a+/ || /b*/. Так будет реально на порядок быстрее. Код для бенчмарка писал человек, который Perl вчера увидел.

@gromo · 26.11.2013, 21:35

Сообщение от MrGluck

Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку:

А поСимвольное считыавание должно быть быстрее?

MrGluck · 26.11.2013, 22:12

Не по теме:

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

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	30.11.2012, 22:34 [ТС]	14
	Сообщение от diagon Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету. Но Perl же написан на том же си/с++, к тому же является интерпретатором (т.о. он должен быть медленней, чем скомпилированная программа). Кстати, я пишу еще на c# около года. Так вот, на c# (.NET Framework 2.0) после всевозможных ухищрений удалось добиться скорости (в области обработки текста) в 2 раза меньше, чем у Perl. Я надеялся, что с++ пошустрее будет. 0

MrGluck Форумчанин 8194 / 5044 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	30.11.2012, 22:36	17
	Кстати, реализация регексов на VS может отличаться от реализации на gcc. Можно MinGW попробовать посмотреть, мб шустрее будет. И да, буст регекс наверняка лучше реализован. 0

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	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 382 / 280 / 31 Регистрация: 04.09.2009 Сообщений: 1,225
	26.11.2013, 21:35	19
	Сообщение от MrGluck Вы в С++ считываете построчно, вот, считывает весь текст с файла в строку: А поСимвольное считыавание должно быть быстрее? 0

@ForEveR В астрале 8048 / 4805 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	29.11.2012, 21:22	2
	Suppir, boost::regex попробуйте, вполне возможно что стандартные регексы еще не оптимизированы. А так регекс в С++ вообще не быстрая штука, если что. 0

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	30.11.2012, 12:57 [ТС]	3
	Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ). 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	30.11.2012, 15:15	4
	Сообщение от Suppir Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ). Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации. 0

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	30.11.2012, 16:40 [ТС]	5
	Сообщение от diagon Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации. Пользуюсь Visual Studio 2012 for Desktop (бесплатная версия). 0

@I.M. 574 / 557 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	30.11.2012, 16:59	6
	Suppir, компилите в релизе или дебаге? 0

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	30.11.2012, 22:15 [ТС]	7
	В релизе немного побыстрей, но все равно медленней, чем Perl на порядок. 0

@I.M. 574 / 557 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	30.11.2012, 22:20	8
	Suppir, поищите на верхней панели инструментов слово Debug. и поменяйте его на релиз 0

@Suppir 26 / 26 / 11 Регистрация: 08.08.2011 Сообщений: 1,172
	30.11.2012, 22:22 [ТС]	9
	Скорость программки на с++ получилась как у медленных скриптовых языков: Ruby или AutoIt. 0

@I.M. 574 / 557 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	30.11.2012, 22:24	10
	Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	30.11.2012, 22:25	11
	Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету. 0

MrGluck
	26.11.2013, 22:12 с++11. Сильно тормозят регулярные выражения #20
	Не по теме: не прошло и года 0