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

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

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

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

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

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

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

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

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

Функция std::sample не добавляет случайные значения к пробным точкам с фиксированным шагом, она выбирает полностью случайные точки; поэтому в рамках данного примера работает несколько по-другому.

Как это делается

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

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