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

оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
08.09.2012, 13:36     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #1
Здравствуйте.
По заданию требовалось составить программу для подсчета вхождений разных сочетаний букв с алфавита от 1 буквы до 4 в текстовый файл, размером 1 Мб. Т.е, например, для латиницы это a, b, c, ... z, aa, ... az, aaaa, ..., zzzz. Только алфавит надо было взять не латинский (я взял греческий). Результаты поиска записать в файл .csv через запятую. Программу то я написал, да вот выполняется она минут 80 (проц 2-х ядерный Intel D525 с частотой 1,8 ГГц), но все же, хотелось бы как-нибудь уменьшить эту цифру. Помогите оптимизировать алгоритм. Да, пишу под Linux.
Вот код:
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
class Alphabet
{
    int tick[N];
    std::vector<char> all;
    bool stop;
  public:
    Alphabet();
    void entry(std::string, std::ostream &);
    Alphabet& operator ++();
    bool isStop() {return stop; }
};  
 
unsigned long countEntry(const std::string &, const std::string &);
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    if(!ifstext)
    {
        std::cout<< "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));
    Alphabet a;
    std::cout<< "Please wait"<< std::endl;
    while (!a.isStop())
        (++a).entry(text, o);
    return 0;
}
 
unsigned long countEntry(const std::string &s, const std::string &delim)
{
    unsigned long counter = 0, found = s.find(delim); // found - number, where we start finding
    if (found != std::string::npos) counter++; // if in first position
    while(true)
    {
        found = s.find(delim, found + 1);
        if (found != std::string::npos) counter++;
        else break;
    }
    return counter;
}   
 
Alphabet::Alphabet()
{
    stop = false;
    for (int i=0; i < N; i++) 
        tick[i] = -1;
    for (int i=0x03E1; i < 0x03FA; i++)
        all.push_back( char(i) );
}
 
void Alphabet::entry(std::string text, std::ostream &o)
{
    if (stop) return;
    std::string str;
    for (int i=0; i < N; i++)
        if (tick[i] != -1)
           str.push_back( all[ tick[i] ] );
    o<< str<< ", "<< countEntry(text, str)<< std::endl;
}
 
Alphabet& Alphabet::operator ++()
{
    tick[N-1]++;
    for (int i = N-1; i > 0; i--) 
    if (tick[i] == all.size())
    {
        /*if (i == 1) // show new procent
        {
            std::cout<< "|";
            std::cout.flush(); // output stream buffer
        }*/
        tick[i - 1]++;
        tick[i] -= all.size();
    }
    if (tick[0] == all.size())
        stop = true;
    return *this;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2012, 13:36     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
Посмотрите здесь:

Строки.Текстовый файл. C++
C++ Что не так? Дан текстовый файл F. Переписать в другой файл G все строки, содержащие цифры.
C++ Текстовый файл состоит из нескольких строк. Записать во второй файл последние символы из каждой строки первого файла
Текстовый файл содержит строки – предложения разной длины. Записать их в выходной файл в порядке возрастания длины строки C++
Текстовый файл содержит строки – предложения разной длины. Записать их в выходной файл в порядке возрастания длины строки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.09.2012, 14:16     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #2
Эм. Делаете четыре массива: одномерный, двухмерный, трёхмерный и четырёхмерный. Размером, соответственно, сколько-букв-в-алфавите по каждому измерению. Заполняете нулями. Там мегабайт памяти или типа того на них надо для греческого.

Делаете четыре циклических буфера (на основе std::deque): на один, два, три и четыре символа соответственно.

Читаете файл посимвольно, если это не буква, ничего не делаем, если буква — заносим её во все буферы с конца. Если буфер полный, то предварительно выкидываем первый символ, чтобы в буфере всегда было один–четыре символа соответственно.

После каждого чтения буквы смотрим на полные буферы и делаем +1 в каждый из массивов по координатам, соответствующих символам, хранящимся в буфере.

В принципе, можно даже обойтись одним буфером на четыре символа. И одним четырёхмерным массивом (выделить, к примеру, двадцать пятую букву под меньшую размерность).
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.09.2012, 14:24     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #3
Смотри в сторону суффиксных деревьев. Есть хорошая книжка Гасфилда по алгоритмам на строках.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.09.2012, 14:26     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #4
fix:
если это не буква, ничего не делаем сбрасываем буферы
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.09.2012, 15:51     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #5
Дай свой файл для теста, напишу покажу что вышло.

П.С. алгоритмы http://e-maxx.ru/algo/prefix_function http://e-maxx.ru/algo/rabin_karp

Добавлено через 1 час 22 минуты
MrGluck, еще такой момент, я так и не понял ты ищешь вхождение 1 подстроки или массива
C++
1
{"a", "aaa", "aaaa", "aaaa", ..., "z", "zz", "zzz", "zzzz"}
?
Во втором случае тебе надо этот: http://e-maxx.ru/algo/aho_corasick
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
08.09.2012, 16:32  [ТС]     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #6
Спасибо, много полезной информации.
Файл с текстом. https://dl.dropbox.com/u/24221707/text.txt
А вхождения нужно искать для каждого сочетания от a до zzzz, а ответ выглядит например так:
a, 2011
b, 1789
...
zzzz 0
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.09.2012, 21:19     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #7
MrGluck, надо и прописные и строчные символы?

Добавлено через 27 минут
Никогда не любил комбинаторику...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
 
using namespace std;
 
int main () {
        register int i[4], res = 0, n = 'z'-'a';
        for (i[0] = 0; i[0] < n; ++i[0]) {
                for (i[1] = 0; i[1] < n; ++i[1]) {
                        for (i[2] = 0; i[2] < n; ++i[2]) {
                                for (i[3] = 0; i[3] < n; ++i[3]) {
                                        ++res;
                                }
                        }
                }
        }
        cout << res << endl;
}
output:
Bash
1
2
3
4
5
ruslan@ruslan-K53TA:~/Documents/StringTest$ vim test.cpp 
ruslan@ruslan-K53TA:~/Documents/StringTest$ g++ -x c++ test.cpp -c
ruslan@ruslan-K53TA:~/Documents/StringTest$ g++ test.o -o test
ruslan@ruslan-K53TA:~/Documents/StringTest$ ./test 
390625
У нас получается 390625 подстрок надо найти в файле с ~1M символов.
1. Здесь без вопросос только Ахо-Корасика надо
2. Можно еще распаралелить. Оптимальным количеством потоков считается N+2, где N - количество ядер процессора. Я бы для этого дела использовал boost::thread так как native pthread на линухе мне не нрав.

Раньше я мог дать оценку времени выполнения исходя с асимптотики, но сейчас мощности очень выросли, затрудняюсь ответить.

Добавлено через 3 минуты
UPD: Спец символы надо? Я видел в файле цифры, знаки препинания скобки...

Добавлено через 4 часа 12 минут
Мда, а гречесский текст найти сложно? Это не гречесский алфавит, и такст также. В гречесском алвафите всего 24 символа, а утебя около 28.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.09.2012, 22:07     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #8
Весело было поиграться с boost::program_options. Поищи в нете Ахо-Корасика готового и распаралеливание сделай.
Вложения
Тип файла: zip StringTest.zip (8.8 Кб, 10 просмотров)
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
09.09.2012, 02:31  [ТС]     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #9
outoftime, нужно только строчные с алфавита. В греческом 24 буквы, но одну особенную обозначают 2 символами (выходит 25, не задавать же диапазон из 2 отрезков).
Буду вкуривать Ахо-Карасика . Чувствую, много кофе уйдет. Распараллеливание пока точно не трону (лвл не тот).
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
09.09.2012, 13:10     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #10
MrGluck, а я наоборот, написал КМП и пробую распаралелить, еще добавил индикация прогресса. Кстати, если ты не заметил файл со строками что надо искать занимают 2.3 метра а сам текст 1 метр.

Добавлено через 10 часов 19 минут
Задача в лоб решается элементарно, полный перебор рулит.
Вложения
Тип файла: zip StringTest_fullcheck.zip (8.7 Кб, 10 просмотров)
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
09.09.2012, 16:20     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #11
http://paste.ubuntu.com/1193704/
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.09.2012, 13:20     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
Еще ссылки по теме:

C++ Дан исходный текстовый файл. Записать его строки в выходной файл в перевёрнутом виде
Алгоритм поиска строки в тексте C++
C++ Найти все вхождения строки P в текст T, используя наивный алгоритм поиска

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
10.09.2012, 13:20  [ТС]     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) #12
Почитав Ахо-Корасика и про суффиксальные деревья, меня натолкнула на мысль одна идея. Вот, в корни переделал алгоритм. Теперь выполняет за 15 секунд (для нетбука неплохо).
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
struct comp // comparison in map
{
    bool operator()(const std::string &str1, const std::string &str2)
    {
        return str1.length() == str2.length() ? str1 < str2 : str1.length() < str2.length();
    }
};
 
typedef std::map <std::string, unsigned int, comp> map_string_uint;
 
class Combinations
{
    map_string_uint allcomb;
    std::vector<char> alphabet;
  public:
    Combinations();
    void entry(const std::string &);
    void print(std::ostream &);
};
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    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) );
    std::cout<< "Text downloaded in buffer"<< std::endl;
    Combinations c;
    std::cout<< "Combinations compiled"<< std::endl;
    c.entry(text);
    std::cout<< "Writing results in file"<< std::endl;
    c.print(o);
    std::cout<< "Completed"<< std::endl;
    return 0;
}
 
Combinations::Combinations()
{
    for (int i=0x03E1; i < 0x03FA; i++) // forming alphabet
        alphabet.push_back( char(i) );
    int tick[N];
    std::fill(tick, tick + N-1, -1);
    tick[N-1] = 0;
    std::string str;
    while (tick[0] != alphabet.size())
    {
        // forming new combination
        str.clear();
        for (int i=0; i < N; i++)
            if (tick[i] != -1)
                str.push_back( alphabet[ tick[i] ] );
        allcomb.insert( std::make_pair(str, 0) );
        tick[N-1]++; // incriminating combination
        for (int i=N-1; i > 0; i--) // if need increase capacity (разрядность)
            if (tick[i] == alphabet.size())
            {
                tick[i - 1]++;
                tick[i] -= alphabet.size();
            }
    }
}
 
void Combinations::entry(const std::string &text)
{
    std::string buf;
    for (int i=0; i < text.length(); i++)
    {
        for (int j=0; j < N && i + j < text.length(); j++)
        {
            if (std::binary_search (alphabet.begin(), alphabet.end(), text[i + j]) )
                buf.push_back( text[i + j] );
            else break;
        }
        // incriminating counter
        if (!buf.empty() )
        { 
            ++allcomb[buf];
            buf.clear();
        }
    }
}                
 
void Combinations::print(std::ostream &o)
{
    std::for_each(allcomb.begin(), allcomb.end(), [&o](const std::pair <std::string, int> &p)
        { o<< p.first<< ", "<< p.second<< std::endl; } );
}
Добавлено через 29 минут
С компаратором неверно считает... Почему?

Добавлено через 17 часов 40 минут
Исправил ошибку, вот конечный исходник. Результаты работы совпадают с результатами брутаса (1 вариант).
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
struct comp // comparison in map
{
    bool operator()(const std::string &str1, const std::string &str2) const
    {
        return (str1.length() == str2.length() ? str1 < str2 : str1.length() < str2.length() );
    }
};
 
typedef std::map <std::string, unsigned int, comp> map_string_uint;
 
class Combinations
{
    map_string_uint allcomb;
    std::vector<char> alphabet;
  public:
    Combinations();
    void entry(const std::string &);
    void print(std::ostream &);
};
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    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) );
    std::cout<< "Text downloaded in buffer"<< std::endl;
    Combinations c;
    std::cout<< "Combinations compiled"<< std::endl;
    c.entry(text);
    std::cout<< "Writing results in file"<< std::endl;
    c.print(o);
    std::cout<< "Completed"<< std::endl;
    return 0;
}
 
Combinations::Combinations()
{
    for (int i=0x03E1; i < 0x03FA; i++) // forming alphabet
        alphabet.push_back( char(i) );
    int tick[N];
    std::fill(tick, tick + N-1, -1);
    tick[N-1] = 0;
    std::string str;
    while (tick[0] != alphabet.size())
    {
        // forming new combination
        str.clear();
        for (int i=0; i < N; i++)
            if (tick[i] != -1)
                str.push_back( alphabet[ tick[i] ] );
        allcomb.insert( std::make_pair(str, 0) );
        tick[N-1]++; // incriminating combination
        for (int i=N-1; i > 0; i--) // if need increase capacity (разрядность)
            if (tick[i] == alphabet.size())
            {
                tick[i - 1]++;
                tick[i] -= alphabet.size();
            }
    }
}
 
void Combinations::entry(const std::string &text)
{
    std::string buf;
    for (int i=0; i < text.length(); i++)
    {
        for (int j=0; j < N && i + j < text.length(); j++)
        {
            if (std::binary_search (alphabet.begin(), alphabet.end(), text[i + j]) )
            {
                buf.push_back( text[i + j] );
                ++allcomb[buf]; // incriminating counter
            }
            else break;
        }
        buf.clear();
    }
}                
 
void Combinations::print(std::ostream &o)
{
    std::for_each(allcomb.begin(), allcomb.end(), [&o](const std::pair <std::string, int> &p)
        { o<< p.first<< ", "<< p.second<< std::endl; } );
}
Yandex
Объявления
10.09.2012, 13:20     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
Ответ Создать тему
Опции темы

Текущее время: 09:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru