c++:ASAP和ALAP算法

xiaoxiao2021-02-28  13

一、ASAP和ALAP的概念

最近在看一些算法的论文,其中涉及了ASAP和ALAP算法,这两种算法由很多的应用背景,在此仅阐述对于图中节点执行顺序的选择。首先从字面上理解,ASAP是as soon as possible,是尽快执行的意思,即当图中节点没有依赖关系和资源限制的前提下就可以马上执行;相反的,ALAP是as late as possible的意思,即在图中关键路径执行结束前拖到最晚执行。从字面上理解有点笼统,下面我们可以通过一个例子来理解:

图a是DFG图,图中节点有两种,三角形和圆形分别代表不同的操作,如加操作、乘操作、加载操作、存储操作等,图中的边表示不同操作之间的依赖关系,图b是ASAP算法下的调度方式,在第0步时,0 1 3 4这四个节点没有父节点的限制,则尽快在第一步执行,当第0步执行完毕后,在图中去掉这四个节点,所以2 5 7这三个节点又没有了父节点的依赖限制,所以在第1步就执行2 5 7,依次类推,在第2步执行6,在第3步执行8。图c是ALAP算法,可以看出,0->2->6->8是这个图的关键路径,即最长的路径,所有节点要尽量靠后执行,节点是根据关键路径反向尽快执行,图中的7节点可以在第1步或者第2步执行则选择靠后的第2步,4节点可以选择在第0步和第1步执行,则选择靠后的第1步。

二、c++代码实现

1.输入

输入图文件如下所示,其中每一行的第一个数字表示一个节点,后面的所有数字表示为第一个数字的子节点,对于后面的所有数字来说,第一个数字使他们的父节点。每一行都是如此。例如第一行表示,节点0是父节点,8 23 26 28 31 37 39 46全部是0节点的子节点。

0 8 23 26 28 31 37 39 46 8 28 31 37 39 23 8 28 31 37 39 26 8 23 28 31 37 39 31 28 37 39 37 28 39 39 28 46 8 23 26 28 31 37 39 53 13

2.算法实现

#include<iostream> #include<fstream> #include<vector> #include <regex> #include<map> using namespace std; /*存储图节点*/ struct node { int name; vector<int> parent; vector<int> child; int priority = 0; }; void input(vector<vector<int>> &Vec_Dti, string FileName); void initData(map<int, node> &map, vector<vector<int>> inData); void ASAP(vector<vector<int>> &output_ASAP, map<int, node> m); void ALAP(vector<vector<int>> &output_ALAP, map<int, node> m); void delate(map<int, node> &m, vector<int> key ); void print(vector<vector<int>> output); void main() { vector<vector<int>> inData; string FileName = "E:/graph_copy.g"; input(inData, FileName); map<int, node> m; initData(m, inData); vector<vector<int>> output_ASAP; ASAP(output_ASAP, m); cout << "-----------ASAP-------------" << endl; print(output_ASAP); vector<vector<int>> output_ALAP; ALAP(output_ALAP, m); cout << "------------ALAP------------" << endl; print(output_ALAP); system("PAUSE"); } /*fuction:input 将文件中标示图的节点以二维组的形式存放在vector中*/ void input(vector<vector<int>> &Vec_Dti,string FileName) { vector<int> temp_line; string line; ifstream in(FileName); //读入文件 regex pat_regex("[[:digit:]]+"); //匹配原则,这里代表一个或多个数字 while (getline(in, line)) { //按行读取 for (sregex_iterator it(line.begin(), line.end(), pat_regex), end_it; it != end_it; ++it) { //表达式匹配,匹配一行中所有满足条件的字符 temp_line.push_back(stoi(it->str())); //将数据转化为int型并存入一维vector中 } Vec_Dti.push_back(temp_line); //保存所有数据 temp_line.clear(); } } /*fuction:initData 初始化node结构体,存储在map中,记录图的各个节点的依赖关系 所给的图文件,结构像一个邻接表,每一行的第一个数字代表节点名字,后面的所有节点都是第一个节点的子节点*/ void initData(map<int,node> &m,vector<vector<int>> inData) { for (int i = 0; i < inData.size(); i++) { node tmp; tmp.name = inData[i][0];//记录每一行第一节点的名字 for (int j=1; j < inData[i].size(); j++) { tmp.child.push_back(inData[i][j]);//将每一行第一个节点后的所有节点记录到该节点的孩子节点数组中 } m[tmp.name] = tmp; } //每行第一个节点都是后面所有节点的父节点,所以,将父节点的信息存储到每个节点的父节点数组中 for (int i = 0; i < inData.size(); i++) { for (int j = 1; j < inData[i].size(); j++) { m[inData[i][j]].name = inData[i][j]; m[inData[i][j]].parent.push_back(inData[i][0]); } } } /*fuction:print 计算结果存储在一个二维的vector中,将结果输出在终端上*/ void print(vector<vector<int>> output) { for (auto i : output) { for (auto j : i) { cout << j << " "; } cout << endl; } } /*fuction:ASAP 将图中所有没有父母节点先执行,并在图中删除这些已执行的节点,直到图中所有节点被删除*/ void ASAP(vector<vector<int>> &output_ASAP, map<int, node> m) { map<int, node>::iterator it; while (!m.empty()) {//当图中所有节点都被删除时结束 vector<int> tmp; it = m.begin(); while (it != m.end()) { if (it->second.parent.size() == 0) {//找到所有没有父节点的节点,将其存在一个tmp数组中 tmp.push_back(it->first); } it++; } output_ASAP.push_back(tmp); delate(m, tmp);//将tmp数组中的所有节点以及有关的依赖关系删除 } } /*fuction:ALAP ALAP的关键是要倒着用ASAP调度,然后反转结果即可,将图中所有没有孩子节点先执行,并在图中删除这些已执行的节点,直到图中所有节点被删除,最后反转结果顺序*/ void ALAP(vector<vector<int>> &output_ALAP, map<int, node> m) { map<int, node>::iterator it; while (!m.empty()) { vector<int> tmp; it = m.begin(); while (it != m.end()) { if (it->second.child.size() == 0) {//找到所有没有子节点的节点,将其存在一个tmp数组中 tmp.push_back(it->first); } it++; } output_ALAP.push_back(tmp); delate(m, tmp);//删除tmp } int n = output_ALAP.size() ; for (int i = 0; i < n/2; i++) {//将所得结果反转即是ALAP的结果 vector<int> tm; tm = output_ALAP[i]; output_ALAP[i] = output_ALAP[n - i - 1]; output_ALAP[n - i - 1] = tm; } } /*function:delate 删除图中的某些节点,即key中存储的节点,再删除节点时,要将图中所有有关这些节点的依赖关系删除,即以这些删除节点为父节点或孩子节点的依赖关系删除*/ void delate(map<int, node> &m, vector<int> key) { map<int, node>::iterator it; it = m.begin(); while (it != m.end()) {//删掉每个节点中有关的依赖关系,即在父节点数组和子节点数组中删掉key vector<int> parent = it->second.parent; vector<int> child = it->second.child; vector<int>::iterator itr; for (int t = 0; t < key.size(); t++) { for (itr = parent.begin(); itr != parent.end(); ) { if (*itr == key[t]) { itr = parent.erase(itr); } else { ++itr; } } for (itr = child.begin(); itr != child.end();) { if (*itr == key[t]) { itr = child.erase(itr); } else { ++itr; } } } it->second.parent = parent; it->second.child = child; it++; } //从map中删掉key for (int t = 0; t < key.size(); t++) { map<int, node>::iterator k = m.find(key[t]); if (k != m.end()) { m.erase(k); } } }

转载请注明原文地址: https://www.6miu.com/read-1400289.html

最新回复(0)