Параллельное программирование на С++ в действии

Но достоинства функционального программирования проявляются не только в языках, где эта парадигма применяется по умолчанию. С++ — мультипарадигменный язык, и на нем, безусловно, можно писать программы в стиле ФП. С появлением в С++11 лямбда-функций (см. приложение А, раздел А.6), включением шаблона std::bind из Boost и TR1 и добавлением автоматического выведения типа переменных (см. приложение А, раздел А.7) это стало даже проще, чем в С++98. Будущие результаты — это последний элемент из тех, что позволяют реализовать на С++ параллелизм в стиле ФП; благодаря передаче будущих результатов результат одного вычисления можно сделать зависящим от результата другого без явного доступа к разделяемым данным.

Быстрая сортировка в духе ФП

Чтобы продемонстрировать использование будущих результатов при написании параллельных программ в духе ФП, рассмотрим простую реализацию алгоритма быстрой сортировки Quicksort. Основная идея алгоритма проста: имея список значений, выбрать некий опорный элемент и разбить список на две части — в одну войдут элементы, меньшие опорного, в другую — большие или равные опорному. Отсортированный список получается путем сортировки обоих частей и объединения трех списков: отсортированного множества элементов, меньших опорного элемента, самого опорного элемента и отсортированного множества элементов, больших или равных опорному элементу. На рис. 4.2 показано, как этот алгоритм сортирует список из 10 целых чисел. В листинге ниже приведена последовательная реализация алгоритма в духе ФП; в ней список принимается и возвращается по значению, а не сортируется по месту в std::sort().

Рис. 4.2. Рекурсивная сортировка в духе ФП

Листинг 4.12. Последовательная реализация Quicksort в духе ФП

template

std::list sequential_quick_sort(std::list input) {

 if (input.empty()) {

  return input;

 }

 std::list result;

 result.splice(result.begin(), input, input.begin());←(1)

 T const& pivot = *result.begin();                   ←(2)

 auto divide_point = std::partition(input.begin(), input.end(),

  [&](T const& t) { return t < pivot; });←(3)

 std::list lower_part;

 lower_part.splice(

  lower_part.end(), input, input.begin(), divide_point); ←(4)

 auto new_lower(

  sequential_quick_sort(std::move(lower_part)));         ←(5)

 auto new_higher(

  sequential_quick_sort(std::move(input)));              ←(6)

 result.splice(result.end(), new_higher);  ←(7)

 result.splice(result.begin(), new_lower); ←(8)

 return result;

}

Хотя интерфейс выдержан в духе ФП, прямое применение ФП привело бы к неоправданно большому числу операций копирования, поэтому внутри мы используем «обычный» императивный стиль. В качестве опорного мы выбираем первый элемент и отрезаем его от списка с помощью функции splice() (1). Потенциально это может привести к неоптимальной сортировке (в терминах количества операций сравнения и обмена), но любой другой подход при работе с std::list может существенно увеличить время за счет обхода списка. Мы знаем, что этот элемент должен войти в результат, поэтому можем сразу поместить его в список, где результат будет храниться. Далее мы хотим использовать этот элемент для сравнения, поэтому берем ссылку на него, чтобы избежать копирования (2). Теперь можно с помощью алгоритма std::partition разбить последовательность на две части: меньшие опорного элемента и не меньшие опорного элемента (3). Критерий разбиения проще всего задать с помощью лямбда-функции; мы запоминаем ссылку в замыкании, чтобы не копировать значение pivot (подробнее о лямбда-функциях см. в разделе А.5 приложения А).

Алгоритм std::partition() переупорядочивает список на месте и возвращает итератор, указывающий на первый элемент, который не меньше опорного значения. Полный тип итератора довольно длинный, поэтому мы используем спецификатор типа auto, чтобы компилятор вывел его самостоятельно (см. приложение А, раздел А.7).