百度统计
一面之猿网
让这个世界,因为我,有一点点的不一样
纯序员给你介绍图化框架的简单实现——执行逻辑

友情提示:项目相关视频在B站持续更新中,内容略新于文章更新,欢迎观看交流和一键三连:


大家好,我是不会写代码的纯序员——Chunel。有人说,码如人生。人生中,有些事情是可以同时进行的,有些事情又必须是前后依次进行的;有些事情是可以刚开始就做的,有些事情又必须等待某个时机成熟了才可以开始。

我给大家举个例子:
人必须出生后,然后才能上学和工作。同样的,出生后还可以恋爱,然后结婚,和生娃。你可以上学的时候恋爱;也可以工作的时候再撩妹。但是,你必须先完成上学之后,才能开始工作。同样的,你必须恋爱后,才能结婚,然后再生娃(好吧,这个顺序,你想咋样我都支持你,哈哈)。最终,我们都会被辞退,我想大概是35岁左右吧。

image.png

看上面这个例子,和程序开发中常用的图化框架(比如TensorFlow)是不是很像。今天,纯序员给大家提供一种思路,可以轻松的实现一套属于自己的轻量级的图化框架。

分析

这个问题乍一看很难。但是我们来拆解一下,其实一共只有几步:

1,构建图框架,把node(图中的节点)和node的依赖信息注册到图中
2,对图进行分析,找出其中没有任何依赖的node,放入一个queue中
3,依次执行queue中的节点,直到queue中所有node被执行完毕
4,搜集依赖queue中node执行的节点(称为newNode)
5,清空queue,然后将newNode中所有未被运行且依赖的节点均被执行的节点,放入queue中
6,重复3、4、5步骤,直到queue中无node插入,则结束

举例

看着看着就晕了?没关系,看举个例子来,就比较容易理解了。

image.png

我们来看上图这个例子,然后对照上面的步骤,开始我们的流程。

  • 执行A的内容,直到全部结束
  • 执行B和C节点的内容,直到全部结束
  • 执行D和E的内容,直到全部结束
  • 执行F的内容,直到全部结束
  • 执行G的内容

所以说,最终的执行顺序,应该是 A->B->C->E->D->F->G。这样下来,是不是就是比较清楚了。

优化

你以为就这样就结束了?很多朋友应该已经看出来了,上图中B和C的执行顺序,应该是没有任何先后依赖的。所以,为了加速整体流程,B和C应该并发执行,而不是先执行B,结束后再执行C。

再继续看,D、E、F这三个节点。如果按照上面的说法,应该是D和E并发执行,都结束后再执行F。我们假设,D、E、F的流程的耗时,分别为 D=3s(秒),E=1s,F=2s 。那这个子流程结束,就需要max(3s,1s)+2s,也就是5s。但是F虽然依赖E,但是并不依赖D啊。

于是,优化点又来了,把E和F当做一个簇(cluster),簇内部依次执行。同时簇作为一个整体,与D并发执行。这样下来,这个子流程的最终耗时就应该是max(3s, 1s+2s),也就是3s。

当然了,还有很多优化思路我没有提到,或者我压根不知道的。也欢迎大家来一起讨论。

实现

懂了,但是不知道代码应该如何下手?至于代码实现,纯序员早已贴心的为你写了一套通用组件——CGraph。仅需要自己实现一下节点的功能函数,然后调用一个注册接口,并且设定依赖节点,就可以轻松的run起来上面提到的所有功能了。

就以上面画的那个图来举例吧,代码实现一共就这么几句话:

#include "/src/GraphCtrl/GraphInclude.h"

class MyNode1 : public GraphNode {
public:
    CSTATUS run () override {
        CSTATUS status = STATUS_OK;
        std::cout << "enter node1 run function. sleep for 1 second ... " << std::endl;
        this_thread::sleep_for(chrono::milliseconds(1000));
        return status;
    }
};
#include "/src/GraphCtrl/GraphInclude.h"

class MyNode2 : public GraphNode {
public:
    CSTATUS run () override {
        CSTATUS status = STATUS_OK;
        std::cout << "enter node1 run function. sleep for 2 second ... " << std::endl;
        this_thread::sleep_for(chrono::milliseconds(2000));
        return status;
    }
};
#include "MyGraphNode/MyNode1.h"
#include "MyGraphNode/MyNode2.h"

void graph_demo() {
    /* 创建图化 */
    Graphic* graphic = new Graphic();

    GraphNode* A = nullptr;
    GraphNode* B = nullptr;
    GraphNode* C = nullptr;
    GraphNode* D = nullptr;
    GraphNode* E = nullptr;
    GraphNode* F = nullptr;
    GraphNode* G = nullptr;

    /* 注册节点,其中MyNode1和MyNode2必须为GraphNode的子类 */
    graphic->registerGraphNode<MyNode1>(&A);               // A节点执行,没有任何依赖信息
    graphic->registerGraphNode<MyNode1>(&B, {A});          // B节点执行,依赖A节点执行完毕
    graphic->registerGraphNode<MyNode2>(&C, {A});
    graphic->registerGraphNode<MyNode1>(&D, {B});          // D节点执行,依赖B节点执行完毕
    graphic->registerGraphNode<MyNode2>(&E, {B});
    graphic->registerGraphNode<MyNode1>(&F, {E});
    graphic->registerGraphNode<MyNode1>(&G, {C, D, F});    // G节点执行,依赖C、E、F节点执行完毕

    /* 图信息初始化,准备开始计算 */
    graphic->init();

    /* 运行图计算。初始化后,支持多次循环计算 */
    graphic->run();

    /* 图信息逆初始化,准备结束计算 */
    graphic->deinit();
    delete graphic;
}

写在最后

这没有理由说看不懂了吧。当然了,CGraph自身也在不断的迭代和演进过程中,我们也会不断的借(co)鉴(py)行业中比较先进和成熟的一些实现方法。这个过程也需要大家大力的参与、鼓励和拍砖。

目前CGraph源码已经开源至github上,源码地址是:CGraph项目github链接,欢迎大家前来帮忙review,star and fork哦。如果能帮忙找到几个bug,或者做一些功能和性能上优化,那当然就更好了,哈哈哈哈!!!!!

    					[2021.05.09 by Chunel]

个人信息

微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站:www.chunel.cn
github地址: https://github.com/ChunelFeng