Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
#1

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

02.11.2013, 12:12. Просмотров 648. Ответов 11
Метки нет (Все метки)

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*?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2013, 12:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как ускорить работу (поиск вхождений подстроки)? (C++):

Как подсчитать количество вхождений подстроки в строку - C++
Добрый вечер! Как можно подсчитать количество вхождений строки S2 в строку S1? Допустим: S1= dfsgsffgsrr S2= gs

Как ускорить работу? - C++
Прога ещё не доработана, сейчас интересует именно графический режим, когда нажимается клавиша 1-4 один из 4-х квадратов должен...

Как ускорить работу с файлами? - C++
Предполагается, что программа будет работать с файлами размера 300-500МБ. Эти обычные функции работают слишком медленно. Может быть стоит...

Подскажите пожалуйста как ускорить работу программы! - C++
Есть задача :&quot;Во входном файле (вы можете читать данные из файла input.txt) записан текст. Словом считается последовательность непробельных...

Можно ли как нибудь ускорить работу цикла for? - C++
Подскажите пожалуйста - можно ли как нибудь ускорить работу цикла for? Заранее сильно благодарен!

Динамический массив, много циклов и простые числа. Как ускорить работу программы ? - C++
Всем привет. Задание следующее: Кто нибудь вводит с клавиатуры число n и k, должен создастся массив из чисел от 1 до n, далее каждый...

11
Avazart
Эксперт С++
7232 / 5428 / 303
Регистрация: 10.12.2010
Сообщений: 24,123
Записей в блоге: 17
02.11.2013, 15:42 #2
Про STL слыхали?
0
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
02.11.2013, 20:35  [ТС] #3
как бы я использую stl. Но факт в том что std:: string работает медленнее char*. А возвращяться к char* не хочу, а как более оптимизировать это не знаю.
0
Avazart
Эксперт С++
7232 / 5428 / 303
Регистрация: 10.12.2010
Сообщений: 24,123
Записей в блоге: 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() на каждом шагу цикла, такие вещи желательно выносить, за цикл.
0
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,295
Завершенные тесты: 1
03.11.2013, 12:31 #5
Цитата Сообщение от zeratul47 Посмотреть сообщение
Вопрос: могу ли я как-то ускорить работу этой функции, не переходя к использованию char*?
Конечно. У твоего кода просто ужасная алгоритмическая сложность. Посмотри на алгоритм Укконена и суффиксные деревья.
1
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() на каждом шагу цикла, такие вещи желательно выносить, за цикл.
Насколько я знаю, там реализовано точное совпадение строк без замен, что мне не подходит.
0
Avazart
Эксперт С++
7232 / 5428 / 303
Регистрация: 10.12.2010
Сообщений: 24,123
Записей в блоге: 17
03.11.2013, 16:05 #7
Цитата Сообщение от zeratul47 Посмотреть сообщение
Насколько я знаю, там реализовано точное совпадение строк без замен, что мне не подходит.
А использовать алгоритм, со своим копоратором, не ?

Добавлено через 2 минуты
http://www.cplusplus.com/reference/algorithm/search/?kw=search
0
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
03.11.2013, 20:40  [ТС] #8
Глупый вопрос, но обращение по итераторам идет быстрее?
0
Avazart
Эксперт С++
7232 / 5428 / 303
Регистрация: 10.12.2010
Сообщений: 24,123
Записей в блоге: 17
03.11.2013, 20:51 #9
Цитата Сообщение от zeratul47 Посмотреть сообщение
Глупый вопрос, но обращение по итераторам идет быстрее?
Чем что?
Быстрее чем по индексу, но не факт из-за оптимизации компилятором...

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

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

http://ru.wikipedia.org/wiki/Boost
0
zeratul47
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 6
04.11.2013, 11:30  [ТС] #12
Цитата Сообщение от Avazart Посмотреть сообщение
пенок под зад тоже дает ускорение и чЁ ?
чувствую себя днищем(
0
04.11.2013, 11:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2013, 11:30
Привет! Вот еще темы с ответами:

Подсчет вхождений подстроки в строку - C++
Здравствуйте, помогите найти ошибку, в файле есть строки например S1gfgd S2vsdfvbf S1ffgv необходимо подсчитать сколько раз...

Функция замены всех вхождений подстроки - C++
Необходимо написать функцию типа функции PHP str_replace , которая возвращает строку, в которой все вхождения search заменены на replace....

Найти количество и места вхождений подстроки в строку - C++
Всем привет, есть задача, где нужно найти количество и места вхождений подстроки в строку, но она немного не стандартна, то есть в...

Определить количество вхождений подстроки в заданную строку - C++
Определить количество вхождений подстроки в заданную строку.. Добавлено через 3 часа 57 минут Вообщем сам допер. Если кому...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.