友情提示:项目相关视频在B站持续更新中,内容略新于文章更新,欢迎观看交流和一键三连:
- 【B站视频】CGraph 入门篇
- 【B站视频】CGraph 功能篇
- 全面介绍CGraph项目中,所有的名词术语和功能模块
- 结合实际coding过程,详细介绍了每个功能的具体的使用场景、用法、以及解决的问题
- 适合想要全面了解功能和快速上手使用CGraph的童鞋
- 适合对多线程编程感兴趣的童鞋
- 【B站视频】CGraph 应用篇
- 【B站视频】CGraph 分享篇
- 【B站视频】CGraph 和 taskflow 性能对比实测
大家好,我是不会写代码的纯序员——Chunel。有人说,码如人生。人生中,有些事情是可以同时进行的,有些事情又必须是前后依次进行的;有些事情是可以刚开始就做的,有些事情又必须等待某个时机成熟了才可以开始。
我给大家举个例子:
人必须出生后,然后才能上学和工作。同样的,出生后还可以恋爱,然后结婚,和生娃。你可以上学的时候恋爱;也可以工作的时候再撩妹。但是,你必须先完成上学之后,才能开始工作。同样的,你必须恋爱后,才能结婚,然后再生娃(好吧,这个顺序,你想咋样我都支持你,哈哈)。最终,我们都会被辞退,我想大概是35岁左右吧。
看上面这个例子,和程序开发中常用的图化框架(比如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插入,则结束
举例 |
看着看着就晕了?没关系,看举个例子来,就比较容易理解了。
我们来看上图这个例子,然后对照上面的步骤,开始我们的流程。
- 执行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