May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2132|回复: 18
收起左侧

集中讨论一下RoundRobin的问题

[复制链接] |试试Instant~ |关注本帖
wxr.dal 发表于 2015-11-21 10:08:48 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
开个帖子集中讨论一下Round Robin可能出现的follow up,corner case. 还有请video后的小伙伴过来说说,面试官都会问什么问题~谢谢啦
-google 1point3acres-google 1point3acres
补充内容 (2015-11-24 14:23):
补充一下吧,最近挖帖子,有同学提到过的follow up。怎么求最大最小wait time。

本帖被以下淘专辑推荐:

fagyjames 发表于 2015-11-21 10:17:21 | 显示全部楼层
关注一亩三分地微博:
Warald
我准备时候分析了container的选择,比如queue list vector stack array等等 他们之间的区别以及什么情况下RR可以考虑queue以外的 比如list。。。当时想的头都炸了。。。
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-21 10:17:54 | 显示全部楼层
fagyjames 发表于 2015-11-21 10:17. more info on 1point3acres.com
我准备时候分析了container的选择,比如queue list vector stack array等等 他们之间的区别以及什么情况下R ...

有道理有道理~
回复 支持 反对

使用道具 举报

fagyjames 发表于 2015-11-21 10:19:56 | 显示全部楼层

学姐加油!!!!~
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:12:18 | 显示全部楼层
这最小wait time 不就是0 吗第一个任务直接就执行了 还是说重新加到queue之后这个任务的等待时间还要加进去?
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:13:51 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:12.鐣欏璁哄潧-涓浜-涓夊垎鍦
这最小wait time 不就是0 吗第一个任务直接就执行了 还是说重新加到queue之后这个任务的等待时间还要加进去 ...

那第一个任务的run time要是大于q不就得等。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:17:31 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:13
那第一个任务的run time要是大于q不就得等。
. from: 1point3acres.com/bbs
我的意思是如果一个任务重新加到queue里面不算是新的任务 那如果这样的话大于q还得累计每个任务分别的总共等待时间就好了
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:21:02 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:17
我的意思是如果一个任务重新加到queue里面不算是新的任务 那如果这样的话大于q还得累计每个任务分别的总 ...

我觉得,是until finish, 中间所有的wait time都要加在一起。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:26:20 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:21
我觉得,是until finish, 中间所有的wait time都要加在一起。

那我觉得很简单啊 用一个list记录所有执行时间大于q的任务的等待时间 然后一个variable 记录所有执行时间小于q的最大和最小时间 然后跟list里面最大最小时间比较一下就可以了吧
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:30:06 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:26
那我觉得很简单啊 用一个list记录所有执行时间大于q的任务的等待时间 然后一个variable 记录所有执行时间 ...

小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:40:06 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:30
小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。

每次累加等待时间的时候和当前最小时间比较一下就好了啊
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:42:39 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:40
每次累加等待时间的时候和当前最小时间比较一下就好了啊
-google 1point3acres
"然后一个variable 记录所有执行时间小于q的最大和最小时间" 我没看懂,你这个是要怎么记录
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:42:40 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。

还有请问你能把看到这个问题的帖子链接发一下吗 谢啦
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:43:58 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:42
还有请问你能把看到这个问题的帖子链接发一下吗 谢啦
-google 1point3acres
这个要去翻帖子了,慢慢翻吧…… 我一时半会儿也找不到
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-11-28 03:59:36 | 显示全部楼层
对求最大最小时间没什么好的思路,求大神们指点!!
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-28 04:25:27 | 显示全部楼层
chuxidemeng 发表于 2015-11-28 03:59
对求最大最小时间没什么好的思路,求大神们指点!!

一个hash table 应该就解决了吧 用index记录process ID, value是积累的等待时间
回复 支持 反对

使用道具 举报

returning 发表于 2015-11-28 15:58:53 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:42
还有请问你能把看到这个问题的帖子链接发一下吗 谢啦

同问,云里雾里,看不懂啊。。。
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-4 14:27:30 | 显示全部楼层
http://www.1point3acres.com/bbs/thread-142143-1-1.html 我的C++解法.
  1. #include <iostream>
  2. #include <queue>. visit 1point3acres.com for more.
  3. using namespace std;
  4. .1point3acres缃
  5. float roundRobin(int* Atime, int len, int* Etime, int q) {
  6.         if (len < 2) return 0;
  7.         queue< pair<int, int> > qq;        // execution time, insert time.
  8.         int currenttime = 0, stackhead = 0, currenttask = 0, totalwaittime = 0;. more info on 1point3acres.com
  9.         bool killcurrenttask = 0;
  10.         while (qq.size() || stackhead != len || killcurrenttask) {
  11.                 while (stackhead < len && Atime[stackhead] <= currenttime) {
  12.                         qq.push(make_pair(Etime[stackhead], Atime[stackhead]));
  13.                         stackhead++;
  14.                 }
  15.                 if (killcurrenttask) {
  16.                         qq.push(make_pair(currenttask - q, currenttime));
  17.                 }
  18.                 if (!qq.size()) . from: 1point3acres.com/bbs
  19.                         currenttime = Atime[stackhead];
  20.                 else {
    . visit 1point3acres.com for more.
  21.                         currenttask = qq.front().first;
  22.                         totalwaittime += currenttime - qq.front().second;
  23.                         qq.pop();
  24.                         killcurrenttask = currenttask > q;
  25.                         currenttime += ((q < currenttask) ? q : currenttask);
  26.                 }-google 1point3acres
  27.         }
  28.        
  29.         return totalwaittime / (double)(len);
  30. }

  31. int main() { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.         // int Atime[] = { 0, 1, 3, 9 };
  33.         // int Etime[] = { 2, 1, 7, 5 };
  34.         // int q = 2;

  35.         // int Atime[] = { 0, 1, 4 };. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.         // int Etime[] = { 5, 2, 3 };. more info on 1point3acres.com
  37.         // int q = 3;

  38.         int Atime[] = { 0, 4, 8 };
  39.         int Etime[] = { 1, 1, 1 };
  40.         int q = 3;
  41. . 1point 3acres 璁哄潧
  42.         cout << roundRobin(Atime, sizeof(Atime) / sizeof(int), Etime, q);

  43.         // your code goes here. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.         return 0;
  45. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-28 10:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表