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

Дополнительная информация

Можно добавить в каждый узел дерева переменные-счетчики. Это позволит определить, как часто префикс встречается в некоторых входных данных. На основе этой информации можно отсортировать предположения по частоте их встречаемости, что и делают поисковики. Подсказки, возникающие при наборе текста на смартфоне, также реализованы подобным образом.

Предлагаю вам создать этот вариант генератора подсказок в качестве самостоятельного упражнения. 

Реализуем формулу преобразования Фурье с применением численных алгоритмов STL

Преобразование Фурье — это очень важная и очень известная формула в области обработки сигналов. Она была открыта примерно 200 лет назад, но с появлением компьютеров количество вариантов ее использования значительно увеличилось. Она применяется при сжатии аудио/изображений/видео, в аудиофильтрах, медицинских устройствах отображения, приложениях для телефонов, которые определяют, какая песня сейчас играет, и т.д.

Поскольку количество возможных вариантов применения данной формулы довольно велико (и не только преобразования Фурье), STL разрабатывалась так, чтобы приносить пользу и при выполнении вычислений. Преобразование Фурье — лишь один из многих примеров подобных вычислений, при этом не самый простой. Сама формула выглядит так (рис. 6.3):

Преобразование, описываемое этой формулой, по сути, описывает сумму. Каждый элемент суммы является произведением точки графика вектора входного сигнала и выражения exp(-2*i*...). Вычисления, стоящие за даннойформулой, могут озадачить всех, кто незнаком с комплексными числами (и тех, кому просто не нравится математика), но освоить пример можно и не понимая эту формулу полностью. Если взглянуть на нее поближе, то увидим, что все точки графика сигнала (N элементов) суммируются с помощью переменной цикла j. Переменная k — еще одна переменная цикла, поскольку преобразование Фурье вычисляет не одно значение, а целый вектор. В данном векторе каждая точка графика представляет собой интенсивность и фазу определенной частоты повторяющейся волны. При реализации этой формулы с помощью циклов получится примерно такой код:

csignal fourier_transform(const csignal &s) {

  csignal t(s.size());

  const double pol {-2.0 * M_PI / s.size()};

  for (size_t k {0}; k < s.size(); ++k) {

    for (size_t j {0}; j < s.size(); ++j) {

      t[k] += s[j] * polar(1.0, pol * k * j);

    }

  }

  return t;

}

Тип csignal может быть вектором, содержащим комплексные числа. Для работы с такими числами в STL существует класс std::complex. Функция std::polar, по сути, выполняет часть exp(–i*2*...).

Эта версия работает хорошо, но давайте реализуем преобразование Фурье с помощью инструментов, доступных в STL.

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

В данном примере мы реализуем преобразование Фурье, а затем трансформируем с его помощью некоторые сигналы.

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

#include <iostream>

#include <complex>

#include <vector>

#include <algorithm>

#include <iterator>

#include <numeric>

#include <valarray>

#include <cmath>

using namespace std;

2. Точка графика сигнала представляет собой комплексное число, которое будет выражено с помощью типажа std::complex, специализированного для типа double. Таким образом, псевдоним типа cmplx будет расшифровываться в виде двух связанных значений типа double, которые представляют действительную и мнимую части комплексного числа. Весь сигнал представляет собой вектор, содержащий подобные элементы; назовем этот тип csignal:

using cmplx = complex<double>;

using csignal = vector<cmplx>;

3. Чтобы проитерировать по возрастающей численной последовательности, мы возьмем численный итератор из соответствующего примера. Переменные k и j и формулы преобразования будут итерировать по подобным последовательностям.

class num_iterator {

  size_t i;

public:

  explicit num_iterator(size_t position) : i{position} {}

  size_t operator*() const { return i; }

  num_iterator& operator++() {

    ++i;

    return *this;

  }

  bool operator!=(const num_iterator &other) const {

    return i != other.i;

  }

};

4. Функция преобразования Фурье будет принимать сигнал и возвращать новый. Последний представляет собой преобразование Фурье, выполненное для входного сигнала. Обратное преобразование Фурье выполняется аналогично прямому, поэтому предоставим необязательный параметр булева типа, который указывает на направление преобразования. Обратите внимание: наличие подобных параметров зачастую указывает на плохой стиль программирования, особенно если в сигнатуре функции их несколько. Здесь мы для краткости применили всего один параметр булева типа.

Первое, что нужно сделать, — это выделить память для нового вектора сигналов, имеющего размер исходного сигнала:

csignal fourier_transform(const csignal &s, bool back = false)

{

  csignal t (s.size());

5. В формуле имеются два множителя, которые всегда выглядят одинаково. Поместим их в отдельные переменные:

  const double pol {2.0 * M_PI * (back ? -1.0 : 1.0)};

  const double div {back ? 1.0 : double(s.size())};

6. Алгоритм std::accumulate отлично подходит для выполнения формул, которые складывают элементы. Мы воспользуемся им для диапазона увеличивающихся численных значений. На основе этих значений можно сформировать отдельные слагаемые для каждого шага. Алгоритм std::accumulate на каждом шаге вызывает бинарную функцию. Первым параметром данной функции будет текущее значение части суммы, которая уже была подсчитана на предыдущих шагах, а второй параметр — следующее значение диапазона. Мы выполняем поиск значения сигнала s в текущей позиции и умножаем его на комплексный множитель, pol. Затем возвращаем новую частичную сумму. Бинарная функция обернута в другое лямбда-выражение, так как мы станем использовать разные значения переменной j при каждом вызове алгоритма accumulate. Поскольку этот алгоритм цикла двумерный, внутреннее лямбда-выражение применяется для внутреннего цикла, а внешнее — для внешнего.

  auto sum_up ([=, &s] (size_t j) {

    return [=, &s] (cmplx c, size_t k) {

      return c + s[k] *

        polar(1.0, pol * k * j / double(s.size()));

    };

  });

7. Внутренняя часть преобразования Фурье теперь выполняется алгоритмом std::accumulate. Для каждой позиции алгоритма, кратной j, подсчитываем сумму всех слагаемых для позиций i = 0...N. Эта идея оборачивается в лямбда-выражение, которое мы будем выполнять для каждой точки графика полученного вектора преобразования Фурье:

  auto to_ft ([=, &s](size_t j){

    return accumulate(num_iterator{0},