0

Имеется массив (1-10 элементов), состоящий из длинных (до 10000 символов) неизменяемых строк. Так же имеется одна (такая же длинная) строка, которая активно изменяется. Строки из массива очень активно сравниваются с изменяемой строкой.

К функциям добавил inline, к изменяемой строке добавил register, программа всё равно работает медленно. Массив строк реализован как string*, другая строка - просто string.

Скажите пожалуйста, как можно ускорить выполнение программы? Будет ли string.erase работать быстрее string.substr? Или в данном случае вообще лучше использовать классические char'овые строки вместо string'ов?

Заранее благодарен!

UPD: добавил немного кода

строка min-str не изменяется (просто хранит значение для sub-str) ( '_' не вставляется в сообщение)

sub_str = min_str.substr(j, i);

После того, как sub-str получает значение, проверяется выполнение функции

if (is_inside(sub_str, str, amount))

А это, собственно, сама функция, которая проверяет, входит ли подстрока во все строки заданного массива.

inline bool is_inside(string sub_str, string *str, int n)
{
    int m = 0;
    for (int i = 0; i < n; i++)
    {
        if ( str[i].find(sub_str) != -1 ) { m++ ;}
    }
    if (m == n) { return true; }
    else { return false; }
}

Только что понял, что программа должна работать быстрее, если я в функцию буду передавать значения по ссылке (или указателю). Есть ещё предложения?

7
  • если внутри inline функции есть цикл то она автоматически становится обычной
    – perfect
    19 фев 2013 в 17:24
  • register для строки не поможет. Показывайте код, как строкой манипулируете, может там в цикле складываете посимвольно, что очень медленно будет. Но можно заведомо сразу выделить немного места - быстрее будет.
    – KoVadim
    19 фев 2013 в 17:24
  • Какие именно действия вы проводите с изменяемой строкой? Может быть, вам нужно rope или вообще связный список символов? Не пытайтесь мелкими подсказками компилятору выиграть в скорости, компиляторы сегодня не глупее нас с вами. Надо оптимизировать алгоритм и структуры данных.
    – VladD
    19 фев 2013 в 17:27
  • @perfect: очччччень компиляторозависимо.
    – VladD
    19 фев 2013 в 17:28
  • @Артём Девятов, а как именно сравниваются?
    – user6550
    19 фев 2013 в 17:32

3 ответа 3

7

Замечания по коду:
1. Передаем строку по ссылке
2. Прединкремент работает быстрее постинкремента
3. Искать не все вхождения, а первое
4. Правильно сравнивать с std::string::npos, а не с -1

Только эти микрооптимизации не сильно помогут, ибо оптимизируется наивный и неэффективный алгоритм со сложностью O(k * N * N) где к - количество элементов массива, N максимальная длина строки.
Замените std::string::find на быстрые КМП или Бойера-Мура и получите O(k * N)
Ахо-Корасик не подойдет, т.к. решает обратную задачу.

PS. раз изменяется только искомая строка, можно подумать о специализированном алгоритме на основе префикс-функции.

8
  • @Dith: <зануда mode on>насчёт 2. я бы всё же заметил, что (1) для POD-типов преинкремент и постинкремент одинаковы, и (2) хороший оптимизатор (gcc, MSVC, Clang, Intel Compiler, Comeau) заметит, что результат не нужен, и произведёт одинаковый код.<зануда mode off>
    – VladD
    20 фев 2013 в 11:53
  • @Dith: но +1 за микрооптимизации и анализ сложности алгоритма. --- А разве КМП индексирует haystack?
    – VladD
    20 фев 2013 в 11:54
  • Спасибо, мне тоже показалось, что Ахо-Корасик решает немного другую задачу. А насчёт 4 пункта - пришлось, скрипя зубами, написать -1, потому что npos в g++ не компилировался (в MSVS компилировался) 20 фев 2013 в 13:22
  • 1
    @VladD Момент спорный, дабы не разводить холивары сошлюсь на наиболее авторитетный источник: Саттер/Александреску - Стандарты программирования C++, совет 9 и 28.
    – Dith
    22 фев 2013 в 1:59
  • 1
    @Dith, не знаю, что имел в виду авторитет по поводу пре/пост инкрементов, но как и следовало ожидать, код функции автора что с i++, m++, что c ++i, ++m оттранслированный g++ -S одинаков. Коды, полученные g++ -S -O3 естественно тоже совпадают.
    – avp
    22 фев 2013 в 12:09
4

Для начала, можно упростить код сравнения до вот такого:

bool is_inside(const string& sub_str, string str[], int n)
{
    for (int i = 0; i < n; i++)
    {
        if ( str[i].find(sub_str) == -1 )
            return false;
    }
    return true;
}

Поскольку если вы уж нашли несовпадение, дальше можно не проверять.

Затем, вычислять подстроку -- излишнее копирование данных. Передавайте массив символов (по ссылке, конечно), и два индекса:

char* min_str_data = min_str.c_str(); // вычисляется один раз

if (is_inside(min_str_data, j, i, str, amount)) // ...

bool is_inside(
        const char* whole_str, int start_idx, int len,
        string str[], int n)
{
    for (int i = 0; i < n; i++)
    {
        if (str[i].find(whole_str, j, i) == -1)
            return false;
    }
    return true;
}

Так должно быть немного скорее.

Кроме того, уже давно не надо писать inline: смысл этого ключевого слова не совсем такой, как вы думаете.

4
  • Гениально! Метод от противного действительно будет работать намного быстрее А что насчёт стрингов и чаров? 19 фев 2013 в 17:47
  • @Артём Девятов: добавил.
    – VladD
    19 фев 2013 в 17:52
  • В if (str[i].find(whole_str, j, i) == -1) надо -1 заменить на string::npos. Замена string на char[] скорее всего выигрыша не даст. Строго говоря, оно, конечно, зависит от реализации string, так что я бы тупо реализовал и замерил скорость. 22 фев 2013 в 2:47
  • @Пётр Таран: ТС писал, что у него проблемы с npos, a -1 срабатывает. Моя замена не для ускорениям а для того, чтобы избежать ненужного копирования данных: substr создаёт копию данных, а нам она не нужна. А без substr не обойтись: std::string::find не имеет перегрузки с std::string, начальным индексом и длиной.
    – VladD
    22 фев 2013 в 11:28
1

Вычислять хэш для строк. Очевидно, что для статичных строк это надо сделать один раз. Рекомендую алгоритм FNV-1a, даже его 32-битный вариант очень хорош и крайне редко даёт коллизии. Для перестраховки можно взять 64-битный вариант, а вообще есть и 1024-битный.

unsigned long long fnv64_hash(const char* s)
{
    unsigned long long h = 14695981039346656037LL;
    while( *s ) {
        h ^= (unsigned long long)*s++;
        h *= 1099511628211LL;
    }
    return h;
}
4
  • И как это приложить к вопросу автора? Вычислить fnv для всех возможных подстрок в массиве неизменяемых строк? -- Если уж всерьез заниматься ускорением поиска в описанной задачке, то наверное надо бы для каждой неизменной строки (в которой ищут подстроки) сделать индекс пар символов (в худшем случае 64K штук на строку), адресующий позиции таких пар в строке. И вместо .find подстроки по всей строке смотреть strncmp искомой подстроки только в этих точках. Если распределение символов в строках более-менее равномерное, то для строк по 10000 символов (IMHO) все будет просто летать...
    – avp
    21 апр 2014 в 13:57
  • Цитирую топикстартера: Имеется массив (1-10 элементов), состоящий из длинных (до 10000 символов) неизменяемых строк. Так же имеется одна (такая же длинная) строка, которая активно изменяется. Строки из массива очень активно сравниваются с изменяемой строкой. Изменяем строку, вычисляем ее хэш. Если хэш совпал с одним из хэшей для неизменямой строки - значит, изменяемая строка совпала с ней (99.9999999%, но для полной уверенности можно strcmp сделать). Может, я чего-то недопонял? Может, я тут один такой дурак, который понимает буквально то, что видит, а другие додумывают, как бы играя в шарады 21 апр 2014 в 17:19
  • 1
    @VadimTukaev, отвечая на старые вопросы (от февраля 13-го года), желательно читать еще и уже сделанные ответы и комментарии. Обычно открывается много информации, которую изначально автор не отобразил в первых строках своего вопроса. Например, inline bool is_inside(string sub_str, string *str, int n) { int m = 0; for (int i = 0; i < n; i++) { if ( str[i].find(sub_str) != -1 ) { m++ ;} .... и т.п., вокруг чего, собственно, и шла основная часть обсуждения здесь.
    – avp
    21 апр 2014 в 18:32
  • Это проблемы автора, не так ли? Я дал правильный ответ на тот вопрос, что он задал. Если у него другой вопрос - пусть задаёт другой вопрос. hashcode.ru/questions/18428/… 22 апр 2014 в 6:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.