Russian Qt Forum

Qt => Кладовая готовых решений => Тема начата: m_ax от Январь 07, 2017, 22:18



Название: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 07, 2017, 22:18
В последнее время на форуме частенько возникают темы, в которых поднимается проблема поиска и замены выражений в тексте. И, казалось бы, никаких вопросов  возникать не должно, ведь у нас есть замечательный find/replace прямо из коробки, но.. Но стоит задачу чуть усложнить, т.е. не просто тупо замена одного на другое, а скажем замена по определенному правилу... И вот тут возникают вопросы, плодятся темы [http://www.prog.org.ru/topic_30197_0.html (http://www.prog.org.ru/topic_30197_0.html), http://www.prog.org.ru/topic_30885_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
 

Ну и приаттачиваю исходники с проектом.


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Racheengel от Январь 07, 2017, 22:57
Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.
А как у данного алгоритма с этим? Будет ли регэксп быстрее "заточенного" велика?


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 08, 2017, 15:42
Цитировать
Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.
Здесь и то и другое будет во много раз лучше штатного find/replace. Это очевидно.
Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.

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

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


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Igors от Январь 10, 2017, 13:55
Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.
Хмм.. ну а какую гибкость? Вариант типа "первое вхождение меняем на это, а второе - уже на то". Ну в принципе возможно, но редко

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

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


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 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 какая то хитрая стратегия аллокации памяти под капотом?  ???


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Racheengel от Январь 10, 2017, 14:04
Ну я так понимаю, регэксп надо тут только для того, чтобы начальные индексы слов найти.
Но, честно говоря, тяжело такое будет использовать.
Я бы API примерно так видел:

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

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


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 14:10
Цитировать
По поводу реализации: может не стоит формировать "список замен", а действовать "в лоб" в одном цикле замены.
Вот мне сейчас это тоже интересно.. Списки были нужны, чтоб знать точный размер итоговой строки, чтоб можно было вначале один раз отхватить кусок.

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

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


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 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 (http://www.prog.org.ru/topic_30197_0.html)
Ммм?  :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 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;
}
 


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 14:29
Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..) 


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 10, 2017, 14:33
Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..)  
Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....

Т.е. для вашего объема было выполнено 28 переаллокаций.


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 14:38
Цитировать
Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....
Да, действительно) Достаточно агрессивная стратегия)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: __Heaven__ от Январь 10, 2017, 14:46
Ещё бы spirit под Qt онли :) :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: __Heaven__ от Январь 10, 2017, 14:47
Вектора примерно также растут (QVector, std::vector под gcc и clang)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 10, 2017, 14:48
Вектора примерно также растут (QVector, std::vector под gcc и clang)
Не примерно, а ровно точно так (QVector, QByteArray, QList). :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 14:55
Цитировать
Т.е. для вашего объема было выполнено 28 переаллокаций.
Нет, я думаю, гораздо меньше.. В результирующую строку ведь идёт не посимвольная запись, а целыми кусками текста. И кусков таким порядка N штук, где N - число заменяемых фрагментов..  

Цитировать
Ещё бы spirit под Qt онли  :)  :)
Аха, spirit им ещё подавай  :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 10, 2017, 14:57
Нет, я думаю, гораздо меньше.. В результирующую строку ведь идёт не посимвольная запись, а целыми кусками текста. И кусков таким порядка N штук, где N - число заменяемых фрагментов..  
Да, 28 переалокаций было бы при посимвольном дополнении.


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Пантер от Январь 10, 2017, 14:58
Аха, spirit им ещё подавай  :)
Даёшь Qoost!


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 15:06
Цитировать
Даёшь Qoost!
;D Пссс.. /* шёпотом  */ Вы такими призывами некоторых товарищей до инфаркта доведёте..  ;D


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Igors от Январь 10, 2017, 15:16
QString qRegexReplace(const QString& text, const QMap<QString,QString>& replaceMap) const

и пользователь больше не имеет понятия ни о каком регэксп - оно меняет ключи на значения, а как - вопрос имплементации.
Не, ну так нет гибкости, к тому же если никакого регэксп нет, то зачем его поминать в имени ф-ции? Cимпатичнее напр так
Код
C++ (Qt)
template <class TRepl>
QString qCustomReplace( const QString& text, TRepl repl );
 
Пример реализации функтора
Код
C++ (Qt)
inline QStringRef OffsetRef( QStringRef & ref, int offs  )
{
return QStringRef(ref.string(), ref.position() + offs, ref.length() - offs);
}
 
QStringRef MyRepl( QStringRef & ref )
{
const int count = 2;
typedef QPair<QString, QString> TPair;
static const TPair data[count] = {
   TPair("$user", "terminator"),
   TPair("$version", "T1000")
};
 
// if (ref[0] != '$')  return QStringRef();  // возможная оптимизация
 
for (int i = 0; i < count; ++i)
  if (ref.startsWith(data[i].first)) {
   ref = OffsetRef(ref, data[i].first.size());
   return QStringRef(&data[i].second);
}
 
return QStringRef();   // пустая ссылка - замены не было (переход на след символ)
}
А для типового варианта с мапой запастись хвунктором-классом с конструктором принимающим напр ссылку на мапу

Нет, я просто перенёс идею, реализованную в boostе в Qt мир) Потому что в Qt из коробки такого решения нет, а тема, по видимому, актуальна для новичков) Вот и всё..
До этой идеи можно сэволюционировать и без буста  :)

Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..)  
Не стоит впадать в крайность, достаточно "боковым зрением" присматривать за числом malloc. Напр код выше можно запустить в 2 прохода, чтобы предвычислить длину рез-та, но по-моему это уже перегиб


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: m_ax от Январь 10, 2017, 16:00
Цитировать
Cимпатичнее напр так
Да, и заставлять пользователя брать на себя ответственность за разбор (в функторе) - опять проверять, отлаживаться и т.д.. А если завтра ситуация по сложней окажется?
Нет уж)

Цитировать
Напр код выше можно запустить в 2 прохода, чтобы предвычислить длину рез-та, но по-моему это уже перегиб
Да, согласен, перегиб.. 


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Igors от Январь 10, 2017, 16:19
Да, и заставлять пользователя брать на себя ответственность за разбор (в функторе) - опять проверять, отлаживаться и т.д.. А если завтра ситуация по сложней окажется?
Нет уж)
Так это так или иначе неизбежно - только он и знает правила замены, обобщать их в общем случае бесполезно. Просто здесь он избавлен от забот со "склейкой" выходной строки -  что очень неплохо


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 10, 2017, 16:33
Cимпатичнее напр так
Код
C++ (Qt)
template <class TRepl>
QString qCustomReplace( const QString& text, TRepl repl );
 
А что же так симпатично упрощает qCustomReplace для пользователя, если ему все равно приходиться каждый раз кодировать и поиск, и замену, в общем все? :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: __Heaven__ от Январь 10, 2017, 17:16
Примерно про std::vector. Лень по новой проверять, но было, кажется не 1024, а что-то около 1028.


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Racheengel от Январь 10, 2017, 17:40
Вот пару ссылочек в тему...

https://en.wikipedia.org/wiki/Overengineering

https://ru.wikipedia.org/wiki/%D0%91%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82



Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Old от Январь 10, 2017, 18:08
Вот пару ссылочек в тему...
У нас другая крайность. :)
Мы докатились до функции, которая ничего не делает. :)


Название: Re: qRegexReplace - аналог boost::regex_replace
Отправлено: Racheengel от Январь 11, 2017, 13:30
Цитировать
Я бы API примерно так видел:

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


Ну Вы привели пример задачи, в которой нужно просто заменить одни фиксированные значения на другие.
Я лишь имел в виду, что для этого использовать регулярки - оверхэд как по производительности, так и по "клиентскому" (вызывающему) коду.
А Ваша реализация лучше подойдет для более сложных примеров, как по ссылке, например :)