C++并发实战15:函数式编程

来源:互联网 发布:淘宝扫二维码别人付款 编辑:IT博客网 时间:2019/09/17 14:57

1  函数式编程        

   函数y=f(x)就是个x->y的映射,其仅仅是x和y的关系,其运算关系仅仅是依赖参数x并不涉及其它外部状态,函数式编程中就把每个函数理解为数学意义上的函数f(x)。在函数式编程中,每个语句是一个表达式都是执行单纯的计算并有返回值,而C中的语句是执行某种操作如赋值,且计算是由函数完成的,仅仅依赖于输入参数。如一条简单的函数语句,功能是(1+2)*3-4:

var result = subtract (multiply (add (1,2), 3), 4); 
其运算过程是不同的函数组成的。函数和其它数据类型一样平等的,可以作为参数、返回值,且函数式编程中变量是不变的可以理解为都是const,这就表明函数式编程不改变对象的状态。函数内部不与外部互动(不会涉及修改全局变量等),从而利于并行化。函数编程还有个特点是具备重现能力。

         C++中本身也具有函数式的身影,比如:sin,cos这些函数。C++11中的lambda表达式,std::bind,std::function,std::auto均为函数式编程实现提供了可能。这里将采用函数式来简化并行化编程,在传统的并行化编程中涉及到共享内存、状态等,使用mutex、condition_variable等机制同步线程,而在函数式编程中每个函数只与输入参数相关且不修改外部状态,只负责计算,这使得某些并行化计算可以采用函数式编程思想。

         1.1 下面是传统的快速排序采用递归实现的例子:(非稳定排序)

template<typename T>std::list<T> sequential_quick_sort(std::list<T> input){   if(input.empty())   {     return input;   }   std::list<T> result;   result.splice(result.begin(),input,input.begin());//先将pivot元素放到result中,input开始的第二个元素前移到begin()    T const& pivot=*result.begin();//piovt元素引用    auto divide_point=std::partition(input.begin(),input.end(),[&](T const& t){return t<pivot;});//采用STL算法partition针对input分割,小于pivot的在前面,大于pivot在后面,返回第一个大于pivot元素的位置    std::list<T> lower_part;   lower_part.splice(lower_part.end(),input,input.begin(),divide_point);//将小于pivot的元素移动到lower_point中    auto new_lower(sequential_quick_sort(std::move(lower_part)));//递归排序小于pivot的元素,注意move的使用可以避免拷贝构造    auto new_higher(sequential_quick_sort(std::move(input)));//递归排序大于pivot的元素    result.splice(result.end(),new_higher);//将大于pivot的元素放于result后半部   result.splice(result.begin(),new_lower);//将小于pivot的元素置于pivot前面    return result;}


         1.2 使用future的函数式并行化重写1.1的快排:

template<typename T>std::list<T> parallel_quick_sort(std::list<T> input){   if(input.empty())   {      return input;   }   std::list<T> result;   result.splice(result.begin(),input,input.begin());//首先将pivot元素即input的第一个元素保存在result中   T const& pivot=*result.begin();   auto divide_point=std::partition(input.begin(),input.end(),[&](T const& t){return t<pivot;});   std::list<T> lower_part;   lower_part.splice(lower_part.end(),input,input.begin(),divide_point);   std::future<std::list<T> > new_lower(    std::async(&parallel_quick_sort<T>,std::move(lower_part)));//启动或选择一个空闲线程去完成快速排序,这里使用async是由于C++库保证高并发下是选择空闲线程还是创建一个新的线程去做,若是自己手动开启线程thread那么无疑面临线程过多导致上下文切换从而影响并发性能   auto new_higher(parallel_quick_sort(std::move(input)));    result.splice(result.end(),new_higher);    result.splice(result.begin(),new_lower.get());    return result;}



   2  communicating sequential processes(CSP)编程:没有共享数据,每个线程是独立的,单纯的依赖与传递给线程的消息,每个线程就是一个状态机当消息来到更新状态,并发送消息给其它线程,可以参考有限状态机模型。比如:HTTP请求状态:正在解析请求行、正在解析头部、解析中。一个HTTP服务端的例子:这里

CCIA中举的例子是ATM的简化程序片段:开始时run()状态变为wait_for_card,若有人插卡则执行send将消息发送给远程的银行数据库,并将状态置为getting_pin,由getting_pin()执行密码验证,然后存取款操作

struct card_inserted{  std::string account;};class atm{  messaging::receiver incoming;  messaging::sender bank;  messaging::sender interface_hardware;  void (atm::*state)();  std::string account;  std::string pin;  void waiting_for_card()   {    interface_hardware.send(display_enter_card());     incoming.wait().handle<card_inserted>(&](card_inserted const& msg)     {      account=msg.account;      pin="";      interface_hardware.send(display_enter_pin());      state=&atm::getting_pin;    }    );  }  void getting_pin();//密码验证public:  void run()   {    state=&atm::waiting_for_card;     try    {      for(;;)      {         (this->*state)();       }    }    catch(messaging::close_queue const&)    {    }  }};
      getting_pin()的实现:等待用户输入密码然后将状态更新为verifuing_pin,清除用户密码,完成密码验证将状态置为done_processing

void atm::getting_pin(){   incoming.wait()   .handle<digit_pressed>(    [&](digit_pressed const& msg)//等待用户输入密码   {     unsigned const pin_length=4;     pin+=msg.digit;     if(pin.length()==pin_length)     {        bank.send(verify_pin(account,pin,incoming));        state=&atm::verifying_pin;//更改状态     }   }   )   .handle<clear_last_pressed>(    [&](clear_last_pressed const& msg)//清除用户密码   {     if(!pin.empty())     {        pin.resize(pin.length()-1);     }   }   )   .handle<cancel_pressed>(    [&](cancel_pressed const& msg)//完成密码验证   {     state=&atm::done_processing;更改状态   }   );}



0 0
原创粉丝点击