- 浏览: 76120 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
I've seen these two:
http://www.iteye.com/topic/711162?page=13
http://www.iteye.com/topic/713259
But I am not sure whether I missed something or the majority missed something. Though the chancee of later is slim, I am going to take the chance.
Say we have 100 numbers and we are break them into batches of size 3,
{1, 2, 3}, {4, 5, 6} .... {97, 98, 99}, {100}
now compute the sums,
6, 15, ..., 294, 100
There are 34 numbers. Now we should break this array again into batches of size 3, right? Why does nobody do this? I am scratching my hair!
So here is my code. First, let's create a simple version
package my.test.brainteaser.sum; public class SingleThreadCalculator { public long calc(long[] values, int start, int end) { if (values == null || values.length == 0) return 0; long sum = 0; for (int i=start; i<end; i++) sum += values[i]; return sum; } }
Here we are using long to avoid overflow (java won't raise a flag like fortran for overflow). The extra variables start and end for avoiding array copying later on. These are counterintuitive, we shall talk about them later on.
Now let's create a Runnable wrapper for this:
package my.test.brainteaser.sum; import java.util.concurrent.CountDownLatch; public class RunnableCalculator implements Runnable { private SingleThreadCalculator calc; private long[] values; private int start; private int end; private long result; private CountDownLatch doneSignal; public RunnableCalculator(SingleThreadCalculator calc, long[] values, int start, int end, CountDownLatch doneSignal) { this.calc = calc; this.values = values; // for fast performance, no copy this.start = start; this.end = end; this.doneSignal = doneSignal; } public void run() { System.out.println("Thread: " + Thread.currentThread() + " start=" + start + " end=" + end); result = calc.calc(values, start, end); this.doneSignal.countDown(); } public long getResult() { return result; } }
The countdown latcher is to wait for all jobs finishes.
Now the core code:
package my.test.brainteaser.sum; import java.util.ArrayList; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; public class MultiThreadedCalculator { private int numThreads = 0; // 0 means no threading private int partSize = 100; private SingleThreadCalculator singleThreadCalculator = new SingleThreadCalculator(); public long calc(long[] values) { if (numThreads == 0) return singleThreadCalculator.calc(values, 0, values.length); if (values == null || values.length == 0) return 0; // compute how many parts we can divide int len = values.length / partSize; if (values.length % partSize != 0) len++; long[] sums = new long[len]; // partial results CountDownLatch doneSignal = new CountDownLatch(len); ExecutorService executor = Executors.newFixedThreadPool(numThreads); List<RunnableCalculator> calcs = new ArrayList<RunnableCalculator>(len); for (int i=0; i<len; i++) { int end; if (i < len - 1) // not the last one end = (i+1) * partSize; else // last one { end = values.length; } RunnableCalculator rc = new RunnableCalculator(singleThreadCalculator, values, i*partSize, end, doneSignal); calcs.add(rc); executor.execute(rc); } try { doneSignal.await(); for (int i=0; i<len; i++) sums[i] = calcs.get(i).getResult(); if (sums.length <= partSize) return singleThreadCalculator.calc(sums, 0, sums.length); else return calc(sums); } catch (InterruptedException ie) { throw new RuntimeException("got interrupted", ie); } } public void setNumThreads(int numThreads) { if (numThreads < 0) this.numThreads = 0; this.numThreads = numThreads; } public void setPartSize(int partSize) { this.partSize = partSize; } }
Here we have two variables, one for number of threads, another is for the part size in each thread. They are different, and very important when we want to optimize the performance in the real world.
There is a try block, inside, there is a recursive call, this is where we apply the same logic to the intermediate results.
The test case is:
package my.test.brainteaser.sum; import junit.framework.TestCase; public class SummationTest extends TestCase { public void testMultithreading() { long[] a = new long[10000]; for (int i=0; i<a.length; i++) a[i] = i+1; MultiThreadedCalculator c = new MultiThreadedCalculator(); c.setNumThreads(4); c.setPartSize(100); long sum = c.calc(a); System.out.println("sum=" + sum); assertTrue(sum == 10001 * 5000); } public void testMore() { MultiThreadedCalculator c = new MultiThreadedCalculator(); int len = 100000; c.setNumThreads(7); c.setPartSize(321); long sum = c.calc(generateCase(len, true)); System.out.println("sum=" + sum); long res = 1L * len * (len + 1) / 2; System.out.println("res=" + res); assertTrue(sum == res); } public void testMore1() { MultiThreadedCalculator c = new MultiThreadedCalculator(); int len = 54321; c.setNumThreads(7); c.setPartSize(123); long sum = c.calc(generateCase(len, false)); System.out.println("sum=" + sum); long res = 1L * len * (len + 1) / 2; System.out.println("res=" + res); assertTrue(sum == res); } private long[] generateCase(int len, boolean inc) { long[] ret = new long[len]; if (inc) { for (int i=0; i<ret.length; i++) ret[i] = i+1; } else { for (int i=0; i<ret.length; i++) ret[i] = len - i; } return ret; } }
To go further beyond this puzzle, there are two practical concerns:
1. We should extract a general interface from SingleThreadCalculator and MultiThreadedCalculator to shield out the runtime environment(single threaded or multi threaded env) so that users can choose. There are quite a few runtime environments I've experienced, such as message based, parallel computing based, in addition to multi-threaded.
2. The calculator interface can be abstracted to a general computing job interface which will be passed into a computing runtime environment so that we could run different computings, such as sum, average, or others.
评论
print("better");
很不错的主意,赞呀.
1. 中国人的英语, 楼上别怀疑了
2. 代码看上去很舒服, 解释的也很清楚
3. 利用partSize 参数调优, 再赞.
同问,我想是楼主在练英语吧
继续问...估计是外企的.....nr
同问,我想是楼主在练英语吧
发表评论
-
Excel Addin
2014-02-23 02:07 0When utilizing custom excell a ... -
Interview questions
2011-07-23 03:38 0Core: private int a; --> in ... -
How to design a bowling scoreboard
2011-07-22 23:26 1296I just saw this post: http:// ... -
obj xml
2011-05-27 23:13 0def record_parent(child, par ... -
obj xml 1
2011-05-27 23:11 0def obj2xml(obj, objname=Non ... -
Tetris Swing implementation
2011-02-05 11:04 1550Recently, I've seen an interest ... -
JSE links
2007-07-13 08:09 1907Tutorials: http://javaboutique. ... -
TCP, NIO, concurrency
2007-05-15 21:57 30Raw servers http://cindy.sour ... -
Exceptions
2007-03-24 22:52 31In batch modes, sometimes, we d ... -
Java enums in JDK 1.4
2007-03-04 05:59 1752Constantly, we need to define e ...
相关推荐
:beach_with_umbrella: 看望我使用由Puppeteer和Node-Fetch支持的CLI可以更轻松地访问您的网页安装 $ npm i -g visit-me用法 $ visit-me -u [YOUR_WEB_URL]其他选项争论别名描述数据类型默认值--count -c 造访次数...
For the latest information about Hadoop, please visit our website at: http://hadoop.apache.org/ and our wiki, at: http://wiki.apache.org/hadoop/ This distribution includes cryptographic software. ...
注意:visit.js只是一个实验,因为 ,但Firefox和最新的IE除外。 如果您厌倦了这些: // To get `name`, but you do not know whether `employees` and `employees[0]` exist or not const name = ( company . ...
VisIt是一个很好的可视化软件,功能强大,可免费使用。
结果:保留率很高,有21名参与者完成了为期12周的课程,17名参与者参加了至少12次课程中的10次。 12周后的平均体重(标准差)和减脂分别为8.2(4.6)千克和6.6(3.6)千克。 在第52周,体重和脂肪减少量分别维持在...
linux下从源代码安装32位的visit,里面有安装软件包和详细的安装文档~~
VisIt is an Open Source, interactive, scalable, visualization, animation and analysis tool. From Unix, Windows or Mac workstations, users can interactively visualize and analyze data ranging in scale ...
从大到小输出不小于x的结点元素(注意:其中用了visit函数作为函数的形参)
把XP的系统视图更换为VISIT视图 让界面更潮流
九年级英语全册 Unit 7 Where would you like to visit单元综合试题 人教新目标版
VisIt的openPMD插件 目录 推介会 该存储库包含可视化软件的openPMD插件的源。 该插件现在可以处理HDF5中的openPMD文件。 它既可以顺序运行,也可以并行运行。 该插件可以读取笛卡尔和轴对称几何体(在标准中称为...
cocos2dx中的CCScrollLayer类 CCScrollLayer::create(); srollLayer->setOriginPosition(pos); 修正内容: visit() -> CCLayer::visit() 修改成 CCLayer::draw();
支持XP和VISIT和WIN7的64位和32位分区软件AcronisDiskDirector10及注册机.是英文的,有使用教程。win7 分区成功,不丢失文件,亲自使用验证。
import { visit } from 'unist-util-visit' const tree = u ( 'tree' , [ u ( 'leaf' , '1' ) , u ( 'node' , [ u ( 'leaf' , '2' ) ] ) , u ( 'void' ) , u ( 'leaf' , '3' ) ] ) visit ( tree , 'leaf' , ( ...
:订阅他们的每周时事通讯和您感兴趣的任何其他主题 : 一个分享知识和更好地了解世界的地方 :社区策划的最佳学习路径知识图谱 :您可以咆哮和释放压力的社区 :一个指导社区,通过实时 1:1 帮助等方式向其他开发...
将此行添加到您的应用程序的Gemfile中: gem 'hightop' 选项 限制结果 Visit . top ( :referring_domain , 10 ) 包含零值 Visit . top ( :search_keyword , nil : true ) 与多个组一起使用 Visit . top ( [ :...
门诊医生工作站涉及到的数据表结构 1.医生工作站: (1).选取病人: 数据表:mz_zd_haoming(号名字典) mz_patient_mi(门诊病人主索引) ... 说明:取mz_visit_table中visit_flag='2'的病人。 (3).上线:
Lesson 12 A Visit to the Great Wall练习题及答案.doc
NEW_VISTA_WITH_SP2简体中文
visit是一个开源、交互式、可扩展、可视化、动画和分析工具。visit包含一组丰富的可视化功能,用户可以查看各种数据,包括在二维和三维结构化、自适应和非结构化网格上定义的标量和矢量字段。