有限制的调度算法 [英] Scheduling Algorithm with limitations
问题描述
由于user3125280，D.W.和叶夫根尼·Kluev问题被更新。
Thanks to user3125280, D.W. and Evgeny Kluev the question is updated.
我有网页的名单，我必须经常下载它们，每个网页有不同的下载频率。在此基础上的频率，我们组的网页中5组：
I have a list of webpages and I must download them frequently, each webpage got a different download frequency. Based on this frequency we group the webpages in 5 groups:
Items in group 1 are downloaded once per 1 hour
items in group 2 once per 2 hours
items in group 3 once per 4 hours
items in group 4 once per 12 hours
items in group 5 once per 24 hours
这意味着，我们必须下载所有组1的网页在1小时内，所有的组2在2个小时等。
This means, we must download all the group 1 webpages in 1 hour, all the group 2 in 2 hours etc.
我试图让一个算法。作为输入，我有：
I am trying to make an algorithm. As input, I have:
一） DATA_ARR =一个阵列中有5个号码。每个号码重新presents在这一组中的项目数。
a) DATA_ARR = one array with 5 numbers. Each number represents the number of items in this group.
B） TIME_ARR =一个阵列中有5个号码（1，2，4，12，24）重新presenting多久的项目将被下载。
b) TIME_ARR = one array with 5 numbers (1, 2, 4, 12, 24) representing how often the items will be downloaded.
B）如果我们有，15个项目在第5组和第3项第4组，这将是15/24 + 3/12 = 0.875，并四舍五入为1。
b) X = the total number of webpages to download per hour. This is calculated using items_in_group/download_frequently and rounded upwards. If we have 15 items in group 5, and 3 items in group 4, this will be 15/24 + 3/12 = 0.875 and rounded is 1.
每一个小时我的程序必须下载最多 X 网站。我希望算法的输出是这样的：
Every hour my program must download at max X sites. I expect the algorithm to output something like:
Hour 1: A1 B0 C4 D5
Hour 2: A2 B1 C2 D2
...
A1 =第2个第1组
项目
C0 =第3组的项目
A1 = 2nd item of 1st group
C0 = 1st item of 3rd group
我的算法必须尽可能地有效。这意味着：
My algorithm must be as efficient as possible. This means:
a）该模式必须是扩展以至少200多个小时
B）的无需创建一个可重复的模式
C）处所的需要如果可能的话，以使用绝对最小带宽
D）从来没有下载的项目往往比更新频率，没有例外
a) the pattern must be extendable to at least 200+ hours
b) no need to create a repeatable pattern
c) spaces are needed when possible in order to use the absolute minimum bandwidth
d) never ever download an item more often than the update frequency, no exceptions
示例：
group 1: 0 items | once per 1 hour
group 2: 3 items | once per 2 hours
group 3: 4 items | once per 4 hours
group 4: 0 items | once per 12 hours
group 5: 0 items | once per 24 hours
我们计算的项目，我们可以每小时走多少： 3/2 + 4/4 = 2.5。我们这一轮向上和它的3。
We calculate the number of items we can take per hour: 3/2+4/4 = 2.5. We round this upwards and it's 3.
使用铅笔和纸，我们可以发现以下解决方案：
Using pencil and paper, we can found the following solution:
Hour 1: B0 C0 B1
Hour 2: B2 C1 c2
Hour 3: B0 C3 B1
Hour 4: B2
Hour 5: B0 C0 B1
Hour 6: B2 C1 c2
Hour 7: B0 C3 B1
Hour 8: B2
Hour 9: B0 C0 B1
Hour 10: B2 C1 c2
Hour 11: B0 C3 B1
Hour 12: B2
Hour 13: B0 C0 B1
Hour 14: B2 C1 c2
and continue the above.
我们采取 C0 ， C1 C2 ，和 C3 每4小时一次。我们还采取 B0 ， B1 和 B2 连用2小时。
We take C0, C1 C2, and C3 once every 4 hours. We also take B0, B1 and B2 once every 2 hours.
问：请给我解释一下，如何设计一个算法能够下载项目，而使用下载的绝对最低数蛮力不会？溶液和算法必须效率的CPU明智的，因为元件的数量可以是巨大的。
Question: Please, explain to me, how to design an algorithm able to download the items, while using the absolute minimum number of downloads? Brute force is NOT a solution and the algorithm must be efficient CPU wise because the number of elements can be huge.
您可以读取答案张贴在这里： http://cs.stackexchange.com/a/19422/12497以及答案贴波纹管由user3125280
You may read the answer posted here: http://cs.stackexchange.com/a/19422/12497 as well as the answer posted bellow by user3125280.
推荐答案
您的问题是一个典型的调度问题。这些类型的问题进行很好的研究在计算机科学这样有一个巨大的文学阵列咨询。
You problem is a typical scheduling problem. These kinds of problems are well studied in computer science so there is a huge array of literature to consult.
在code是一种像赤字循环赛的，但有一些简化。首先，我们养活我们自己的队列通过向 data_to_process 变量。其次，队列只是遍历值列表
The code is kind of like Deficit round robin, but with a few simplifications. First, we feed the queues ourself by adding to the data_to_process variable. Secondly, the queues just iterate through a list of values.
一个区别是，这个解决方案会得到你想要的最佳值，除非数学错误。
One difference is that this solution will get the optimal value you want, barring mathematical error.
<打击>草图：没有编制（C ++ 11） UNIX基础，以SPEC code
Rough sketch: have not compiled (c++11) unix based, to spec code
#include <iostream>
#include <vector>
#include <numeric>
#include <unistd.h>
//#include <cmath> //for ceil
#define TIME_SCALE ((double)60.0) //1 for realtime speed
//Assuming you are not refreshing ints in the real case
template<typename T>
struct queue
{
const std::vector<T> data; //this will be filled with numbers
int position;
double refresh_rate; //must be refreshed ever ~ hours
double data_rate; //this many refreshes per hour
double credit; //amount of refreshes owed
queue(std::initializer_list<T> v, int r ) :
data(v), position(0), refresh_rate(r), credit(0) {
data_rate = data.size() / (double) refresh_rate;
}
int getNext() {
return data[position++ % data.size()];
}
};
double time_passed(){
static double total;
//if(total < 20){ //stop early
usleep(60000000 / TIME_SCALE); //sleep for a minute
total += 1.0 / 60.0; //add a minute
std::cout << "Time: " << total << std::endl;
return 1.0; //change to 1.0 / 60.0 for real time speed
//} else return 0;
}
int main()
{
//keep a list of the queues
std::vector<queue<int> > queues{
{{1, 2, 3}, 2},
{{1, 2, 3, 4}, 3}};
double total_data_rate = 0;
for(auto q : queues) total_data_rate += q.data_rate;
double data_to_process = 0; //how many refreshes we have to do
int queue_number = 0; //which queue we are processing
auto current_queue = &queues[0];
while(1) {
data_to_process += time_passed() * total_data_rate;
//data_to_process = ceil(data_to_process) //optional
while(data_to_process >= 1){
//data_to_process >= 0 will make the the scheduler more
//eager in the first time period (ie. everything will updated correctly
//in the first period and and following periods
if(current_queue->credit >= 1){
//don't change here though, since credit determines the weighting only,
//not how many refreshes are made
//refresh(current_queue.getNext();
std::cout << "From queue " << queue_number << " refreshed " <<
current_queue->getNext() << std::endl;
current_queue->credit -= 1;
data_to_process -= 1;
} else {
queue_number = (queue_number + 1) % queues.size();
current_queue = &queues[queue_number];
current_queue->credit += current_queue->data_rate;
}
}
}
return 0;
}
的例子现在应该编译在海湾合作委员会与--std = C + + 11，你想要什么给你。
The example should now compile on gcc with --std=c++11 and give you what you want.
这里是测试案例输出：（非时间标较早code）
and here is test case output: (for non-time scaled earlier code)
Time: 0
From queue 1 refreshed 1
From queue 0 refreshed 1
From queue 1 refreshed 2
Time: 1
From queue 0 refreshed 2
From queue 0 refreshed 3
From queue 1 refreshed 3
Time: 2
From queue 0 refreshed 1
From queue 1 refreshed 4
From queue 1 refreshed 1
Time: 3
From queue 0 refreshed 2
From queue 0 refreshed 3
From queue 1 refreshed 2
Time: 4
From queue 0 refreshed 1
From queue 1 refreshed 3
From queue 0 refreshed 2
Time: 5
From queue 0 refreshed 3
From queue 1 refreshed 4
From queue 1 refreshed 1
作为扩展，以允许该调度只完成了第一个LCM回答重复模式问题（update_rate * LCM（...刷新率...），CEIL（update_rate））步骤，然后重复模式
As an extension, to answer the repeating pattern problem by allowing this scheduler to complete only the first lcm(update_rate * lcm(...refresh rates...), ceil(update_rate)) steps, and then repeating the pattern.
另外：这，确实是无法解决的，有时因为小时边界的要求。当我用你无法解决的例子，并修改time_passed返回0.1，调度解决与更新每1.1小时（只是没有在小时边界！）。
ALSO: this will, indeed, be unsolvable sometimes because of the requirement on hour boundaries. When I use your unsolvable example, and modify time_passed to return 0.1, the schedule is solved with updates every 1.1 hours (just not at the hour boundaries!).
这篇关于有限制的调度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
