📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4564| 回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

Amazon : 设计一个并行运算的程序

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
是这样的,一共有K个排序链表需要归并。给你一个m核处理器的PC(m << k), 你设计一个小系统,能高效的实现归并操作。 说一下实现细节(没有标答,我只想出了一个windows下),大家open mind

上一篇:google : 计算二进制1的个数
下一篇:Microsoft : 字符串模糊匹配
🔗
Etrnls 2011-4-29 15:34:41 | 只看该作者
全局:
跟操作系统有神马关系……
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-1 22:51:17 | 只看该作者
全局:
我的想法是一开始知道有k个待排序链表,固定spawn m*2个线程。
所有的线程等待一个信号量, 每个线程在开始任务和结束任务时检查
是否有可以执行的任务,如果有就释放信号量,如果没有就设信号量为无信号状态。
其他的线程在执行完本任务后,如果信号量为无信号状态就卡在上面了。
每完成两个任务会产生一个新任务 : 比如合并1,2==>a, 3,4==>b, 新任务就是合并a,b
回复

使用道具 举报

🔗
bosshugoboss 2011-12-18 20:20:54 | 只看该作者
全局:
这个已经超越我的范围了~~ 不过以后想进AMAZON- -
还得努力啊! 谢谢LZ分享
回复

使用道具 举报

🔗
v85216192 2012-1-14 06:33:02 | 只看该作者
全局:
用线程的想法很好!
是不是分配m个线程比较好,这样可以保证每个线程一直占有一个CPU,避免线程的切换的开销,虽然线程的切换开销比进程小很多...
每个线程合并两个链表,然后把产生的新链表放到等待合并的队列中,同时给每一个正在被合并的队列加上锁
求教wwwyhx为什么要sprawn m*2个线程?
回复

使用道具 举报

🔗
erhuaming 2012-1-15 09:38:10 | 只看该作者
全局:
用的Java里的Executor.

  1. import java.util.concurrent.ExecutorService;
  2. import java.util.concurrent.Executors;
  3. import java.util.concurrent.Callable;
  4. import java.util.List;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.concurrent.atomic.AtomicInteger;

  8. public class MergeList<T extends Comparable> {
  9.         private List<List<T>> list;
  10.         private AtomicInteger round = new AtomicInteger(0);
  11.         private final int totalRounds;

  12.         public MergeList(List<List<T>> list) {
  13.                 this.list = list;
  14.                 totalRounds = list.size() - 1;
  15.         }

  16.         public List<T> merge() {
  17.                 int cores = Runtime.getRuntime().availableProcessors();
  18.                 System.out.println("Number of cores:" + cores);

  19.                 ExecutorService pool = Executors.newFixedThreadPool(cores);
  20.                 while(round.get() < totalRounds) {
  21.                         Object[] next = getNextTwoList();
  22.                         if (next == null) {
  23.                                 break;
  24.                         }
  25.                         Callable<List<T>> callable = new MergeTask((List<T>)next[0], (List<T>)next[1]);
  26.                         pool.submit(callable);
  27.                 }
  28.                 return list.get(0);
  29.         }

  30.         private synchronized void addToList(List<T> l) {
  31.                 list.add(l);
  32.                 round.getAndAdd(1);
  33.                 this.notifyAll();
  34.         }

  35.         private synchronized Object[] getNextTwoList() {
  36.                 if (round.get() == totalRounds){
  37.                         return null;
  38.                 }
  39.                
  40.                 while(list.size() < 2 && round.get() < totalRounds) {
  41.                         try{
  42.                                 this.wait();
  43.                         } catch (InterruptedException e) {
  44.                                 e.printStackTrace();               
  45.                         }
  46.                 }
  47.                 if (list.size() >= 2) {
  48.                         return new Object[]{list.remove(0), list.remove(0)};
  49.                 } else {
  50.                         return getNextTwoList();
  51.                 }
  52.         }

  53.         private class MergeTask implements Callable{
  54.                 private List<T> listA;
  55.                 private List<T> listB;

  56.                 public MergeTask(List<T> a, List<T> b) {
  57.                         listA = a;
  58.                         listB = b;
  59.                 }

  60.                 public Void call() {
  61.                         List<T> result = new LinkedList<T>();
  62.                         Iterator<T> ia = listA.iterator();
  63.                         Iterator<T> ib = listB.iterator();
  64.                         T itemA = null;
  65.                         T itemB = null;
  66.                         while(ia.hasNext() && ib.hasNext()) {
  67.                                 if (itemA == null) {
  68.                                         itemA = ia.next();
  69.                                 }

  70.                                 if (itemB == null) {
  71.                                         itemB = ib.next();
  72.                                 }

  73.                                 if (itemA.compareTo(itemB) < 0) {
  74.                                         result.add(itemA);
  75.                                         itemA = null;
  76.                                 } else {
  77.                                         result.add(itemB);
  78.                                         itemB = null;
  79.                                 }
  80.                         }

  81.                         T left = itemA == null ? itemB : itemA;
  82.                         Iterator<T> iterator = ia.hasNext()? ia : ib;

  83.                         T item = null;
  84.                         while(iterator.hasNext()) {
  85.                                 if (left == null) {
  86.                                         result.add(iterator.next());
  87.                                 } else {
  88.                                         item = iterator.next();
  89.                                         if (left.compareTo(item) < 0) {
  90.                                                 result.add(left);
  91.                                                 result.add(item);
  92.                                                 left = null;
  93.                                         } else {
  94.                                                 result.add(item);
  95.                                         }
  96.                                 }
  97.                         }
  98.                         addToList(result);
  99.                         return null;
  100.                 }
  101.         }
  102. }
复制代码
回复

使用道具 举报

🔗
ziegfeld 2012-1-15 11:26:14 | 只看该作者
全局:
这贴又上来了。。地里牛人多啊
并行计算完全不懂,不知道该不该花时间好好学学。。
回复

使用道具 举报

🔗
mwd 2012-3-4 15:29:59 | 只看该作者
全局:
回复 5# v85216192

一般来说,TLP中,每个core上的线程负载可以稍微重一点,一般来说一个核上2个线程的配置会使得计算资源的利用率较高。只有1个线程,处理核心并不会达到最优的计算资源利用率。但是如果负载太重了,过多的计算资源也会被浪费在线程切换上。

另,这种链表之间数据相关性不强的问题,可以考虑使用异步的方式来做,尽量避免或减少信号量、锁之类的的同步操作的使用。
回复

使用道具 举报

🔗
mwd 2012-3-4 15:45:00 | 只看该作者
全局:
本帖最后由 mwd 于 2012-3-4 15:46 编辑

回复 7# ziegfeld

唉,读研的时候一直在搞并行、architecture方面的东西,觉得挺没意思的。

现在的感觉是,如果就想做个合格的码农,就主攻上层吧,OO啦,design pattern啦,把这些东西弄好还挺实用的。

另,算法神马的,找工作面试的时候最重要。至于工作之后,我觉得基本用不上了。一是,现成的算法库多了去了;二是,让偶们自己写一个排序算法,公司还怕代码不够scalable,不够规范啊之类的。
回复

使用道具 举报

🔗
dhshao 2012-3-6 03:08:21 | 只看该作者
全局:
我的想法是用queue来实现任务的分配.
每个core运行一个thread.
每个thread:
{
    pickup two lists from queue;
    merge them;
    put the result list into queue;
}

如果考虑load balance, 可以用priority queue.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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