[題目]http://mp.weixin.qq.com/s/-cR07rHU91owk8nMOfhz9w
題目:任務(wù)調(diào)度在分布式調(diào)度系統(tǒng)中是一個很復(fù)雜很有挑戰(zhàn)的問題叠赐。這里我們考慮一個簡化的場景:假設(shè)一個中央調(diào)度機(jī),有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上去執(zhí)行赛不。由于每臺服務(wù)器的配置不一樣罢洲,因此服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。
例如:有2個執(zhí)行機(jī)a, b. 執(zhí)行一個任務(wù)分別需要7min耸峭,10min,有6個任務(wù)待調(diào)度抓艳。如果平分這6個任務(wù)帚戳,即a,b各分三個任務(wù)偏友,則最短需要30min執(zhí)行完所有对供。如果a分這4個任務(wù),b分2個鹅髓,則最短28min執(zhí)行完京景。
請設(shè)計調(diào)度算法,使得所有任務(wù)完成所需的時間最短
簡述思路
請用你熟悉的編程語言編碼實現(xiàn)以下方法醒串,輸入為m臺服務(wù)器鄙皇,每臺機(jī)器處理一個任務(wù)的時間為t[i],完成n個任務(wù)伴逸,輸出n個任務(wù)在m臺服務(wù)器的分布:
int estimate_process_time(int[] t, int m, int n);
思路:本題是個基本的題型,考慮到如何進(jìn)行調(diào)度的問題博烂,調(diào)度問題是個非常大的問題漱竖,本題簡化了模型馍惹,該某型考慮的是如何組織計算單元, 使得計算的總時間最小悼吱。
其實良狈,學(xué)習(xí)算法直到現(xiàn)在,我基本上完成了算法的前半部分(基礎(chǔ))遇西,就是如何去思考一個算法題,用什么行為去完成這個算法粱檀,我對后半部分漫玄,比如圖論算法,DNF算法渗常,數(shù)論算法等等汗盘,這些高級算法我還是沒有掌握,還有就是如何進(jìn)行算法分析尸执,這個內(nèi)容我也沒有掌握缓醋,很遺憾,我需要學(xué)習(xí)的東西還有很多褪贵。個人感覺計算機(jī)的知識是個很龐大的體系,要想全部掌握我想很困難脆丁,所以針對個人興趣动雹,研究某一領(lǐng)域的算法是一個不錯的選擇,但是歼培,基礎(chǔ)的算法還是要會的,畢竟萬變不離其宗躲庄。
此題,如果能想到使用小頂堆笋庄,基本上就算完成了算法了倔监。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct nt{
int n;
int t;
int i;
nt (int e1, int e2) : n(0), t(e1), i(e2) {}
};
class CCompNt
{
public:
bool operator() (nt e1, nt e2)
{
return (e2.n+1) * e2.t < (e1.n+1) * e1.t
|| ((e2.n+1) * e2.t == (e1.n+1) * e1.t && e2.t <= e1.t);
}
} CompNt;
class CCompNt2
{
public:
bool operator() (nt e1, nt e2)
{
return e1.i < e2.i;
}
} CompNt2;
void printNt(nt e)
{
cout << "(" << e.i << "," << e.t << "," << e.n << ") ";
}
vector<nt> estimate_process_time(const vector<int> & vect, int m, int n)
{
vector<nt> vecNt;
for (int i=0; i<m; ++i) {
vecNt.push_back(nt(vect[i], i));
}
make_heap(vecNt.begin(), vecNt.end(), CompNt);
for (int i=0; i<n; ++i) {
pop_heap(vecNt.begin(), vecNt.end(), CompNt);
auto nt1 = vecNt.back();
vecNt.pop_back();
nt1.n += 1;
vecNt.push_back(nt1);
push_heap(vecNt.begin(), vecNt.end(), CompNt);
}
sort(vecNt.begin(), vecNt.end(), CompNt);
return vecNt;
}
int main(int argc, char ** argv)
{
int n = 6;
int m = 2;
vector<int> t = {
7, 10
};
auto vecNt = estimate_process_time(t, m, n);
cout << "(index, t, n)" << endl;
for_each(vecNt.begin(), vecNt.end(), printNt);
return 0;
}
文章的最后丐枉,還是想吐槽一下,C語言提供的數(shù)據(jù)結(jié)構(gòu)真心的少籍嘹,C++這方面做的不錯弯院,但是C++這方面需要不斷的訓(xùn)練和學(xué)習(xí),比如颂碘,這里設(shè)計小頂堆的時候椅挣,我對于比較算法的設(shè)計就出現(xiàn)了問題,糾結(jié)了好長時間鼠证。另外,這只是一個校招題适掰,題目的難度你們可以從代碼中感受一下荠列,代碼真的不難,難得是如何去想费就、去解決類似這樣的問題4ǘ印?寻帷艳汽!核心算法就是函數(shù)estimate_process_time中的for循環(huán)河狐,如果你用C實現(xiàn)瑟捣,那么heap的實現(xiàn)應(yīng)該也算是核心代碼了,這樣增加了解題的難度捐祠!