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

Как ускорить работу (поиск вхождений подстроки)? - C++

Восстановить пароль Регистрация
 
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
02.11.2013, 12:12     Как ускорить работу (поиск вхождений подстроки)? #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//подсчет kf
int NumberKF(string &P, vector<string> & F, const int f){
    int kf =0;
    for(size_t i = 0; i < f; ++i){                  //обход по всем строкам
        for(size_t j = 0; j < F[i].size() - P.size() +1; ++j){      //по всем подстрокам длины l
            bool b = true;
            for(int g = 0; g < P.size(); ++g){                      //проверка входжения
                if ((P[g] != F[i][j+g]) && (P[g] != 'N')){
                    b = false;
                                        break;
                }
            }
            if (b) {++kf;}          //если да то увеличиваем kf
        }
    }
    return kf;
}
Ищем возможные вхождения подстроки P в массиве строк F. Символ N в контексте задачи - джокер, т.е. может "являться" любым другим символом.
Например:
AATCGT
ANNCGN
Такие подстроки совпадут.
Вопрос: могу ли я как-то ускорить работу этой функции, не переходя к использованию char*?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2013, 12:12     Как ускорить работу (поиск вхождений подстроки)?
Посмотрите здесь:

Как подсчитать количество вхождений подстроки в строку C++
указатели (посчитать кол-во вхождений подстроки в строку) C++
C++ Определить количество вхождений подстроки в заданную строку
C++ Динамический массив, много циклов и простые числа. Как ускорить работу программы ?
Подскажите пожалуйста как ускорить работу программы! C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
02.11.2013, 15:42     Как ускорить работу (поиск вхождений подстроки)? #2
Про STL слыхали?
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
02.11.2013, 20:35  [ТС]     Как ускорить работу (поиск вхождений подстроки)? #3
как бы я использую stl. Но факт в том что std:: string работает медленнее char*. А возвращяться к char* не хочу, а как более оптимизировать это не знаю.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
02.11.2013, 23:41     Как ускорить работу (поиск вхождений подстроки)? #4
Цитата Сообщение от zeratul47 Посмотреть сообщение
как бы я использую stl.
Если вы тупо вписали типы STL это не значит что вы используете STL...
Почитайте про итераторы и алгоритмы, ну и про сами контейнеры.

К примеру в std::string уже реализован поиск подстроки http://www.cplusplus.com/reference/string/string/find/

Добавлено через 9 минут
Кроме того то что вы
Цитата Сообщение от zeratul47 Посмотреть сообщение
C++
1
for(size_t j = 0; j < F[i].size() - P.size() +1; ++j){ //по всем подстрокам длины l
Ясно что это совсем не оптимально считать .size() на каждом шагу цикла, такие вещи желательно выносить, за цикл.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
03.11.2013, 12:31     Как ускорить работу (поиск вхождений подстроки)? #5
Цитата Сообщение от zeratul47 Посмотреть сообщение
Вопрос: могу ли я как-то ускорить работу этой функции, не переходя к использованию char*?
Конечно. У твоего кода просто ужасная алгоритмическая сложность. Посмотри на алгоритм Укконена и суффиксные деревья.
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
03.11.2013, 15:40  [ТС]     Как ускорить работу (поиск вхождений подстроки)? #6
Цитата Сообщение от Avazart Посмотреть сообщение
Если вы тупо вписали типы STL это не значит что вы используете STL...
Почитайте про итераторы и алгоритмы, ну и про сами контейнеры.

К примеру в std::string уже реализован поиск подстроки http://www.cplusplus.com/reference/string/string/find/

Добавлено через 9 минут
Кроме того то что вы

Ясно что это совсем не оптимально считать .size() на каждом шагу цикла, такие вещи желательно выносить, за цикл.
Насколько я знаю, там реализовано точное совпадение строк без замен, что мне не подходит.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
03.11.2013, 16:05     Как ускорить работу (поиск вхождений подстроки)? #7
Цитата Сообщение от zeratul47 Посмотреть сообщение
Насколько я знаю, там реализовано точное совпадение строк без замен, что мне не подходит.
А использовать алгоритм, со своим копоратором, не ?

Добавлено через 2 минуты
http://www.cplusplus.com/reference/a...rch/?kw=search
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
03.11.2013, 20:40  [ТС]     Как ускорить работу (поиск вхождений подстроки)? #8
Глупый вопрос, но обращение по итераторам идет быстрее?
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
03.11.2013, 20:51     Как ускорить работу (поиск вхождений подстроки)? #9
Цитата Сообщение от zeratul47 Посмотреть сообщение
Глупый вопрос, но обращение по итераторам идет быстрее?
Чем что?
Быстрее чем по индексу, но не факт из-за оптимизации компилятором...

Но я это не о скорости, а о стиле.
Ясное дело что если хочется добиться наибольшей скорости то иногда приходится опускаться на уровень ниже (к Си или даже Asm) и бо там может быть больше возможностей для оптимизации алгоритма.

Добавлено через 5 минут
Вот только понять не могу почему эта тема в разделе boost ?
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
03.11.2013, 22:51  [ТС]     Как ускорить работу (поиск вхождений подстроки)? #10
Цитата Сообщение от Avazart Посмотреть сообщение
Вот только понять не могу почему эта тема в разделе boost ?
Потому что:
а) я новичок на форуме
б) boost вроде ускорение
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
03.11.2013, 23:07     Как ускорить работу (поиск вхождений подстроки)? #11
Цитата Сообщение от zeratul47 Посмотреть сообщение
б) boost вроде ускорение
пенок под зад тоже дает ускорение и чЁ ?

http://ru.wikipedia.org/wiki/Boost
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2013, 11:30     Как ускорить работу (поиск вхождений подстроки)?
Еще ссылки по теме:

Как ускорить работу? C++
C++ Найти количество и места вхождений подстроки в строку
C++ Можно ли как нибудь ускорить работу цикла for?

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

Или воспользуйтесь поиском по форуму:
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
04.11.2013, 11:30  [ТС]     Как ускорить работу (поиск вхождений подстроки)? #12
Цитата Сообщение от Avazart Посмотреть сообщение
пенок под зад тоже дает ускорение и чЁ ?
чувствую себя днищем(
Yandex
Объявления
04.11.2013, 11:30     Как ускорить работу (поиск вхождений подстроки)?
Ответ Создать тему
Опции темы

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