加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

依赖链问题的解决方案

发布时间:2020-12-14 02:10:40 所属栏目:百科 来源:网络整理
导读:几个月前,看到这样一道题:有若干个任务,都是以数字来表示任务ID,任务之间有依赖关系,比如:1 - 2,表示任务2依赖于任务1,即,必须先完成任务1,才能完成任务2.那么现在给定多个这样的任务依赖关系,请设计并实现算法,其输出是一个任务序列,使得所有

几个月前,看到这样一道题:有若干个任务,都是以数字来表示任务ID,任务之间有依赖关系,比如:1 <- 2,表示任务2依赖于任务1,即,必须先完成任务1,才能完成任务2.那么现在给定多个这样的任务依赖关系,请设计并实现算法,其输出是一个任务序列,使得所有任务都可以被依次完成(即满足所有依赖关系)。

而几个月后的前不久,工作中又遇到这样一个问题,有若干个library,互相之间有依赖关系,请设计并实现一个算法,以输出一个library的序列,使得它们可以被按此序列顺利加载。

所以你看,其实这2个问题是同一个问题。那么怎么做呢?其实并不难,但其中有一个很关键的点。只要想透了这个点,一切就迎刃而解了。这个点,一句话说破了也很简单,如果不说破,可能也会困扰不少人。一句话,每一次都找出所有的无依赖任务。这就很容易理解了:

维护若干个依赖链,第一次,先找出所有的无依赖任务,然后将这些任务从依赖链中删除并添加到结果列表;

然后再找出所有的无依赖任务,再将它们从依赖链中删除并添加到结果列表;

如此循环往复,直到以下2种情况的任意一种发生为止:

1. 正常情况:所有的依赖链为空,即所有任务都被移到了结果列表;

2. 异常情况:仍有若干条依赖链不为空,但已经找不出无依赖任务了。这是为什么呢?聪明的读者想一想吧,不解释了。

最后,实现代码如下(115行的C++代码搞定,其实还能更短一点):

#include <vector>
#include <set>
#include <iostream>
using namespace std;

// The original dependency sequences.
const vector<vector<int>> dependencyVec = {
  {1,2 },{3,4,5},{2,6},3 }  
};

// A copy of dependencyVec,but it will be changed during calculation
vector<vector<int>> calcVec = dependencyVec;

// This function is just print the dependency sequencies in run time for debug purpose.
void printCalcVec()
{
  cout << "caclVec is as below: " << endl;
  for (auto vec : calcVec) {
    for (int i : vec) {
      cout << i << ",";
    }
    cout << endl;
  }
  cout << "----------------" << endl;
}

set<int> collectNoDependencyItems()
{
  set<int> noDependItems = {};

  // Store the headers of each dependency sequence.
  set<int> headers = {};
  for (auto vec : calcVec) {
    if (vec.size() > 0) headers.insert(vec[0]);
  }

  for (int h : headers) {
    bool noDepend = true;
    for (auto vec : calcVec) {
      for (unsigned int count = 1; count < vec.size(); ++count) {
        if (h == vec[count]) {
          noDepend = false;
          break;
        }
      }
      if (!noDepend) break;
    }

    if (noDepend) noDependItems.insert(h);
  }

  cout << "No Dependencies: ";
  for (int t : noDependItems) {
    cout << t << ",";
  }
  cout << endl << "----------------" << endl;

  return noDependItems;
}

void generateOrderList()
{
  // This is the final order list.
  vector<int> finalList{};

  // Check if calcVec is empty. If yes,Done.
  while (calcVec.size() > 0) {
    printCalcVec();

    // Figure out no dependency items and push them to finalList
    set<int> noDependItems = collectNoDependencyItems();

    if (noDependItems.size() == 0) {
      cout << "NoDependItems = 0" << endl;
      // There is no item which is no dependent. This means there is loop dependency.
      break;
    }

    // Push no dependent items to finalList
    for (unsigned int i : noDependItems) {
      finalList.push_back(i);
    }

    // Remove the headers of each dependency sequence which are no dependent items
    for (int i = 0; i < calcVec.size(); ) {
      if (noDependItems.find(calcVec[i][0]) != noDependItems.end()) {
        calcVec[i].erase(calcVec[i].begin());
      }
      if (calcVec[i].size() == 0) {
        calcVec.erase(calcVec.begin() + i);
      }
      else {
        ++i;
      }
    }
  }

  cout << "FinalList: ";
  for (int i : finalList) {
    cout << i << ",";
  }
  cout << endl;
}


int main()
{
  generateOrderList();
  return 0;
}


而运行结果如下:

caclVec is as below:
1,2,3,5,6,----------------
No Dependencies: 1,----------------
caclVec is as below:
2,----------------
No Dependencies: 2,----------------
caclVec is as below:
3,----------------
No Dependencies: 3,----------------
caclVec is as below:
4,----------------
No Dependencies: 4,----------------
caclVec is as below:
5,----------------
No Dependencies: 5,----------------
FinalList: 1,Press any key to continue . . .

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读