Форум программистов, компьютерный форум 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) подробнее

Показать сообщение отдельно
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.09.2012, 21:19     оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
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.
 
Текущее время: 06:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru