如需转载请留言。
题目如下:
- 有一个消息队列集群,集群里每台Broker的响应时间RT都不一样,但是每台Broker的极限服务QPS都是一样的,超过这个QPS会出现过载雪崩。而消息的生产者客户端,每次发送都会选择其中的一台broker来发送,一般来说发送逻辑是运行在一个线程池里面。假设cpu资源充足,通过实现一个负载均衡算法,使得生产者能够达到最大吞吐量,最优的平均响应时间,但是又不能把任何一台服务器压垮。已知每个broker的rt、极限qps,消息生产者的线程数量,请求总数,如果采用吞吐量最优的算法,求处理完所有请求需要的耗时,单位毫秒。
- 概念说明:
- QPS:query per second, 每秒请求量
- RT:response time,请求的响应时间
- Broker:消息队列的服务器
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int maxQps= Integer.valueOf(in.nextLine());
- final String[] rtList = in.nextLine().split(",");
- final int requestNum = Integer.valueOf(in.nextLine());
- final int threadNum = Integer.valueOf(in.nextLine());
- System.out.println(doneTime(maxQps, rtList, requestNum, threadNum));
- }
- /**
- * 如果使用最优的最大吞吐量负载均衡算法,按照最优模型多久能够处理完所有请求,单位毫秒。
- * @return
- */
- static long doneTime(int maxQps,String[] rtList,int requestNum,int threadNum) {
- //TODO
- return 0;
- }
- }
编译器版本: Java 1.8.0_66 请使用标准输入输出 (System.in,;已禁用图形、文件、网络、系统相关的操作,如 java.lang.Process , , Runtime.getRuntime;不要自定义包名称,否则会报错,即不要添加 package answer 之类的语句;您可以写很多个类,但是必须有一个类名为 Main,并且为 public 属性,并且 Main 为唯一的 public class,Main 类的里面必须包含一个名字为'main'的静态方法(函数),这个方法是程序的入口
时间限制: 30S (C/C++ 以外的语言为: 32 S) 内存限制: 200M (C/C++ 以外的语言为: 712 M)
输入: 输入数据包含 5 行数字: 第一行是每台 broker 的极限 QPS 第二行是 broker rt 列表, 用逗号分割,几个 rt 表示几个 broker 第三行是消息生产请求总数 第四行是最大并发线程数
输出: 按照最大吞吐量执行完所有请求,需要耗时多少毫秒
输入范例: 200 1,1,1,10,10 5000 10
输出范例: 5000
首先,我们要弄明白几个概念。第一个,什么叫最大吞吐量负载均衡算法。
详见:
而且,如题所需,我们建立在 "最优模型" 下求解。所以,我们忽略带宽,节点信息等的限制,进入理想情况。
接下来,我们需要解决的问题,就是在理想情况下,qps(query per second)和 threadNum(线程数量),rt(相应时间)之间的关系。
详见:
上面的资料链接里,那张吞吐量与 qps,threadNum 的关系,以及 qps=threadNum/rt,对本题都很关键。
那么答案已经显而易见了。我们也能理清题目中所有已知条件对最终结果的影响。那码代码就是分分钟的事。
- import java.util.Scanner;
- /**
- * @author Feng_zhulin
- * @since 17/3/20
- */
- public class Main {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int maxQps= Integer.valueOf(in.nextLine());
- final String[] rtList = in.nextLine().split(",");
- final int requestNum = Integer.valueOf(in.nextLine());
- final int threadNum = Integer.valueOf(in.nextLine());
- System.out.println(doneTime(maxQps, rtList, requestNum, threadNum));
- }
- /**
- * 如果使用最优的最大吞吐量负载均衡算法,按照最优模型多久能够处理完所有请求,单位毫秒。
- * @return
- */
- static long doneTime(int maxQps,String[] rtList,int requestNum,int threadNum) {
- //TODO
- int qpsSum = 0;
- for (String rtString : rtList) {
- int singleMaxQps = threadNum * 1000 / Integer.valueOf(rtString);
- if (singleMaxQps > maxQps) {
- qpsSum += maxQps;
- }else {
- qpsSum += singleMaxQps;
- }
- }
- return requestNum / qpsSum * 1000;
- }
- }
简单的写法,随手码的,求不喷。
最后验证一下:
- Feng_zhulindeMacBook-Pro:Desktop Feng_zhulin$ java Main
- 200
- 12,11,13,20,50
- 40000
- 8
- 41000
- Feng_zhulindeMacBook-Pro:Desktop Feng_zhulin$ java Main
- 200
- 1,1,1,10,10
- 5000
- 10
- 5000
来源: http://www.cnblogs.com/zhulin-jun/p/6597074.html