Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
#1

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

29.11.2012, 20:37. Просмотров 1473. Ответов 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 аналогичный скрипт отрабатывает за долю секунды. В чем может быть проблема, где код тормозит?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2012, 20:37     с++11. Сильно тормозят регулярные выражения
Посмотрите здесь:
C++ Регулярные выражения
C++ Регулярные выражения
С++ и регулярные выражения C++
C++ Регулярные выражения с++11
C++ Регулярные выражения
C++ Регулярные выражения
C++ регулярные выражения
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7969 / 4731 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
29.11.2012, 21:22     с++11. Сильно тормозят регулярные выражения #2
Suppir, boost::regex попробуйте, вполне возможно что стандартные регексы еще не оптимизированы. А так регекс в С++ вообще не быстрая штука, если что.
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 12:57  [ТС]     с++11. Сильно тормозят регулярные выражения #3
Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 15:15     с++11. Сильно тормозят регулярные выражения #4
Цитата Сообщение от Suppir Посмотреть сообщение
Мне кажется, медленно работают не только регулярные выражения, но и вот это место: getline(infile, line ).
Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 16:40  [ТС]     с++11. Сильно тормозят регулярные выражения #5
Цитата Сообщение от diagon Посмотреть сообщение
Это вряд ли. А каким компилятором вы пользуетесь? Возможно, вы не включаете оптимизации.
Пользуюсь Visual Studio 2012 for Desktop (бесплатная версия).
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 16:59     с++11. Сильно тормозят регулярные выражения #6
Suppir, компилите в релизе или дебаге?
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 22:15  [ТС]     с++11. Сильно тормозят регулярные выражения #7
В релизе немного побыстрей, но все равно медленней, чем Perl на порядок.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 22:20     с++11. Сильно тормозят регулярные выражения #8
Suppir, поищите на верхней панели инструментов слово Debug. и поменяйте его на релиз
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 22:22  [ТС]     с++11. Сильно тормозят регулярные выражения #9
Скорость программки на с++ получилась как у медленных скриптовых языков: Ruby или AutoIt.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
30.11.2012, 22:24     с++11. Сильно тормозят регулярные выражения #10
Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 22:25     с++11. Сильно тормозят регулярные выражения #11
Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 22:30  [ТС]     с++11. Сильно тормозят регулярные выражения #12
Цитата Сообщение от I.M. Посмотреть сообщение
Suppir, суть скрипта на перле такая же? там тоже построчное считывание? или сразу весь файл считывается?
Да, тоже построчно! Аналогичный скрипт на Perl:

Perl 6
1
2
3
4
5
open(IN, "c:\!\словарь.txt");
open(OU, ">c:\!\результат.txt");
while(<IN>){
    print OU if /^[а-я]{3}$/
}
Он работает на порядок быстрее (в 10 - 15 раз).
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
30.11.2012, 22:33     с++11. Сильно тормозят регулярные выражения #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) );
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 22:34  [ТС]     с++11. Сильно тормозят регулярные выражения #14
Цитата Сообщение от diagon Посмотреть сообщение
Регексы - достаточная новая штуковина в стандартном с++, к тому же вы используете далеко не лучший компилятор, поэтому ничего удивительного тут нету.
Но Perl же написан на том же си/с++, к тому же является интерпретатором (т.о. он должен быть медленней, чем скомпилированная программа).
Кстати, я пишу еще на c# около года. Так вот, на c# (.NET Framework 2.0) после всевозможных ухищрений удалось добиться скорости (в области обработки текста) в 2 раза меньше, чем у Perl. Я надеялся, что с++ пошустрее будет.
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.11.2012, 22:36     с++11. Сильно тормозят регулярные выражения #15
Кстати, есть такой бенчмарк.
Как видно из него бусторегексы более чем в 3 раза уступают по скорости гугловой либе(кстати, на первом месте тоже детище гугла), но все же почти в 2 раза быстрее перловых.
Это я к тому, что стоит использовать нормальные либы для регексов.
Suppir
24 / 24 / 3
Регистрация: 08.08.2011
Сообщений: 1,131
30.11.2012, 22:36  [ТС]     с++11. Сильно тормозят регулярные выражения #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) );
А как мне теперь пробежаться по каждой строке? Нужно ж еще разсплитить этот файл в массив.
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
30.11.2012, 22:36     с++11. Сильно тормозят регулярные выражения #17
Кстати, реализация регексов на VS может отличаться от реализации на gcc. Можно MinGW попробовать посмотреть, мб шустрее будет.

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

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

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

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

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

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

Или воспользуйтесь поиском по форуму:
MrGluck
26.11.2013, 22:12     с++11. Сильно тормозят регулярные выражения
  #20

Не по теме:

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

Yandex
Объявления
26.11.2013, 22:12     с++11. Сильно тормозят регулярные выражения
Ответ Создать тему
Опции темы

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