一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1483|回复: 18
收起左侧

集中讨论一下RoundRobin的问题

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
开个帖子集中讨论一下Round Robin可能出现的follow up,corner case. 还有请video后的小伙伴过来说说,面试官都会问什么问题~谢谢啦

补充内容 (2015-11-24 14:23):
补充一下吧,最近挖帖子,有同学提到过的follow up。怎么求最大最小wait time。

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-21 10:17:54 | 显示全部楼层
fagyjames 发表于 2015-11-21 10:17. from: 1point3acres.com/bbs
我准备时候分析了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不就得等。

我的意思是如果一个任务重新加到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. visit 1point3acres.com for more.
我觉得,是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
每次累加等待时间的时候和当前最小时间比较一下就好了啊

"然后一个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
还有请问你能把看到这个问题的帖子链接发一下吗 谢啦
.鏈枃鍘熷垱鑷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>
  3. using namespace std;. Waral 鍗氬鏈夋洿澶氭枃绔,

  4. float roundRobin(int* Atime, int len, int* Etime, int q) {
  5.         if (len < 2) return 0;
  6.         queue< pair<int, int> > qq;        // execution time, insert time.
  7.         int currenttime = 0, stackhead = 0, currenttask = 0, totalwaittime = 0;
  8.         bool killcurrenttask = 0;
  9.         while (qq.size() || stackhead != len || killcurrenttask) {. 1point 3acres 璁哄潧
  10.                 while (stackhead < len && Atime[stackhead] <= currenttime) {
  11.                         qq.push(make_pair(Etime[stackhead], Atime[stackhead]));
  12.                         stackhead++;
  13.                 }
  14.                 if (killcurrenttask) {
  15.                         qq.push(make_pair(currenttask - q, currenttime));. From 1point 3acres bbs
  16.                 }
  17.                 if (!qq.size())
  18.                         currenttime = Atime[stackhead];. visit 1point3acres.com for more.
  19.                 else {
  20.                         currenttask = qq.front().first;
  21.                         totalwaittime += currenttime - qq.front().second;
  22.                         qq.pop();. visit 1point3acres.com for more.
  23.                         killcurrenttask = currenttask > q;
  24.                         currenttime += ((q < currenttask) ? q : currenttask);
  25.                 }
  26.         }
  27.        
  28.         return totalwaittime / (double)(len);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29. }
  30. . visit 1point3acres.com for more.
  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 };
  37.         // int q = 3;

  38.         int Atime[] = { 0, 4, 8 };
  39.         int Etime[] = { 1, 1, 1 };
  40.         int q = 3;

  41.         cout << roundRobin(Atime, sizeof(Atime) / sizeof(int), Etime, q);.鏈枃鍘熷垱鑷1point3acres璁哄潧

  42.         // your code goes here
  43.         return 0;
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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