Регулярное выражение с QString

[Old]

Немного изменил тест. Теперь коллекция (hash/map) создается и заполняется каждый проход + добавил вывод коллекций для utf8 терминалов.

Код

C++ (Qt)
#include <QRegExp>
#include <QStringList>
#include <QFile>
#include <QTextStream>
#include <QTextCodec>
#include <QTime>
#include <QDebug>
 
template<typename Container>
void dump( const Container &c )
{
        QTextStream out( stdout );
        out.setCodec( QTextCodec::codecForName( "UTF8" ) );
 
        for( typename Container::ConstIterator it = c.constBegin(); it != c.constEnd(); ++it )
                out << "(" << it.key() << ", " << it.value() << ")";
        out << '\n';
}
 
int main( int argc, char *argv[] )
{
        QFile in( "test.txt" );
        if( !in.open( QIODevice::ReadOnly | QIODevice::Text ) )
        {
                qWarning( "Test file not found." );
                return 1;
        }
 
        const int num_iter = 100;
        QString src = QString::fromUtf8( in.readAll() );
 
        QTime tm;
 
        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QHash<QString, int>     hash;
                int start = 0;
                int cur = 0;
                QRegExp rx( "[\\s\\.,:;-()]+" );
                for(;;)
                {
                        cur = rx.indexIn( src, cur );
                        QString word = src.mid( start, (cur != -1)? cur - start : -1 );
                        if( !word.isEmpty() )
                                hash[ word ]++;
 
                        if( cur == -1 )
                                break;
 
                        start = ++cur;
                }
//              dump( hash );
        }
        qDebug() << tm.elapsed();
 
        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QMap <QString, int> MyMap;
                QStringList List = src.split(QRegExp("[\\s\\.,:;-()]+"),QString::SkipEmptyParts);
                foreach (QString Item, List) MyMap[Item] = (MyMap.contains(Item)) ? MyMap[Item]+1 : 1;
//              dump( MyMap );
        }
        qDebug() << tm.elapsed();
 
        return 0;
}
 

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

[Majestio]

Немного изменил тест. Теперь коллекция (hash/map) создается и заполняется каждый проход + добавил вывод коллекций для utf8 терминалов.

Код

C++ (Qt)
#include <QRegExp>
#include <QStringList>
#include <QFile>
#include <QTextStream>
#include <QTextCodec>
#include <QTime>
#include <QDebug>
 
template<typename Container>
void dump( const Container &c )
{
        QTextStream out( stdout );
        out.setCodec( QTextCodec::codecForName( "UTF8" ) );
 
        for( typename Container::ConstIterator it = c.constBegin(); it != c.constEnd(); ++it )
                out << "(" << it.key() << ", " << it.value() << ")";
        out << '\n';
}
 
int main( int argc, char *argv[] )
{
        QFile in( "test.txt" );
        if( !in.open( QIODevice::ReadOnly | QIODevice::Text ) )
        {
                qWarning( "Test file not found." );
                return 1;
        }
 
        const int num_iter = 100;
        QString src = QString::fromUtf8( in.readAll() );
 
        QTime tm;
 
        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QHash<QString, int>     hash;
                int start = 0;
                int cur = 0;
                QRegExp rx( "[\\s\\.,:;-()]+" );
                for(;;)
                {
                        cur = rx.indexIn( src, cur );
                        QString word = src.mid( start, (cur != -1)? cur - start : -1 );
                        if( !word.isEmpty() )
                                hash[ word ]++;
 
                        if( cur == -1 )
                                break;
 
                        start = ++cur;
                }
//              dump( hash );
        }
        qDebug() << tm.elapsed();
 
        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QMap <QString, int> MyMap;
                QStringList List = src.split(QRegExp("[\\s\\.,:;-()]+"),QString::SkipEmptyParts);
                foreach (QString Item, List) MyMap[Item] = (MyMap.contains(Item)) ? MyMap[Item]+1 : 1;
//              dump( MyMap );
        }
        qDebug() << tm.elapsed();
 
        return 0;
}
 

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

Первый тест мне показал:

31797
49750

Потом я кой чего "уровнял" (регулярка была ошибочной - знак минуса нужно квотить + у себя тоже использовал для справедливости QHash:) ... Результаты:

33844
36297

Так какое нафик в 4 раза?)))))) Ваш код быстрее на 10% ))))
Мой код в два раза меньше.
Какие коэффициенты оптимальности выставим??? ... Если равными - ну сами понимаете ))))

Зы: правленый код тут

Код:

#include <QRegExp>
#include <QStringList>
#include <QFile>
#include <QTextStream>
#include <QTextCodec>
#include <QTime>
#include <QDebug>

template<typename Container>
void dump( const Container &c )
{
        QTextStream out( stdout );
        out.setCodec( QTextCodec::codecForName( "UTF8" ) );

        for( typename Container::ConstIterator it = c.constBegin(); it != c.constEnd(); ++it )
                out << "(" << it.key() << ", " << it.value() << ")";
        out << '\n';
}

int main( int argc, char *argv[] )
{
        QFile in( "C:/Temp/test.txt" );
        if( !in.open( QIODevice::ReadOnly | QIODevice::Text ) )
        {
                qWarning( "Test file not found." );
                return 1;
        }

        const int num_iter = 100;
        QString src = QString::fromUtf8( in.readAll() );

        QTime tm;

        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QHash<QString, int>     hash;
                int start = 0;
                int cur = 0;
                QRegExp rx( "[\\s\\.,:;\\-()]+" );
                for(;;)
                {
                        cur = rx.indexIn( src, cur );
                        QString word = src.mid( start, (cur != -1)? cur - start : -1 );
                        if( !word.isEmpty() )
                                hash[ word ]++;

                        if( cur == -1 )
                                break;

                        start = ++cur;
                }
//              dump( hash );
        }
        qDebug() << tm.elapsed();

        tm.start();
        for( int i = 0; i < num_iter; ++i )
        {
                QHash <QString, int> MyMap;
                QStringList List = src.split(QRegExp("[\\s\\.,:;\\-()]+"),QString::SkipEmptyParts);
                foreach (QString Item, List) MyMap[Item] = (MyMap.contains(Item)) ? MyMap[Item]+1 : 1;
//              dump( MyMap );
        }
        qDebug() << tm.elapsed();

        return 0;
}

[Majestio]

))))) Добавочка ....

Чуть оптимизировал свой код ...

Вместо:

Код:

foreach (QString Item, List) MyMap[Item] = (MyMap.contains(Item)) ? MyMap[Item]+1 : 1;

Записал:

Код:

foreach (QString Item, List) MyMap[Item]++;

Результаты:
34016
34843

Ваш код быстрее на целых 3%! ))))

[m_ax]

Ваш код быстрее на целых 3%! ))))

Зато по памяти выигрыш более чем в два раза)

Ладно, чтоб никому не было обидно, привожу сравнение ваших результатов с алгоритмом boost::tokenizer:
Добавил все правки в код в соответствии с последними постами)

Код

C++ (Qt)
#include <QRegExp>
#include <QStringList>
#include <QFile>
#include <QTime>
#include <QDebug>
#include <string>
#include <boost/tokenizer.hpp>
#include <unordered_map>
#include <fstream>
#include <sstream>
 
int main()
{
    QFile in( "test.txt" );
    if( !in.open( QIODevice::ReadOnly | QIODevice::Text ) )
    {
        qWarning( "Test file not found." );
        return 1;
    }
 
    const int num_iter = 100;
    QString src = QString::fromUtf8( in.readAll() );
 
    QTime tm;
    unsigned total = 0;
 
    tm.start();
    for( int i = 0; i < num_iter; ++i )
    {
        QHash<QString, int>     hash;
        int start = 0;
        int cur = 0;
        QRegExp rx( "[\\s\\.,:;\\-()]+" );
        for(;;)
        {
            cur = rx.indexIn( src, cur );
            QString word = src.mid( start, (cur != -1)? cur - start : -1 );
            if( !word.isEmpty() )
                hash[ word ]++;
 
            if( cur == -1 )
                break;
 
            start = ++cur;
        }
        total = hash.size();
    //              dump( hash );
    }
    qDebug() << "Old:\t" << tm.elapsed() << total;
 
    tm.start();
    for( int i = 0; i < num_iter; ++i )
    {
        QHash <QString, int> MyMap;
        QStringList List = src.split(QRegExp("[\\s\\.,:;\\-()]+"),QString::SkipEmptyParts);
        foreach (QString Item, List) MyMap[Item]++;
 
        total = MyMap.size();
    //      dump( MyMap );
    }
    qDebug() << "Majestio:\t" << tm.elapsed() << total;
 
    std::ifstream in_("test.txt");
    if (!in_.is_open()) {
        qWarning( "Test file not found." );
        return 1;
    }
 
    std::ostringstream oss;
    oss << in_.rdbuf();
    std::string source = oss.str();
 
    tm.start();
    for( int i = 0; i < num_iter; ++i )
    {
        std::unordered_map<std::string, unsigned> hash;
        boost::tokenizer<boost::char_separator<char>> tok(source, boost::char_separator<char>(" ,.\r\t\n:;-()"));
        for (auto it = tok.begin(); it != tok.end(); ++it) ++hash[*it];
 
        total = hash.size();
    }
    qDebug() << "m_ax:\t" << tm.elapsed() << total;
 
    return 0;
}
 

И результаты у меня такие (release)

Код

Bash
Old:           15629 15211 
Majestio:    17590 15211 
m_ax:         9028  15211 
 

Хе, хе

[Old]

Ваш код быстрее на целых 3%! ))))

Не знаю почему у вас такие результаты, но у меня выигрыш примерно 10%, судя по результатам m_ax - у него примерно также.
Про двойной выигрыш по скорости я конечно погорячился (нес чего там ), но 10% это тоже не мало, к тому же с памятью проблем нет.

[Majestio]

Хе, хе

Вот не люблю я буст :-P

Ланна ... Резюме какое?
Берем "среднестатистический" текст. Какая разница для интерактивного режима 0.03сек или 0.02???. Какая разница (например для моего компа) - затратит он 700к памяти или полтора мега, если у меня 8Гб на борту? Остается смотреть на скорость и понятность кодинга. Не? :-P

Для эмпирического "потокового анализатора", как я уже говорил - только асм, только хардкор! :-P

[Majestio]

А m_ax - мошенник)))) давай на регулярках меряцца ))))

[Old]

Берем "среднестатистический" текст. Какая разница для интерактивного режима 0.03сек или 0.02???. Какая разница (например для моего компа) - затратит он 700к памяти или полтора мега, если у меня 8Гб на борту? Остается смотреть на скорость и понятность кодинга. Не? :-P

У каждого свой подход к оптимальности кода, я иногда месяцами пытаюсь выжать несколько процентов производительности.
А вообще, еще дельфи подтвердила, что все это глупости и для большинства современных программ, можно вообще ничего не оптимизировать и не о чем беспокоиться. Ну вылетит программ, ну запустит ее секретарша еще раз. Палец у нее не отвалиться.

[Igors]

В целом смысл ясен. Но вот опять же опыта маловато, что бы с легкостью это делать. Конечно в идеале раз увидеть как это последовательно делается. Либо более долгий путь ковырять исходники примеров и постепенно выстраивать свою структуру. Пока протаптываем дорожки и бегаем по проторенным. Как нибудь и эту протопчим .

Протопчем Последовательность простая

- создаете новые файлы cpp и h
- рисуете h файл, напр

Код

C++ (Qt)
#ifndef DAТABLOCK_H
#define DAТABLOCK_H
 
#include <QString>
struct CDataBlock {
  CDataBlock( void ) {};
  void Init( const QString & src ); 
 
//... члены данных как обсуждали выше
};
 
#endif  // DAТABLOCK_H
 

Дальше переносите все что можно из MainWindow в DataBlock.cpp. В результате "очищенный" метод выглядит примерно так

Код

C++ (Qt)
void MainWindow::bufferButtonSave()
{
    QClipboard *clipboard = QApplication::clipboard();
    mDataBlock.Init(clipboard->text());
    textory.clear();
    textory.enableAdd( true );
 
     QMapIterator<QString, int> it(mDataBlock.mFreqMap);
     while(it.hasNext())  {
        it.next();
        textory.addItem(Textory::Item(1, it.key() + "\t" + QString::number(it.value()));
     }
 
     QString total = QString::number(mDataBlock.mWords.size());
     ui.textoryWidget->getTextoryLabel().setText("Frequency list (" + total + ")" );
}

Это далеко от совершенства - никаких "выдач" пока нет, да и не очень хорошо лезть напрямую в члены класса (mDataBlock. ). Тем не менее схлопывание MainWindow налицо - анализатор занимается своим делом, UI - своим

[Majestio]

У каждого свой подход к оптимальности кода, я иногда месяцами пытаюсь выжать несколько процентов производительности.
А вообще, еще дельфи подтвердила, что все это глупости и для большинства современных программ, можно вообще ничего не оптимизировать и не о чем беспокоиться. Ну вылетит программ, ну запустит ее секретарша еще раз. Палец у нее не отвалиться.

В принципе - согласен. За исключением ошибок. Программа вылетать не должна. Под оптимальностью я понимаю соразмерность усилий и величину выигрыша (или минимизацию проигрыша). Ну а в своей практике пытаюсь следовать двум "китам" стратегии:

1) Закон (принцип) Паретто
2) Бритва Оккама

Всегда помогают. Рекомендую

[Igors]

Ну а в своей практике пытаюсь следовать двум "китам" стратегии:

В данном случае Вы не очень-то им следуете - впрочем как и остальные. Увлеклись частной задачей - как быстрейшим образом получить частоты (ассоциативный контейнер). Мне кажется здесь это не очень важно - годится любой приличный вариант. Важнее как гибко и удобно построить данные для разнообразных выдач. Напрашивается напр так

Код

C++ (Qt)
struct CData {
 ...
private:
 QString mSource;
 QVector <QStringRef> mWord;  // принципиально - храним слова
 QHash <QStringRef, int> mFrequency;  // возможно строить по запросу
};

В свете этого придется заменить бздошный split на что-то свое - ну это норм. Однако все это ускользнуло от внимания оптимизаторов 

[Majestio]

В данном случае Вы не очень-то им следуете - впрочем как и остальные. Увлеклись частной задачей - как быстрейшим образом получить частоты (ассоциативный контейнер).

Отнюдь. Затратив в 2 раза меньше времени на кодинг - получил результат на 3% хуже более скоростного. Профит на лицо. Принцип Паретто выполнен и перевыполнен. Более того, в других задачах (с нелинейными алгоритмами) мне придется исправить строчку-другую. Вам - сами подумайте)).

[Majestio]

Напрашивается напр так

Не напрашивается пока. Не плодите сущности без необходимости. Просили частоты - отдали хэш. Это все.

[Old]

Отнюдь. Затратив в 2 раза меньше времени на кодинг - получил результат на 3% хуже более скоростного. Профит на лицо. Принцип Паретто выполнен и перевыполнен.

Вот в этом и беда современной IT-индустрии. Поэтому и программы в своей массе все тормозят и требуют кучу ядер и памяти. В одной программе в одном месте на 10% просели, в другом на 15, в третьем 5. Вроде по отдельности мелочи, а программа работает на треть медленней. Ну это же фигня, пусть пользователь купит себе машину по быстрей.

Главный принцип в программировании это здравый смысл.

[Igors]

Не напрашивается пока. Не плодите сущности без необходимости. Просили частоты - отдали хэш. Это все.

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