C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

std::search для строк и опробуем ее разные вариации для объектов класса searcher.

1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include <iostream>

#include <string>

#include <algorithm>

#include <iterator>

#include <functional>

using namespace std;

2. Мы будем выводить на экран подстроки из позиций, которые вернет алгоритм поиска, поэтому реализуем соответствующую вспомогательную функцию:

template <typename Itr>

static void print(Itr it, size_t chars)

{

  copy_n(it, chars, ostream_iterator<char>{cout});

  cout << 'n';

}

3. Строка вида lorem-ipsum сгодится в качестве примера, мы будем искать в ней подстроку. В нашем случае таковой выступит сочетание "elitr":

int main()

{

  const string long_string {

    "Lorem ipsum dolor sit amet, consetetur"

    " sadipscing elitr, sed diam nonumy eirmod"};

  const string needle {"elitr"};

4. Старый интерфейс std::search принимает начальный/конечный итераторы для строки, внутри которой мы будем искать конкретную подстроку. Он возвращает итератор, указывающий на подстроку, которую смог найти. Если поиск не удался, то он вернет конечный итератор:

  {

    auto match (search(begin(long_string), end(long_string),

                       begin(needle), end(needle)));

    print(match, 5);

}

5. Версия функции std::search, предлагаемая в C++17, принимает не две пары итераторов, а одну (начальный/конечный) и объект поиска. Объект std::default_searcher принимает пару итераторов для подстроки, которую мы ищем в более крупной строке:

  {

    auto match (search(begin(long_string), end(long_string),

        default_searcher(begin(needle), end(needle))));

    print(match, 5);

  }

6. Суть этого изменения заключается в том, что так проще сменить алгоритм поиска. Объект std::boyer_moore_searcher использует поисковый алгоритм Бойера — Мура, чтобы выполнять поиск несколько быстрее:

  {

    auto match (search(begin(long_string), end(long_string),

         boyer_moore_searcher(begin(needle),

                              end(needle))));

    print(match, 5);

  }

7. В библиотеке STL версии C++17 появились три разные реализации поискового объекта. Третья реализация использует алгоритм Бойера—Мура—Хорспула.

  {

    auto match (search(begin(long_string), end(long_string),

        boyer_moore_horspool_searcher(begin(needle),

                                      end(needle))));

    print(match, 5);

  }

}

8. Скомпилируем и запустим программу. Если все работает правильно, то мы должны увидеть несколько одинаковых строк:

$ ./pattern_search_string

elitr

elitr

elitr

elitr

Как это работает

Мы воспользовались четырьмя разными способами применения функции std::search, чтобы получить одинаковые результаты. Какая функция больше подходит для конкретной ситуации?

Предположим, что наша большая строка, в которой мы будем искать шаблон, называется s, а сам шаблон — p. Тогда выражения std::search(begin(s), end(s), begin(p), end(p)); и std::search(begin(s), end(s), default_searcher(begin(p), end(p)); станут делать одно и то же.

Другие поисковые объекты функций реализуют более сложные алгоритмы поиска:

□ std::default_searcher — выполняет переадресацию к устаревшей реализации std::search;

□ std::boyer_moore_searcher — использует поисковый алгоритм Бойера — Мура;

□ std::boyer_moore_horspool_searcher — по аналогии применяет алгоритм Бойера — Мура — Хорспула.

Что делает другие алгоритмы такими особенными? Алгоритм Бойера — Мура разрабатывали, опираясь на конкретную идею: шаблон поиска сравнивается со строкой, начиная с конца шаблона и двигаясь справа налево. Если символ в строке для поиска отличается от символа шаблона на перекрывающихся позициях и даже не встречается в шаблоне, то становится очевидно, что последний можно сместить в строке поиска на количество позиций, равное его длине. Взгляните на рис. 5.3, где это происходит в шаге 1. Если же символ, для которого в данный момент выполняется сравнение, отличается от символа шаблона на этой позиции, но при этом есть в шаблоне, то алгоритм знает, на сколько символов нужно сместить шаблон вправо, чтобы правильно выровнять его относительно этого символа, а затем начинается новая итерация сравнения справа налево. На рис. 5.3 это происходит в шаге 2. Таким образом, алгоритм Бойера — Мура может опустить множество ненужных операций сравнения, в отличие от исходной реализации поиска.

Конечно, этот алгоритм мог бы стать алгоритмом поиска по умолчанию, если бы вам не пришлось идти на компромиссы. Он работает быстрее алгоритма по умолчанию, но его следует использовать для структур данных быстрого поиска, чтобы определить, какие символы содержатся в шаблоне поиска и насколько они смещены. Компилятор выберет их сложную реализацию в зависимости от типов данных, хранящихся в шаблоне (они могут варьироваться от ассоциативных массивов, основанных на хеше, для сложных типов до примитивных справочных таблиц для типов наподобие char). В конечном счете это значит следующее: реализация поиска по умолчанию будет более быстрой при условии, что поисковая строка не слишком велика. Если сам поиск занимает много времени, то использование алгоритма Бойера — Мура может привести к повышению производительности в измерении постоянного коэффициента.

Алгоритм Бойера — Мура — Хорспула является упрощением описанного алгоритма Бойера — Мура. В нем нет правила о плохом символе, что приводит к сдвигу всей длины шаблона, если искомый символ не встречается в найденной строке. Компромисс в принятии такого решения заключается в том, что первый алгоритм работает несколько медленнее, чем второй, но в процессе ему требуется меньше структур данных.

 

 Не пытайтесь определить, какой алгоритм будет работать быстрее в конкретных случаях. Всегда измеряйте производительность кода с помощью диапазонов данных, типичных для ваших пользователей, и основывайте свое решение на результатах этих измерений.

Делаем выборку данных из крупных векторов

При взаимодействии с очень большими объемами численных данных иногда возникают ситуации, когда их нужно обработать за оптимальное время. В одних случаях можно воспользоваться выборкой, чтобы снизить общий объем данных для дальнейшей обработки, что ускорит выполнение всей программы. В других это можно сделать с целью сократить объем операций не для обработки, а для сохранения или передачи данных.

Исходная реализация выборки представляет собой рассмотрение только N-ных точек. Это приемлемо в большинстве случаев, но для обработки сигналов, например, может привести к математическому феномену, который называется искажением. Если расстояние между пробными точками отличается на небольшую случайную величину, то искажение можно сократить. На рис. 5.4 продемонстрирован крайний случай только для того, чтобы показать эту точку: хотя исходный сигнал выражается в виде синусоидальной волны, треугольные точки на графике являются пробными и взяты с одинаковым шагом 100. К сожалению, сигнал