FP

/**
 * 使用操作同步来简化代码 - 带有future的函数式编程（FP）
 * 
 * 才有函数式的方法来编写程序，并非直接在线程之间共享数据；
 * 而是每个任务都可以提供它所需要的数据，并通过使用future将结果传播至需要它的线程
 * 
 * future是使得C++FP风格的并发切实可行的最后一块拼图；
 * 一个future可以在线程之间来回传递，使得一个线程的计算结果以来于另一个的结果，而无需任何对共享数据的显示访问。
 * 
 * 这个风格的快速排序是用list，因为list的splice方法
 * 如果用vector，估计要用算法库里面的算法，而且性能可能不是很高；
 * 因为splice是直接移动的指针，不需要拷贝，这是链表的优势所在
 */

#include <list>
#include <iostream>
#include <algorithm>
#include <future>
using namespace std;

// 1.FP风格快速排序
template<typename T>
list<T> sequential_quick_sort(list<T> input)
{
    if(input.empty())
    {
        return input;
    }
    list<T> result;
    // 将input中的input.begin()这个元素转移到result.begin()的位置
    // 不是复制或移动元素，而是重指向链表节点的内部指针，原指针实效，被移除
    // 所以可以把solice勉强的看成是可移动的
    result.splice(result.begin(),input,input.begin());
    // 使用引用，避免复制,中轴值
    const T &pivot = *result.begin();
    // 将序列划分成小于中轴值的和不小于中轴值的，返回第一个不小于中轴值的迭代起
    auto divide_point = partition(input.begin(),input.end(),[&](const T &t){
        return t < pivot;
    });
    // 新建一个存放小于的容器，大于等于的可以存放在原容器
    list<T> lower_part;
    // 将序列小于中轴值的部分转移到lower_part列表
    // 这样lower_part全是小于中轴值的元素，input还剩下大于等于中轴值的元素
    lower_part.splice(lower_part.end(),input,input.begin(),divide_point);
    // 使用递归分别对小于中轴值的序列进行同样的操作，使用移动，防止拷贝
    auto new_lower(sequential_quick_sort(move(lower_part)));
    // 使用递归对大于等于中轴值的序列进行同样的操作，使用移动，防止拷贝
    auto new_higher(sequential_quick_sort(move(input)));
    // 最后将结果进行正确的拼接，把大于等于的部分拼接到中轴值的后面
    result.splice(result.end(),new_higher);
    // 把小于的部分，拼接到中轴值的前面
    result.splice(result.begin(),new_lower);
    // 返回最终结果
    return result;
}

// FP风格并行快速排序
template<typename T>
list<T> parallel_quick_sort(list<T> input)
{
    if(input.empty())
    {
        return input;
    }
    list<T> result;
    result.splice(result.begin(),input,input.begin());
    const T &pivot = *result.begin();
    auto divide_point = partition(input.begin(),input.end(),[&](const T &t){
        return t<pivot;
    });
    list<T> lower_part;
    lower_part.splice(lower_part.begin(),input,input.begin(),divide_point);
    // 这种并发是否有用？前面的结果总是要等后面的结果才可以返回；
    // 结果和结果之间是需要等待的，但是两部分是可以同时进行的，所以并发还是有一定的作用。
    future<list<T>> new_lower(async(&parallel_quick_sort<T>,move(lower_part)));
    future<list<T>> new_higher(async(&parallel_quick_sort<T>,move(input)));
    // auto new_higher(parallel_quick_sort(move(input)));
    result.splice(result.end(),new_higher.get());
    result.splice(result.begin(),new_lower.get());
    return result;
}

int main()
{
    list<int> t{2,34,4,1,5,63,3,24,5,6};
    //list<int> value = sequential_quick_sort(t);
    list<int> value = parallel_quick_sort(t);
    for (auto &&i : value)
    {
        cout << i << " ";
    }
    cout << endl;
    exit(0);
}

CSP

• CSP基于消息传递的同步操作
• CSP的思想很简单，如果没有共享数据，则每一个线程可以完全独立的运行；
• 只需要基于它对所接收到的信息如果进行反映
• 由于线程天生就是共享全局数据的，所以程序员必须保证：
• 不会在线程之间共享数据，只在线程之间共享消息队列，
• 既然要有这种封装性，就可以封装成类
• 很可能会使用状态机的思想
• 不同的角色对应不同的线程，成为角色模型