异步并发递归模型讨论


#1

异步消除递归的思想源于avboost.com论坛上一篇由博士microcai写的<<异步遍历文件夹>>而来。

考虑一个问题:

void hannoi_sync(int n, char A, char B, char C)  
{
    if (n == 1)
    {
        printf("Move disk %d from %c to %c\n", n, A, C);
    }
    else
    {
        hannoi_sync (n-1, A, C, B);
        printf("Move disk %d from %c to %c\n", n, A, C);
        hannoi_sync (n-1, B, A, C);
    }
}

这是一个很普通的汉诺塔算法,要如何做到并发执行呢?

几乎很难办,这问题在于:通常情况下,我们使用递归去计算某件事的时候,它的计算步骤总是依赖于上一次计算的完成,也就是无法做到并行计算。

博士microcai提出了异步遍历文件夹之后,最终在社区展开了讨论,总结出通过异步消除递归的思想,并且将很多常规串行计算可轻松运用到并发运算中。

根据那个思想,我们可以轻松的修改成异步可并发汉诺塔版本,代码如下:

// 下面是异步可并发汉诺塔算法.
void hannoi_async(boost::asio::io_service& io, int n, char A, char B, char C)  
{
    if (n == 1)
    {
        printf("thread id %d, Move disk %d from %c to %c\n", boost::this_thread::get_id(), n, A, C);
    }
    else
    {
        io.post(boost::bind(&hannoi_async, boost::ref(io), n-1, A, C, B));
        printf("thread id %d, Move disk %d from %c to %c\n", boost::this_thread::get_id(), n, A, C);
        io.post(boost::bind(&hannoi_async, boost::ref(io), n-1, B, A, C));
    }
}

异步消除递归的汉诺塔算法实现,这真是一件非常爽的事情。

我也由此可以得出一个结论:只要是能设计成递归的算法(比如一些循环),统统都可以通过asio来改成并发执行,也就是说,通常只能运行在一个核上的串行计算,使用这种方式,就可以轻松设计成并发的计算。

需要注意的是,执行结果的返回顺序可能与以往普通递归调用不一样,具体区别在于: 比如一颗树,有两个孩子(左右孩子),普通情况下,向下递归时,一般是是等待左子树递归后完全返回,再继续右子树的递归。

但是在异步并发递归里面,则是左右并行向下递归的,而其结果返回,却是树的从上到下层次关系排列,这是和普通递归需要区别的地方。

​–

参考链接:

[1] http://avboost.com/t/topic/250​


#2

非常不错, 将引发编程革命!


#3

返回结果会不会乱序?我觉得多线程的情况下,有可能子节点上的POST操作会比父节点上的POST操作先被执行。


#4

感觉应该所有的尾递归可以改成这样的 汉诺威这样的在执行顺序上还是有区别的


#5

父节点不执行, 如何会发出子节点的 post 操作?


#6

不是所有的递归都可以这样修改, 但是相当多的递归可以.


#7

printf(“thread id %d, Move disk %d from %c to %c\n”, boost::this_thread::get_id(), n, A, C); 我是说这种操作,而不是查找上的异步,有可能子节点先被打印出来


#8

结果打印输出顺序的保证可以通过标识来确定,继续以上为例:

1、n就是层次,无论先打印出来还是后打印出来,这是可确定的。

2、left/right同样可以通过添加参数来标识是第几个孩子,在这个示例里面,第一次post就是1(left),第二次post就是2(right)。


#9

从 server log 里看, iq50 老登录失败.


#10

iq50, 你第一次使用 “使用 google 帐号登录” 虽然会创建给帐号, 但是其实是没密码的, 而且也不会有密码的, 你不要用创建的帐号登录, 第二次你还是继续使用 “使用 google 帐号登录” .


#11

没听懂啊…我该在哪改?关键是我还可以回帖…


#12

异步+状态机,asio的异步回调确实能做到递归消除 TBB的并行算法和这个异步递归有何区别?


#13

本主题已全局置顶,它将始终显示在它所属分类的顶部。可以由版主解除置顶或者点击清除置顶按钮。


#14

#15

fibbnacci你怎么改呢?前后计算相依赖?