推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

A solution to 2 sigma OA problem

[复制链接] |试试Instant~ |关注本帖
andrewmasj 发表于 2016-6-18 06:25:46 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@2 sigma - 网上海投 - 其他 |Other其他

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

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

x
This is my solution to a problem posted in http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

apologize in advance if you disagree that I should open a new post. I want to know some feedbacks too and this way is easier to find out. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鍥磋鎴戜滑@1point 3 acres
So assuming you already passed in all the paremeters, here  is a solution. it assume all clusters are new and empty. The question does not provide how many machihes are already there so this assumption is valid.

static int[] distributeMachineToClusters(int b,int n,int[] a){
//define distribution array and initialize it with 1 distribution, which is minimum num of distr
//also maximum of load               
                int[] distributions = new int[n];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                for(int i=0;i<n;i++){//O(n)
                        distributions = 1;//at least one distribution
                }
                b-=n;//used n already. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                while(b>0){//O(bxn)
                        int j = -1;
                        int leastMax=Integer.MIN_VALUE;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        for(int i=0;i<n;i++){
                                //distribute to each of cluster, pick the one that drops load the least
                                if(a/(distributions+1)>leastMax){
                                        leastMax = a/(distributions+1);
                                        j=i;
                                }
                        }
                        b--;
                        distributions[j]++;
                }
                return distributions;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
       

ruiqin 发表于 2016-6-18 06:39:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这个和用max heap做的思路一样的把   都是找load最高的cluster  加一个machine进去
heap的bigO还要快一点    但是要写个class包含clusterid, load, machineNum之类的
不知道heap和楼主这样暴力做哪个实际run起来会快一点    就怕会超时
回复 支持 反对

使用道具 举报

 楼主| andrewmasj 发表于 2016-6-18 08:22:11 | 显示全部楼层
关注一亩三分地微博:
Warald
first to make it work, then to make it tuned. most important thing is to understand it.

here's heap solution.
. 1point 3acres 璁哄潧
        static int[] distributeMachineToClustersPQ(int b,int n,int[] a){. more info on 1point3acres.com
                class Entry<K,V,N> {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        K cluster;-google 1point3acres
                        V avgLoad;
                        N numMachine;
                        public Entry(K k,V v,N c){
                                cluster=k;
                                avgLoad = v;
                                numMachine = c;
                        }
                }
                //now instead of thinking dropping load the least, thinking to mitigate the one having most average load                                int[] distributions = new int[n];
                PriorityQueue<Entry<Integer, Integer, Integer>> pq = new PriorityQueue<Entry<Integer,Integer, Integer>>(                       
                        new Comparator<Entry<Integer,Integer, Integer>>() {
                                        @Override. 1point3acres.com/bbs
                                        public int compare(Entry<Integer, Integer, Integer> o1,
                                                        Entry<Integer, Integer, Integer> o2) {. 鍥磋鎴戜滑@1point 3 acres
                                                return o2.avgLoad-o1.avgLoad;
                                        }
                        }
                        );. Waral 鍗氬鏈夋洿澶氭枃绔,

                        for(int i=0;i<n;i++){//O(n)
                                Entry<Integer,Integer,Integer> e = new Entry<Integer,Integer,Integer>(i,a[i],1);//maximum load per machine
                                pq.add(e); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                        b-=n;//used n already

                        while(b>0){//O(bxn)
                                Entry<Integer,Integer,Integer> e = pq.poll();
                                b--;
                                e.avgLoad=(e.avgLoad*e.numMachine)/(e.numMachine+1);
                                e.numMachine++;
                                pq.add(e);
                        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴//prepare result
                        int distributions[] = new int[n];
                        for(Entry<Integer,Integer,Integer> e:pq){
                                distributions[e.cluster] =e.numMachine;
                        }
                        return distributions;
        }
回复 支持 反对

使用道具 举报

 楼主| andrewmasj 发表于 2016-6-18 08:23:39 | 显示全部楼层
looking forward to better solutions ...
回复 支持 反对

使用道具 举报

TonyLic 发表于 2016-7-4 07:21:30 | 显示全部楼层
贴个C++的,思路和上面的一样,用max heap,始终给最大的average load的cluster加一个machine,更新其average load,再放入heap中
Time complexty: O(KlogN)
  1. class cluster
  2. {
  3. public:
  4.         cluster(int p1, int p2, int p3, int p4) : work_load(p1), avg_load(p2), index(p3), num_machine(p4) {}. 1point3acres.com/bbs
  5.         int work_load;
  6.         int avg_load;. visit 1point3acres.com for more.
  7.         int index;
  8.         int num_machine;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9. };

  10. struct mycmp
  11. {
  12.         bool operator()(cluster& c1, cluster& c2) { return c1.avg_load < c2.avg_load; }
  13. };
  14. vector<int> loadBalance(vector<int>& loads, int b)
  15. {
  16.         vector<int> res(loads.size());
  17.         if (b < loads.size()) return res;
  18.         priority_queue < cluster, vector < cluster >, mycmp> pq;
  19.         for (int i = 0; i < loads.size(); ++i)
  20.                 pq.emplace(loads[i], loads[i], i, 1);. From 1point 3acres bbs
  21.         b -= loads.size();. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.         while (b--). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.         {
  24.                 auto temp = pq.top();
  25.                 pq.pop();
  26.                 temp.num_machine++;
  27.                 temp.avg_load = temp.work_load / temp.num_machine;
  28.                 pq.push(temp);
  29.         }
  30.         while (!pq.empty())
  31.         {-google 1point3acres
  32.                 auto temp = pq.top();
  33.                 pq.pop();
  34.                 res[temp.index] = temp.num_machine;
  35.         }
  36.         return res;
  37. }

  38. int main()
  39. {. 鍥磋鎴戜滑@1point 3 acres
  40.         vector<int> loads = { 200, 450 };
  41.         auto res = loadBalance(loads, 7);
  42.         printVector(res);. from: 1point3acres.com/bbs
  43.         return 0;
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-26 01:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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