Russian Qt Forum
Май 23, 2024, 22:59 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2   Вниз
  Печать  
Автор Тема: qRegexReplace - аналог boost::regex_replace  (Прочитано 17376 раз)
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« : Январь 07, 2017, 22:18 »

В последнее время на форуме частенько возникают темы, в которых поднимается проблема поиска и замены выражений в тексте. И, казалось бы, никаких вопросов  возникать не должно, ведь у нас есть замечательный find/replace прямо из коробки, но.. Но стоит задачу чуть усложнить, т.е. не просто тупо замена одного на другое, а скажем замена по определенному правилу... И вот тут возникают вопросы, плодятся темы [http://www.prog.org.ru/topic_30197_0.html, http://www.prog.org.ru/topic_30885_0.html] и рождаются велосипеды - хромые и одноразовые..  
Так вот, зачем изобретать велосипед, когда уже давно известен паттерн regex_replace с возможностью передачи в алгоритм своего, пользовательского форматера, который берёт на себя реализацию нетривиальных условий/правил при замене выражений?

Ну и запасясь пивом, семечками и водкой в этот субботний вечер, сел между делом и написал аналог regex_replace чисто на Qt. В качестве регулярки использовал класс QRegularExpression, как более последний.  

Значит какие типичные задачи, можно решать с помощью него? Вот один из примеров, взятый из недавней темы: имеется текст, который содержит некоторый набор различных тегов (список тегов известен) и необходимо заменить соответствующий тег неким специфичным для него значением. Значение для каждого тега мы знаем, т.е. у нас есть мап - (тег, значение). Ну и нужно заменить все теги их значениями за один проход!  
Т.е. для примера у нас есть строка:
Код
C++ (Qt)
QString str = "http://server.com/$user/docs/$version";
 
 
где теги это $user и $version
Мы хотим заменить $user на terminator, а $version на T1000.

С алгоритмом qRegexReplace это делается элементарно:
Код
C++ (Qt)
#include <QCoreApplication>
#include <QDebug>
#include <QMap>
 
#include "qregexreplace.h"
 
class Substitute
{
public:
   Substitute()
   {
       m_map["$user"] = "terminator";
       m_map["$version"] = "T1000";
   }
 
   QString operator()(const QString & match) const
   {
       auto it = m_map.find(match);
       if (it != m_map.end())
           return it.value();
 
       return match;
   }
 
private:
   QMap<QString, QString> m_map;
};
 
 
int main()
{
   QString str = "http://server.com/$user/docs/$version";
 
   QRegularExpression rx("(\\$\\w+)");
 
   qDebug() << qRegexReplace(str, rx, Substitute());
 
   return 0;
}
 
Это, конечно, очень упрощённый вариант - он только для наглядности. Но, думаю, идея понятна)

Сама реализация алгоритма qRegexReplace
Код
C++ (Qt)
#ifndef QREGEXREPLACE_H
#define QREGEXREPLACE_H
 
#include <QRegularExpression>
#include <QStringList>
#include <QStringRef>
#include <QList>
#include <QPair>
 
 
template <class FormatFunction>
QString qRegexReplace(const QString & input, const QRegularExpression & regex, FormatFunction formatFunc)
{
   int pos = 0;
   QString out;
   auto regexIt = regex.globalMatch(input);
   while (regexIt.hasNext())
   {
         QRegularExpressionMatch match = regexIt.next();
         QPair<int, int> r = qMakePair(match.capturedStart(1), match.capturedEnd(1));
         out.append(QStringRef(&input, pos, r.first-pos));
         out.append(formatFunc(match.captured(1)));
         pos = r.second;
   }
 
   out.append(QStringRef(&input, pos, input.size()-pos));
 
   return out;
}
 
#endif // QREGEXREPLACE_H
 

Ну и приаттачиваю исходники с проектом.
« Последнее редактирование: Январь 10, 2017, 20:53 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #1 : Январь 07, 2017, 22:57 »

Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.
А как у данного алгоритма с этим? Будет ли регэксп быстрее "заточенного" велика?
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #2 : Январь 08, 2017, 15:42 »

Цитировать
Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.
Здесь и то и другое будет во много раз лучше штатного find/replace. Это очевидно.
Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.

Цитировать
А как у данного алгоритма с этим? Будет ли регэксп быстрее "заточенного" велика?

Смотря какой регэксп и какой велик.. Вопрос в другом - всегда ли оправдано велосипедить ручной разбор, отлаживаться, делая различные проверки, тратя на это время, если такое решение абсолютно одноразово и не расширяемо? 
Лично для меня ответ очевиден (в подавляющем большинстве случаев) Улыбающийся 
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Январь 10, 2017, 13:55 »

Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.
Хмм.. ну а какую гибкость? Вариант типа "первое вхождение меняем на это, а второе - уже на то". Ну в принципе возможно, но редко

По поводу реализации: может не стоит формировать "список замен", а действовать "в лоб" в одном цикле замены. Кстати если (как в примере) мы все равно проверяем мапу, то почему бы и не обойтись вообще без рыгэкспа? (чуть другой велик)

Смотря какой регэксп и какой велик.. Вопрос в другом - всегда ли оправдано велосипедить ручной разбор, отлаживаться, делая различные проверки, тратя на это время, если такое решение абсолютно одноразово и не расширяемо? 
Лично для меня ответ очевиден (в подавляющем большинстве случаев) Улыбающийся 
А что Вы написали как не велик? (вполне в моем стиле Улыбающийся) И чем оно хуже отой дустовщины? Менее лаконично и меньше возможностей? Может быть, но это с лихвой компенсируется легкостью использования. Ах да, это же "только QString" - где же общность? Ничего, переживем
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #4 : Январь 10, 2017, 14:02 »

Решил тут сравнить по производительности две реализации qRegexReplace:
В первой реализации перед записью результирующей строки (QString out) высчитал её точный размер (каков будет её размер после замены текста) и после этого вызываю reserve:
Код
C++ (Qt)
QString out;
   out.reserve(input.size() - replacedTextLength + replacementTextLength);
 
для того, что бы избежать частых переаллокаций при вызове append вот здесь:
Код
C++ (Qt)
       out.append(QStringRef(&input, pos, r.first-pos));
       out.append(*it++);
 


И второй вариант - в лоб
Код
C++ (Qt)
template <class FormatFunction>
QString qRegexReplace(const QString & input, const QRegularExpression & regex, FormatFunction formatFunc)
{
   int pos = 0;
   QString out;
   auto regexIt = regex.globalMatch(input);
   while (regexIt.hasNext())
   {
         QRegularExpressionMatch match = regexIt.next();
         QPair<int, int> r = qMakePair(match.capturedStart(1), match.capturedEnd(1));
         out.append(QStringRef(&input, pos, r.first-pos));
         out.append(formatFunc(match.captured(1)));
         pos = r.second;
   }
 
   out.append(QStringRef(&input, pos, input.size()-pos));
 
   return out;
}
 

Наивно полагал, что последний вариант будет заметно медленнее, однако тесты показали что по времени оба варианта дают по порядку одинаковые результаты.  Размер файла для теста составлял примерно 123 Мб.  У QString какая то хитрая стратегия аллокации памяти под капотом?  Непонимающий
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #5 : Январь 10, 2017, 14:04 »

Ну я так понимаю, регэксп надо тут только для того, чтобы начальные индексы слов найти.
Но, честно говоря, тяжело такое будет использовать.
Я бы API примерно так видел:

QString qRegexReplace(const QString& text, const QMap<QString,QString>& replaceMap) const

и пользователь больше не имеет понятия ни о каком регэксп - оно меняет ключи на значения, а как - вопрос имплементации.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #6 : Январь 10, 2017, 14:10 »

Цитировать
По поводу реализации: может не стоит формировать "список замен", а действовать "в лоб" в одном цикле замены.
Вот мне сейчас это тоже интересно.. Списки были нужны, чтоб знать точный размер итоговой строки, чтоб можно было вначале один раз отхватить кусок.

Цитировать
Ах да, это же "только QString" - где же общность? Ничего, переживем
С QString сделал специально, специально только Qt онли) Специально для Qt пользователей)  

Цитировать
А что Вы написали как не велик? (вполне в моем стиле  Улыбающийся)
Нет, я просто перенёс идею, реализованную в boostе в Qt мир) Потому что в Qt из коробки такого решения нет, а тема, по видимому, актуальна для новичков) Вот и всё..
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #7 : Январь 10, 2017, 14:13 »

Цитировать
Я бы API примерно так видел:

QString qRegexReplace(const QString& text, const QMap<QString,QString>& replaceMap) const
Окей, как Вы тогда решите такую проблему: http://www.prog.org.ru/topic_30197_0.html
Ммм?  Улыбающийся
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #8 : Январь 10, 2017, 14:18 »

У QString какая то хитрая стратегия аллокации памяти под капотом?  Непонимающий

Код
C++ (Qt)
int qAllocMore(int alloc, int extra) Q_DECL_NOTHROW
{
   Q_ASSERT(alloc >= 0 && extra >= 0);
   Q_ASSERT_X(alloc <= MaxAllocSize - extra, "qAllocMore", "Requested size is too large!");
 
   unsigned nalloc = qNextPowerOfTwo(alloc + extra);
 
   Q_ASSERT(nalloc > unsigned(alloc + extra));
 
   return nalloc - extra;
}
 
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #9 : Январь 10, 2017, 14:29 »

Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..) 
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #10 : Январь 10, 2017, 14:33 »

Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..)  
Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....

Т.е. для вашего объема было выполнено 28 переаллокаций.
« Последнее редактирование: Январь 10, 2017, 14:36 от Old » Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #11 : Январь 10, 2017, 14:38 »

Цитировать
Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....
Да, действительно) Достаточно агрессивная стратегия)
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #12 : Январь 10, 2017, 14:46 »

Ещё бы spirit под Qt онли Улыбающийся Улыбающийся
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #13 : Январь 10, 2017, 14:47 »

Вектора примерно также растут (QVector, std::vector под gcc и clang)
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #14 : Январь 10, 2017, 14:48 »

Вектора примерно также растут (QVector, std::vector под gcc и clang)
Не примерно, а ровно точно так (QVector, QByteArray, QList). Улыбающийся
Записан
Страниц: [1] 2   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.166 секунд. Запросов: 22.