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},
Поделиться книгой в соц сетях:
Обратите внимание, что комментарий должен быть не короче 20 символов. Покажите уважение к себе и другим пользователям!