设为首页收藏本站

ISO/IEC C++ China Unofficial

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 410|回复: 7

fib到Y

[复制链接]

9

主题

25

帖子

137

积分

注册会员

魔理魔理魔~

Rank: 2

威望
5
经验
97
贡献
5
发表于 2015-12-19 20:54:03 | 显示全部楼层 |阅读模式
本帖最后由 帅气可爱魔理沙 于 2015-12-19 05:01 编辑

我们今天只要解很简单的数学题:
我们有一对很可爱的小萝莉小正太兔子,它们一个月后会成为大兔子,在此之后会不停的啪啪啪,每个月生一对兔子,请问第N个月有多小对兔子?
这道题怎么听起来这么眼熟?
没错,这就是fib函数,写起来很简单:
用clang的小伙伴们注意,本文的代码在clang开优化下会崩(还以为我写错了

size_t fib( size_t i ) {
  return i < 2 ? i : fib( i - 1 ) + fib( i - 2 ); }
如果我们要把这个函数写成匿名表达式,使得我们可以很简单的在更多地方创建,并且传入其他函数呢? 我们先试试看很naive的approach吧:
auto fib = [&](size_t i) -> size_t {
  return i < 2 ? i : fib( i - 1 ) + fib( i - 2 ); };
很不幸的,
1:这还是表达式,这是语句,换句话说你不能直接塞在表达式里面
2:这根本过不了编译那我们怎么办?很简单:既然外面的fib引用不了,直接当参数传进来就好了!
template< typename F >
struct fix_struct
{
  F f;
  template< typename T >
  auto operator ( )( const T & arg ) const {
    return f( f, arg ); }
};
template< typename F >
auto fix( const F & f ) { return fix_struct< F > { f }; }
定义了这个helper以后,我们接下来的任务就很简单了:
fix( [](const auto & self, size_t i) -> size_t {
  return i < 2 ? i :
    self( self, i - 1 ) + self( self, i - 2 ); } )
有一点值得一提,由于这里让编译器推导会无限循环,我们要自己提供返回类型 这样子,第一个参数就是函数自身,任务完美解决!
...除了一点:我们每次调用self的时候总是要把自己传回去,麻烦而毫无作用-我们第一个参数永远只会是self.
那末有没有办法抽象掉,让我们不需要写?
如果我们要填上这个洞,我们要先考虑:什么地方可以不加上self就调用整个fib函数?
auto operator ( )( const T & arg ) const {
答案并不难找:我们再一次把fix_struct传进去就可以了
template< typename F >
struct fix_struct
{
  F f;
  template< typename T >
  auto operator ( )( const T & arg ) const { return f( *this, arg ); }
};
template< typename F >
auto fix( const F & f ) { return fix_struct< F > { f }; }
我们现在试试看执行fib函数:
int main()
{
  std::cout << fix(
    [](const auto & self, size_t i) -> size_t {
      return i < 2 ? i : self( i - 1 ) + self( i - 2 ); } )
    ( 9 );
}
34
很好,我们试着开高点,比如50
int main()
{
  std::cout << fix(
    [](const auto & self, size_t i) -> size_t {
      return i < 2 ? i : self( i - 1 ) + self( i - 2 ); } )
    ( 50 );
}
如果机器是32位的,自己改成boost::multiprecision之类的东西
这次,代码执行得很慢,什么地方在吃计算呢?我们试试看输出整个call trace:
int main()
{
  std::cout << fix(
    [](const auto & self, size_t i) -> size_t {
      auto ret = i < 2 ? i : self( i - 1 ) + self( i - 2 );
      std::cout << i << ":" << ret << std::endl;
      return ret; } )
    ( 50 );
}

这里是截取的一段输出:3:2
1:1
0:0
2:1
4:3
1:1
0:0
2:1
1:1
3:2
5:5
7:13
9:34
11:89
13:233
15:610
17:1597
看来问题是一个计算被多次求值:比如fib(4)会对fib(2),fib(3)求值,fib(3)又会再一次对fib(2)求值.
但是在修复这个问题之前,我们要先把调试代码改得漂亮点:今天调试我们就今天改三行代码,明天调试呢?这样不停改多麻烦?
template< typename F >
auto output_wrap( const F & f )
{
  return [=]( const auto & self, const auto & arg )
  {
    auto ret = f(self, arg);
    std::cout << arg << ":" << ret << std::endl;
    return ret;
  };
}
int main()
{
  std::cout << fix(output_wrap(
    [](const auto & self, size_t i) -> size_t {
      return i < 2 ? i : self( i - 1 ) + self( i - 2 ); }) )
    ( 50 );
}
好,回到正题,既然fib对同一参数进行多次计算,我们该如何处理?
最直接的办法就是建立一个缓存,如果函数已经被求值过,就直接用上一次的结果.
更巧妙的是,我们同样可以把缓存这一步抽象出来,独立于fib函数!
template< typename F, typename ARG, typename RET >
struct memorize_struct
{
  static_assert( ! std::is_reference< F >::value, "" );
  F f;
  mutable std::map< ARG, RET > cache;
  template< typename SELF > RET operator ( )
    ( const SELF & self, const ARG & arg ) const
  {
    auto it = cache.find( arg );
    if ( it == cache.end( ) ) {
      it = cache.insert( { arg, f( self, arg ) } ).first; }
    return it->second;
  }
};

template< typename ARG, typename RET, typename F >
auto memorize( const F & f ) { return
  memorize_struct<
    std::remove_reference_t< decltype( f ) >, ARG, RET >{
      f, { } }; }

int main()
{
  std::cout << fix(memorize< size_t, size_t >(
    [](const auto & self, size_t i) -> size_t {
      return i < 2 ? i : self( i - 1 ) + self( i - 2 ); }) )
  ( 50 );
}
12586269025
魔理沙使用了缓存,效果拔群!
int main()
{
  std::cout << fix(memorize< size_t, size_t >(
    output_wrap([](const auto & self, size_t i) -> size_t {
      return i < 2 ? i : self( i - 1 ) + self( i - 2 ); })) )
  ( 50 );
}
1:1
0:0
2:1
3:2
4:3
5:5
6:8
7:13
8:21
9:34
10:55
11:89
12:144
13:233
14:377
15:610
16:987
17:1597
18:2584
19:4181
20:6765
21:10946
22:17711
23:28657
24:46368
25:75025
26:121393
27:196418
28:317811
29:514229
30:832040
31:1346269
32:2178309
33:3524578
34:5702887
35:9227465
36:14930352
37:24157817
38:39088169
39:63245986
40:102334155
41:165580141
42:267914296
43:433494437
44:701408733
45:1134903170
46:1836311903
47:2971215073
48:4807526976
49:7778742049
50:12586269025
12586269025
二连击!至此,我们就成功的完成了http://www.lfcs.inf.ed.ac.uk/rep ... ECS-LFCS-97-375.pdf 的3.2以及以前的内容.
那末接下来呢?接着照着写下去?在此之前我们要重构一下:论文里面有个地方没有写到最好,找到了吗?
val wrap = fn f => fn f’ => fn p =>
  let
    val result = f f’ p
  in
    print (Int.toString result); print "\n"; result
  end ;
这里的wrap,接下来的memoise都需要输入两个f:一个是原函数,一个是fixpoint.
这样做写得更麻烦不说,还导致了wrap无法直接用于一般的函数上.
作为一个C++er,我要优雅,不要污,这样的东西果断要重构掉DAZE~
#define FUNCTION_WRAPPER_OP( RET, TYPE, NAME, CODE ) \
  template< typename TYPE > RET operator ( ) \
    ( TYPE && NAME ) const { CODE } \
  template< typename TYPE > RET operator ( ) \
    ( TYPE && NAME ) { CODE }

template< typename Wrapper, typename F >
struct fix_struct
{
  struct bind
  {
    static_assert( ! std::is_reference< F >::value, "" );
    F f;
    fix_struct & ref;
    FUNCTION_WRAPPER_OP( auto, T, t,
      return f( ref, std::forward< T >( t ) ); )
  };
  decltype( std::declval< Wrapper >( )(
    std::declval< bind >( ) ) ) fun;
  FUNCTION_WRAPPER_OP( auto, T, t,
    return fun( std::forward< T >( t ) ); )
  fix_struct( const Wrapper & w, const F & f ) :
    fun( w( bind { f, * this } ) ) { }
};

auto id = []( const auto & x ){ return x; };
template< typename W, typename F >
auto wrap( const W & w, const F & f ) {
  return fix_struct< W, F > ( w, f ); }

template< typename F >
auto fix( const F & f ) { return wrap( id, f ); }

template< typename F, typename ARG, typename RET >
struct memorize_struct
{
  static_assert( ! std::is_reference< F >::value, "" );
  F f;
  mutable std::map< ARG, RET > cache;
  FUNCTION_WRAPPER_OP(
    RET,
    T,
    arg,
    return ([&](){
      auto it = cache.find( arg );
      if ( it == cache.end( ) ) {
        it = cache.insert( { arg, f( arg ) } ).first; }
      return it->second; } )( ); )
};
template< typename ARG, typename RET >
  auto memorize( ) { return []( const auto & f ) {
    return memorize_struct< std::remove_reference_t<
      decltype( f ) >, ARG, RET >
      { f, { } }; }; }
auto output_wrap = []( const auto & f ){
  return [=]( const auto & arg )
  {
    auto ret = f( arg );
    std::cout << arg << ":" << ret << std::endl;
    return ret;
  }; };
还没完,如果我们wrap的函数是heterogenous的话该怎么办?当类型不单一的时候,就要擦除类型.
template< typename F >
struct hmemorize_struct
{
  static_assert( ! std::is_reference< F >::value, "" );
  F f;
  mutable std::map< std::type_index,
    std::function< boost::any( boost::any ) > > type_dispatch;
  FUNCTION_WRAPPER_OP(
    auto,
    T,
    arg,
    return ([&](){
      typedef decltype( f( arg ) ) RET;
      auto it = type_dispatch.find( typeid( arg ) );
      if ( it == type_dispatch.end( ) ){
        it = type_dispatch.insert({
          typeid( arg ),
          [](const auto & f){return
            [=]( const boost::any & a ) -> boost::any {
              return f( boost::any_cast< T >( a ) ); }; }
          ( memorize< T, RET >( )( f ) ) } ).first;}
      return boost::any_cast< RET >(
        it->second( arg ) ); } )( ); )
    };
auto hmemorize = []( const auto & f ){
  return hmemorize_struct< std::remove_reference_t<
    decltype( f ) > > { f, { } }; };
我们现在就可以测试一下代码
auto compose = []( const auto & l, const auto & r ) {
  return [=]( const auto & f ){ return l( r( f ) ); }; };
wrap( compose( hmemorize, output_wrap ), fib )( 50 );
既然我们的memorize可以对一般函数使用,我们就验证一下确实如此吧struct unit { };
BOOST_AUTO_TEST_CASE(memorize_test)
{
  size_t i = 0;
  auto acc = [&]( size_t ){ return ++i, unit{ }; };
  auto mt = memorize< size_t, unit >( )( acc );
  BOOST_CHECK_EQUAL( i, 0 );
  mt( 12 );
  BOOST_CHECK_EQUAL( i, 1 );
  mt( 12 );
  BOOST_CHECK_EQUAL( i, 1 );
  mt( 450 );
  BOOST_CHECK_EQUAL( i, 2 );
  mt( 12 );
  BOOST_CHECK_EQUAL( i, 2 );
  mt( 450 );
  BOOST_CHECK_EQUAL( i, 2 );
}
嗯,很优雅很放肆写到此,肯定有很多人不解:为何这么大费周章?lambda内写个循环就解决了.
因为本文的重点并不是fib,恰恰相反,本文的重点是,做一个萝莉控兔子厨是多没美妙的事情,不,如何对任何-则使是这样的一个微不足道的程序进行分析,调查出一般化的需求,并对之进行抽象,提高重用性!
更具体的说,我们这些代码,除了fib以外,并没有一个依赖与fib的定义.
如果我们要写递归的lambda expression,我们有fix,如果我们的函数出bug,我们可以用output_wrap,如果我们要尽快的写出一个动态规划程序,我们可以
std::cout << wrap(
  hmemorize,
  [](const auto & self,
    const std::pair< size_t, size_t > p)->size_t{
    return
      ( p.first == 0 && p.second == 0 ) ? 1 : 0 +
      ( p.first > 0 ?
        self( std::make_pair( p.first - 1, p.second ) ) : 0 ) +
      ( p.second > 0 ?
        self( std::make_pair( p.first, p.second - 1 ) ) : 0 ); } )
  ( std::make_pair( 20, 20 ) );
这里埋下了一个伏笔,相信大家都发现了,下次再重构.本文代码:FunctionalCpp/combinator.hpp at master · lolisa/FunctionalCpp · GitHub

评分

参与人数 1威望 +5 贡献 +5 收起 理由
岩川黑鬼 + 5 + 5 不要Y, 要XX

查看全部评分

Yare Yare Daze
回复

使用道具 举报

10

主题

108

帖子

465

积分

超级版主

RA2DIY 特别行政区行政长官

Rank: 8Rank: 8

威望
4
经验
346
贡献
3
发表于 2015-12-20 16:21:33 | 显示全部楼层
斐波那契数列不是矩阵自乘就完事了么。
We will prevail!! www.lhmouse.com
回复 支持 反对

使用道具 举报

8

主题

64

帖子

269

积分

超级版主

Rank: 8Rank: 8

威望
12
经验
169
贡献
12
发表于 2015-12-20 16:32:32 | 显示全部楼层
同吱,再来个快速幂(完全无视加粗
回复 支持 反对

使用道具 举报

10

主题

108

帖子

465

积分

超级版主

RA2DIY 特别行政区行政长官

Rank: 8Rank: 8

威望
4
经验
346
贡献
3
发表于 2015-12-20 17:33:24 | 显示全部楼层
nadesico19 发表于 2015-12-20 16:32
同吱,再来个快速幂(完全无视加粗

话说当年ヲ学算法课就记住这么一个东西。
We will prevail!! www.lhmouse.com
回复 支持 反对

使用道具 举报

9

主题

25

帖子

137

积分

注册会员

魔理魔理魔~

Rank: 2

威望
5
经验
97
贡献
5
 楼主| 发表于 2015-12-20 18:20:47 | 显示全部楼层
LH_Mouse 发表于 2015-12-20 00:21
斐波那契数列不是矩阵自乘就完事了么。

看粗体啊
Yare Yare Daze
回复 支持 反对

使用道具 举报

10

主题

108

帖子

465

积分

超级版主

RA2DIY 特别行政区行政长官

Rank: 8Rank: 8

威望
4
经验
346
贡献
3
发表于 2015-12-20 18:28:24 | 显示全部楼层

嘛,如果那个是重点那就无所谓了(当然我只以为重点是“兔子”)。
We will prevail!! www.lhmouse.com
回复 支持 反对

使用道具 举报

1

主题

16

帖子

142

积分

注册会员

Rank: 2

威望
0
经验
126
贡献
0
发表于 2015-12-20 18:42:51 | 显示全部楼层
GET失败,谁来fix一下我
回复 支持 反对

使用道具 举报

1

主题

21

帖子

80

积分

注册会员

Rank: 2

威望
0
经验
59
贡献
0
发表于 2015-12-20 21:59:17 | 显示全部楼层
来学习思想。。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|ISO/IEC C++ China Unofficial    

GMT+8, 2017-8-19 07:45 , Processed in 0.060049 second(s), 29 queries , Xcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表