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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Количество цифр после точки http://www.cyberforum.ru/cpp-beginners/thread648534.html
Можно ли посчитать количество цифр после точки в числе, введенном пользователем?
C++ Найти положительные действительные Задается любое положительное действительное число R. Найти положительные действительные R1,R2,...,Rn, Ri<4,i=1,...,n, такие, что R=R1*R2*...*Rn=R1+R2+...+Rn http://www.cyberforum.ru/cpp-beginners/thread648531.html
C++ Вызов функции, использующей vector, из dll
Всем привет! Проблема в следующем: есть dll-ка, в ней 3 простых функции: 1. Sum - сложение 2х целых чисел. 2. Concat - соединяет 2 строки. 3. GetFirst - возвращает 1й элемент вектора, переданного ей в качестве параметра. Далее эта длл динамически загружается, и первые две функции отлично определяются и работают. А вот 3я - нет, программа ее не видит. Как это исправить? Причем интересует...
Бинарный файл C++
Удалить из бинарного файла, в котором записаны целые числа все четные элементы.
C++ Найти сумму квадратов элементов четвертого столбца / k-й строки матрицы http://www.cyberforum.ru/cpp-beginners/thread648528.html
Дан двухмерный массив. Определить: 1. Сумму квадратов элементов четвертого столбца массива. 2. Сумму квадратов элементов k-й строки массива.
C++ Сформировать массив А из четных элементов исходного массива, а массив В - из нечетных Элементы массива Т формируются по правилу: Т(к)=15к-12. Сформировать массив А из четных элементов массива Т, а массив В- из нечетных(к=20) подробнее

Показать сообщение отдельно
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
10.09.2012, 13:20  [ТС]     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
Почитав Ахо-Корасика и про суффиксальные деревья, меня натолкнула на мысль одна идея. Вот, в корни переделал алгоритм. Теперь выполняет за 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; } );
}
 
Текущее время: 14:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru