前幾天我在jobstreet看到有趣的東東

Squall_Chua

下面那個圖是我前幾天在jobstreet看到的東東



是不是覺得內容很有趣吧

我嘗試的algorithm在我的電腦上面計算我試過最快只需要115ms
有誰也來挑戰看看
順便來討論一下它的algorithm

faiko

这个问题有漏洞
跑在怎样的CPU? Clock Speed多少？Single core/Multi core?

chooikw

1sec = 1000ms
以我们现在的电脑技术，不可能算这种简单的东西也要1sec吧 除非interviewee想捣蛋，在前面加个cout<<" Please feed me 600watt power or go to www.manmandeng.com..\n"; Sleep(100000);

Squall_Chua

faiko:
那個是只在一般的consumer grade的電腦上面的運行速度啦
一個好的algorithm在任何電腦都能跑很快的
表那麼在意我給你們我測試出來的數目
重要是在algorithm

chooikw:
你試一下就知道需不需要1 sec了

你大概不知道找出200000以內所有的prime number其實還滿花時間的說
如果多加一個0的話,就是2百萬
那樣就要更久了

faiko

恩……就算是这样。multicore & single core CPU，不同的algo，效果也是不同。

首先，怎样去寻找prime number? 这个algo有很多research的。最简单的就是在odd number寻找（因为even number，除了2以外都不是prime）

如果用multicore，你可以用divide & conquer technique来search。200K里面，再细分给每个core来寻找并accumulate summation。

chooiwai...你有所不知了。Prime Number searching在comp science可以算是很重要的一个topic。cryptography里面的prime number大小影响了其安全性 而crypto algo的快慢，决定了其实用性。

科技小女孩

哦？这么这样的呢？不过，我现在学的algorithm是基本的
（老师常常没来）可是你可以解释他是怎样的？

Squall_Chua

就用sequential processing的啦
用parallel processing的根本就是在比cpu power
而不是algorithm的efficiency

Squall_Chua

你需要我們解釋甚麼?
解釋甚麼是algorithm?
還是要解釋甚麼是prime number?

科技小女孩

原帖由 Squall_Chua 于 28-2-2009 10:23 PM 发表 你需要我們解釋甚麼?解釋甚麼是algorithm?還是要解釋甚麼是prime number?

两个都是啊~可以吗？

faiko

Parallel Algorithm
如何写efficient algo也是一门学门

Squall_Chua

你好像很喜歡parallel processing的說

在這裡表談parallel processing
回歸到原始點的sequential algorithm比較好

Squall_Chua

algorithm簡單來說就是一個step by step的instruction來解決一個問題
wiki應該會解釋到比較清楚
http://en.wikipedia.org/wiki/Algorithm

至於prime number的話你中學時期應該有學過
就是除了1之外,只能夠給自己除于的數目
馬來文好像叫nombor perdana
華語好像是叫質數

faiko

已经讲了：
最简单的就是在odd number寻找（因为even number，除了2以外都不是prime）

在distribute processing element来加快运算。呵呵……这个就很简单。

其实，不论sequential怎样快，都不如parallel

Squall_Chua

你的腦裡好像只有distributed processing而已

我要談的是algorithm的efficiency
就拿你說的那個prime testing的方法來說
就算只是找odd number
如果要測試N是不是prime number的話也要大約N/2次的comparison(表太在意準確的數目)
所以這裡的complexity是O(N)
然後根據上面那個題目要你找出200,000裡所有的prime number的總和的話
裡面有大約N/2個odd number
所以整個algorithm的complexity大約是O(N^2)
然後在這個題目裡N是200,000
所以你可以想像N^2有多大了吧


醬子真的是太慢了
所以如果我說當你需要test N是不是prime number時
你只需要test到sqrt(N)就足夠了
那又會怎樣了呢?


P.S. 我把球丟給你們來回答啦
        大家來討論下

晨天

brute force out了。。。。。
一定要用divide－and－conquer 以上的algorithm

Squall_Chua
竟然玩 Big O。。。， 很头痛的。。

以前玩Sieve of A*****, 但还是不理想

[ 本帖最后由 晨天 于 28-2-2009 11:43 PM 编辑 ]

Squall_Chua

沒錯啦
雖然brute force可以嘗試
但是不一定都理想的


會計算Big O很重要的
馬上就可以看到algorithm的efficiency
以前開始培養的習慣來的


sieve of eratosthenes其實是滿快的
不過很麻煩+很吃memory
我是用number theory的方法來解決的

晨天

逻辑数学 的number theory和cryptography 都是被我 brute force破的
haiz.......... number theory真的要翻书了

／****xiuuuuuuu, 不要给逻辑数学版主看到*****／


ps： 建议此贴也在软件工程 开多一分， 那里的人流辆比较多

晨天

请问如何assign a specific job to a specific core。。。
我没玩过parallel processing

Squall_Chua

其實我也不是很會而已
只懂一點點
標準的馬國教育制度下的產品


我大學裡的那些中東來的學生
很多都很鬼厲害一下
尤其是數學
馬國的真的是輸9條街啊

Squall_Chua

parallel processing我也在學著
看faiko一直提的話
他應該是很厲害玩parallel processing的吧
得空跟他請教下