[Haskell Practice] Mandelbrot set

老實說,原本以為會寫很一篇比較長的 blog post ,但是想想之後,做的都是簡單的事情,所以就簡單記錄一下。

測試的編譯指令是 ghc -O2 Mandelbrot.hs -rtsopts -threaded -fllvm

程式碼如下。基本上 Mandelbrot.hs 可以利用 ./Mandelbrot par 100 +RTS -N2 -s 產生資料,該 output data 的前半部是 x points,後半部是 y points。再利用 python plotMandelbrot.py 把圖畫出來。

在 2010 late MBP15 (Intel Core i5 2.4 Ghz, 8Gb) 上跑 ./Mandelbrot par 100 +RTS -N2 -s (2 threads) 約 25 secs 左右,單核心約 45 secs 左右,這速度是不快,不過暫時應該不會再改了,因為還有其他的資料想看 ... (熱帶魚 在 Chapter 6 也實作 Mandelbrot,使用 GPU 加速,只花了 10 secs,而且精細的多)。

最底下附上第一版程式,相較於最後一版其實做了不少修改如上。

  1. 一開始使用 Complex Double 做計算,後來改用 (Double,Double)
  2. 原生的 List 在 2 threads 以上的 GC 時間會特長 (沒有特地去找原因),改用 Data.Vector 實作。
  3. 一開始就產生全部的點去做運算耗費太多的時間,改傳點的平面範圍要算的時候再產生點。
  4. 善用 Bang patterns 限制一些參數為 strict
import Data.Complex
import Data.Binary.Put
import Data.Binary.IEEE754 (putFloat64le)
import qualified Data.ByteString.Lazy as BL

maxIteration :: Integer 
maxIteration = 3000 

pointSize :: Integer
pointSize = 2000 

isMandelPoint :: Complex Double -> Bool
isMandelPoint p = q maxIteration p
    where q :: Integer -> Complex Double -> Bool
          q 0 _ = True 
          q t z = if r > 2 then False else q (t - 1) z'
              where z' = p + z^2
                    r = realToFrac . realPart . abs $ z' 

pointList :: (Double, Double) -> (Double, Double) -> [(Double, Double)]
pointList (xBegin, xEnd) (yBegin, yEnd) =
    [(x, y) | x <- axis xBegin xEnd, y <- axis yBegin yEnd] 
    where axis b e = takeWhile (<e) $ zipWith (+) (repeat b) (scanl1 (+) $ repeat dist)
              where dist = (e - b) / fromIntegral pointSize

mandelPointList :: [(Double, Double)] -> [(Double, Double)]
mandelPointList = filter (\(x, y) -> isMandelPoint $ x :+ y)

serDoublesData :: [(Double, Double)] -> Put
serDoublesData zs = mapM_ putFloat64le $ xs ++ ys 
                    where (xs, ys) =  unzip zs

main :: IO ()
main = do let fn = "mandelbot.bin" 
          let p = mandelPointList $ pointList (-2, 1) (0, 1)
          BL.writeFile fn (runPut (serDoublesData p))
          putStrLn $ "Finish write " ++ fn

練習寫這個程式算是長知識,因為很多基本的事其實都不太會,做個記錄哩。

Comments

[Haskell Practice] Execute shell command

算是今天做的小練習,為了要讓 ghc-fllvm 選項,發現 ghc 支援的 llvm 版本為 3.3,所以自己寫了一個程式練習執行 shell command

import System.Directory
import System.FilePath.Posix
import Data.String.Utils
import Control.Applicative
import System.Process

main :: IO ()
main = do f <- filter (endswith "-3.3") <$> getDirectoryContents "./"
          let ori_f = map ("../../Cellar/llvm33/3.3_1/bin/" </>) f
          let ln_f = map ((</>) "llvm33" . (\x -> take (length x - 4) x)) f
          mapM_ (\(n, n') -> readProcess "ln" ["-s", n, n'] "") (zip ori_f ln_f)

在執行完 brew install homebrew/versions/llvm33 且建立好 /usr/local/bin/llvm33 資料夾後在 /usr/local/binrunhaskell 執行 就可以了。

只是單純留下來備忘,有些 function 也是臨時查的 XD。

Comments

[Haskell Practice] Get the postive-edge probability for throwing a coin with n times

很久很久以前 Josh 有寫過 one-linear code,不過我現在只能用 (>>=) 硬拼成一行 ... 估計我這樣子是做弊的方式,哈。

module R1000 where

import System.Random

divI :: Fractional a => Int -> Int -> a 
a `divI` b = fromIntegral a / fromIntegral b

prob :: Fractional a => Int -> Int -> a 
x `prob` y = x `divI` y * 100.0

trues :: Int -> IO Int
trues n = newStdGen >>= \gen -> return $ length . filter (==True) $ (take n $ randoms gen :: [Bool])

positive :: Fractional r => Int -> IO r
positive n = trues n >>= \x -> return $ x `prob` n

positive' :: Fractional r => Int -> IO r
positive' n = newStdGen >>= \gen -> return (length . filter (==True) $ (take n $ randoms gen :: [Bool])) >>= \x -> return $ x `prob` n

positive'' :: Fractional r => Int -> IO r
positive'' n = do gen <- newStdGen
                  let pos_sides = length . filter (==True) $ (take n $ randoms gen :: [Bool])
                  return $ pos_sides `prob` n

在 ghci 輸出範例結果如下

*R1000> positive 1000
50.7
*R1000> positive 10000
50.09
*R1000> positive 100000
50.248000000000005
*R1000> positive 1000
49.2
*R1000>

Comments

[Haskell Practice] List 10 x 10 results

無聊做的簡單練習,把目前想到的列在下面,以前 Su Horng 有列過,不過我也懶的找了。

其實這幾個都是大同小異,只是用不同的方式寫出來而己。

import Control.Applicative
import Control.Monad

sol = [x*y | x <- [1..10], y <- [1..10]]

sol1 = concat $ map (\x -> map x [1..10]) $ map (*) [1..10] 

sol2 = (*) <$> [1..10] <*> [1..10]  
-- sol2' = pure (*) <*> [1..10] <*> [1..10]
-- sol2'' = [(*)] <*> [1..10] <*> [1..10] 

sol3 = liftM2 (*) [1..10] [1..10]
-- sol3' = liftA2 (*) [1..10] [1..10]

sol4 = do x <- [1..10]
          y <- [1..10]
          return (x*y)
-- sol4' = [1..10] >>= \x -> [1..10] >>= \y -> return (x*y)

有想到再補上。這幾個的輸出結果都會是

Prelude Control.Applicative> pure (*) <*> [1..10] <*> [1..10]
[1,2,3,4,5,6,7,8,9,10,2,4,6,8,10,12,14,16,18,20,3,6,9,12,15,18,21,24,27,30,4,8,12,16,20,24,28,32,36,40,5,10,15,20,25,30,35,40,45,50,6,12,18,24,30,36,42,48,54,60,7,14,21,28,35,42,49,56,63,70,8,16,24,32,40,48,56,64,72,80,9,18,27,36,45,54,63,72,81,90,10,20,30,40,50,60,70,80,90,100]

Comments

[Haskell Practice] List all files in a directory recursively

寫的蠻差的,不過總算是拼出來了,這幾天有空再來寫漂亮 ... 這一陣子為了練習 Haskell,有好多事都沒有做,是該趕快把其他事完成了 ... Orz。

Comments

我的計算機探索

大家好,我是 Wen-Shih Chao,從大學之後大家都叫我 Yen3,我是從這個系上的大學和研究所畢業的,今天很開心 Chun-Liang Lee 老師給我這個機會來說明分享一下自己的故事,我有很多事情想要說,希望可以在半個小時講完。

我從很小的時候開始使用電腦,一直到高中的時候才開始學習程式設計。高一上的時候我參加了彰中電研社學習程式設計,但是我上了兩次社課聽不懂之後就放棄了。在那個時候的我以為我這輩子應該會去念個中文系,這輩子不再碰電腦之類的。結果在高一下的時候學校的老師開設了一個學習如何寫 C++ 的課程 ,那時候的我心想,這可能是我最後一次機會開始學習程式設計了,報名參加之後,我對我高中的印象最深的就是常常拿 A4 紙出來練習寫程式碼,學習如何寫程式來解決問題,就這樣子渡過了我的高中生涯,但是因為高中玩社團玩了兩年,且我也不太會念書,在最後一年不希望自己後悔的狀況下,成績還算普通的考上了這裡。

剛進大學其實也不是很清楚知道自己想要做什麼,但是沒有好好念書這一項,能翹課就翹,曾經有一段時間,不管上麼課,都是帶程式設計的書在課堂上看,然後回宿舍就拼命玩電腦遊戲和寫程式。或許是因為寫程式可以找到自己的成就感,不過更多的是把程式寫出來的開心,也因為個性因素使然,剛開始的大學生活朋友並不多,在這段時期幾乎把全部的心力投注在這裡面。這樣子行為直接反應在我的大學成績裡面,不過我也並不在乎,總覺得活的像自己就好了。

高中寫程式的時候,因為是與很多朋友一起寫程式,所以要寫什麼程式我並沒有思考太多,而大一大二的時候,除了課堂上的程式設計題目,老實說我並不知道我想要解決什麼問題,在那個時候做的就是拼命買書看書,在那個時候看了很多關於 C++ 與軟體工程的書,開始思考程式該長成什麼樣子,該解決怎麼樣的問題 ? 電腦的軟體與硬體如何互動,電腦的計算能力是否有所極限 ? 這些問題都變成我這幾年來一直在思考的問題。而這些問題有些有了答案,而有些到現在還在思考,為什麼要思考這些的問題呢 ? 因為我想要讓自己程式寫出更快的程式。

看起來人生好像很認真,其實不然,大學是我看最多日劇與動漫的時候,也常常躲起來無所事事好幾天。曾經有一天我朋友問我有去上課的朋友,你有看到 Yen3 嗎 ? 他好像好幾天沒來上課了,但是其實我都在看海賊王動畫或日劇之類的。但是之後不要讓朋友擔心,我還是上課去,但是我很確定在課堂上不是在做該課堂的事 (笑)。

而且大學的時候對自己一直都很沒有自信,因為只喜歡寫程式,而且以社會的觀感來看,我念了一間普通的大學,成績也普普通通,生活也很普通,並沒有特別努力像名人傳記一樣力爭上游。這樣子的生活下去會怎麼樣好像是看的出來的。但也因為如此,我也過的蠻開心的。當然有機會的時候會想要好好表現自己,不過好像都失敗了,幸好當下都不覺得會影響到自己想做的事。

在大學的時候,我跟著 cllee 老師參加了兩個比賽,所幸都沒有得獎。一個是比賽撰寫矩陣相乘程式的比賽,在這 cllee 老師的指導下順利的完成,但是程式跑出來的時間整整多別人了一倍。我們在賽後與 cllee 老師一起尋找為什麼比別人慢的原因。程式比別人慢沒關係,找到原因下次總是會比較快。

另外一個比賽是從提案到實作及報告自己想法的 App 比賽,這個比賽讓我暫離技術層面以外的問題,去加以了解一個點子的發想及實現,除了寫程式還有許多重要的事,但是除了寫程式以外的事,我好像也沒有會多少,我從這次也了解從創意發想到完成的過程中,我所喜歡扮演的角色。

後來考研究所的時候,處於一個隨便的狀態,於是就直升了自己學校的研究所,很幸運的跟 Yung-Cheng Ma 老師做研究,他是一個做研究很嚴格但是待人很好的老師,他教我最重要的事就是,寫程式只是解決問題的方式之一,重點是你想要解決什麼問題。他完全讓我體會沒有任何想法根本無法解決問題,更遑論寫程式了,在那個當下,我真的覺得研究所這兩年過的頂痛苦的 (笑)。不過我一直到現在都記得他跟我說的一段話。

寫程式並不是最重要的,找到想要解決什麼問題是最重要的。然後把你想要解決問題的相關領域學習起來。舉個例子來說 MIT Media lab 裡面的人,有歷史系、美術系與心理系等等,但是計算機科學系的比例並不是特別的大。

研究所之後呢 ? 負擔著對於研究的害怕及對於自己只會寫程式的茫然,在博士班及當兵的時候試著逃脫這個想法,但是始終沒有什麼好成果。但是慢慢的知道自己只會寫程式相關部分,那麼把解決問題需要但是自己不會的部分再慢慢學習起來就是了。

在計算機科學這個領域,我過的很開心,對我來說,學習計算機科學就是面對真實的自己,電腦不會騙人,要不他人出錯了,要不我出錯了,但是我比較笨,我出錯的機率應該相對較高。計算機科學是需要用精確的語言來描述自己想法的世界。

我一向認為我不聰明,只是我一向對自己想要做什麼事不太知道怎麼放棄,也就這樣子過到了現在。在這個生活中,我只是專注在自己想做的事上,我覺得我很幸運,因為這個興趣可以讓我有份工作而且活的不錯。

最後,我想說明為什麼會有這個探索的過程 ? 簡單來說,在時間有限的狀況下,我會選擇自己想做的事來做,因為我一向很難專注,我會覺得很多事很有趣,但是專注一件事足以把嘗試許多有趣的事時間吃掉。所以我得選擇我把時間分配到什麼事情上。

如果這件事值得我花時間,那麼我就會去做。

祝各位可以找到自己想做的事,這並不容易,我自己也在尋找,一起加油吧。

What we can do now practically

講完一個簡單的故事,我想嘗試說幾個當初如果我大一就知道事會很棒的事,金玉良言一向都容易理解但是不容易體會。

  1. 開始時間管理 - 因為時間有限,但想做的事有很多。對我來說時間管理是取捨的藝術。我每個一段時間就會重看 Randy Pausch - Time management (中文字幕),如果你有興趣也可以看看。
  2. 嘗試從網路上學習,並與人討論 - 自學通常最大的問題來自於沒有人可以討論及自我反省不一定有用,可以看看 Courseraedx,好好跟完一兩門課,你會發現你有許多有趣的改變。
  3. 最後,也是最重要的,把我上述提到的三個網址點開來看看。因為大一的我是看過就算的 (笑)。

Finally

然後,我們可以開始來講一些其他的有趣部分 :) 因為前面的訊息如果有機會,我相信你已經在聽我演講之前看完了。

如何知道自己對這門學系有沒有興趣 ? 這其實不容易,你可以詢問你自己,是否願意勉強自己做一些不喜歡的事 ? 這跟喜歡打籃球棒球一樣,你喜歡,但是你一定要做基礎訓練才打的好,但是做基礎訓練很痛苦,不做又打不好一樣。每個學門或專業都有你不喜歡做的事,端看你能不能為了你想要做的事來忍受這些不喜歡的事。

舉個例子來說,我大一的時候英文其實差到不行,計算機概論的課本第一頁就看了一個小時,第二個還是看了一個小時,後來才慢慢開始變快。這件事在看 C++ 相關的書的時候又重演了,第一頁看了二個小時,第二頁還是看了兩個小時,不斷的重覆到看一頁只需要二十分鐘。一直到現在,我看某些英文書還是很慢,但是為了要理解,只能不斷的逼迫自己做自己不喜歡的事直到熟練為止。

有時候可以強迫自己做一些不擅長的事,會有一些意想不到的進步。就像我最近要強迫自己看不想看的平行程式設計書籍一樣 … 真的是很難,但是不看懂不行 (笑)。

如果自己對這個系沒有興趣怎麼辦 ? 你還有很多時間可以重來,但是如果不敢重來,我相信人生就是這樣子一步一步的過,然後就這樣子結束了,這也是你的選擇。

想顧好學業,也想要有愛情,更想要有多采多姿的大學生活,該怎麼辦 ? 時間有限,能力與精神也有限,如果你覺得你很聰明可以顧好全部的事,就去做,如果不行要硬幹,也去做,不管怎麼樣,你總是可以從中學習到你自己與時間。但是盡可能不要發生到大四甚至後來才哭哭啼啼說大學應該要好好努力的過,當初應該多看點書之類的。

試想想你現在要怎麼過,以後才不會想要說後悔的話。

謝謝你耐心聽完我講了三十分鐘的故事(其實應該會超過三十分鐘),如果你睡著了,至少我們渡過一段愉快的時間,而且等一下就可以吃披薩了(耶~),如果你可以從中獲益,謝謝你喜歡。

Q & A

  • Q: 以資工系的角度來說,微積分與普物重不重要 ?

    • 是重要的,雖然這兩堂課並不能一定實際運用,但是可以教會你怎麼思考一個問題轉換成數學問題。
    • 微積分很可愛,試想想為什麼可以從 FTC 開始就可以串起全部的故事。
    • 大一的學習其實是打基礎,不妨利用這種時間思索想要解決什麼問題,以及你要用什麼方式來解決。
  • Q: 我們現在學的是 C++ ,看起來業界是需要 C 的人才,我們會需要學習 C 嗎 ?

    • 不管那裡都會需要會解決問題的人。建議先學好一種語言,以大家所知的程式語言來說,學會一個語言之後,要在短時間內上手另外一個語言難度並不高 (但是要精通該語言還是需要很多時間)。
    • 學好程式語言與程式設計是相當重要的,以我的角度來說,學會程式設計與思考要解決什麼問題兩個是同等重要的問題。
  • Q: 如果遇到不會寫的程式怎麼辦 ?

    • 如果覺得是自己現在無法決解決的程式而且用盡了辦法,就放著,然後有一天想到了就解決他。
    • 學習已經從考試變成你要怎麼面對自己的一個故事 :)。
  • Q: 大一學生可以練習什麼程式呢 ?

    • 建議可以上 coursera 修課,是一個不錯的選擇。
      • Introduction to Python,會教你 Python 入門,最後的期末作業是用 Python 做出一個遊戲。
      • 也有所謂的網頁設計課程,Big Data (其實是 Data mining/ Machine learning 課程),以及其他零零總總的課程。
    • 如果是單純的想要練習邏輯的話,可以考慮 UVA Online JudgeProject Euler,可以跟同學一起練習。
    • 如果有興趣的話,我們可以一起討論該如何進行。
  • Q: 大學最該做的一件事與最不該做的一件事 ?

    • 最該做的一件事: 去旅行,去一些你過往不會去的地方 (但盡可能確保安全)。我們都以為我們了解了這個社會,其實我們只知道都市的繁榮或鄉村的溫暖,但是很難去理解都市與鄉村中還存在些什麼。
    • 最不該做的一件事: 為了學分去修一門爛課,人生有限,不要浪費時間,盡可能修自己喜歡的課。

Thanks

我想感謝我的很多朋友在這段時間的相處,其實這個探索過程並不孤獨,在大一的時候遇到 Josh Ko,他比我聰明,也更認真及堅定追求自己想要的,現在是一名博士後研究員了,他讓我學會很多很多事,fire7617, eating, Clara, decay, Melting 都是我在大學時候的朋友。yi-chen 在我人生很沮喪的時候陪我渡過很多日子直到現在 :)。很多老師 cllee, ycma, gwchen, scm ... 及很多朋友 (jaiyalas, chi-en, godfat) 幫了很多忙,因為這不是論文致謝,就此打住,如果有一天還有機會寫的話,那名字大概就會很多書的感謝名字列表一樣長吧 XD。

Comments

murmur (7) - 慢與前進

從決定了一件很重要的事情以來,心情終於平靜了很多。人總是會有所傍偟,但是還可以堅定的朝自己的路前進。

其實過往的自己有提到慢即是快的哲學,但是我覺得我自己並沒有懂過。最近在看一些書,學習一些事情的時候,其實並不能太在乎自己可以學習的多快,而是自己有沒有把看到的確實理解。不然其實我還是要重看重新想很多遍,反而更浪費時間。不過也因為如此,慎選自己看的資料,就算看到不好的資料也當成一種思維練習。希望重覆這個行為,能讓自己的想事情的方式更加穩定吧。

穩定下來,才會有辦法做自己想做的事。現在的我是這樣子想的。

前幾天有與人聊到,要不要把網路上過往的自己的所做所為刪除掉。我的回答是,不想也做不到。我在網路上 po 的文章也是過往的自己做的。就保持過往的自己會很好。我的過往是一個小屁孩與中二的集合體,也做了很多得罪人也讓人不開心的事,所幸沒發生大事情,在這邊表示一個抱歉 (不過我估計也沒有人會看的到,也好,下次遇到每一個想道歉的人就好好的道歉)。但是也因為過往的自己與這些經歷造就了現在的自己,總是會帶著微笑觀看自己的過往,期待現在與未來的生活可以繼續的進步了。


前幾天開始 review 自己寫的 SNPA,SNPA 是一個針對 nikola (a static blogging system),寫的個一個小程式,主要功能為提供一個網頁介面可以新增, 編輯及刪除 nikola 的文章 (唉,就是檔案啦)。介面還可以,不過程式碼爛到我想重寫了 XD,本體的 code 倒是不多,300 行上下,所以今年應該會找個機會重寫整個 code 吧,然後希望可以改成用 nikola plugin 的型式。

這一年使用下來,介面還算滿意,其實現在都習慣使用 markdown 來寫簡單的 blog article ,我會需要 markdown preview 功能,但是不需要與寫作區域並行,我會因為這樣子容易分心。不過長時間使用下來會發現介面上有一些不需要的額外元素,之後也可以一並移除掉就是了。還有其他許許多多的改進可以做。就看自己有沒有機會啦 XD。

Comments

2015 年目標

完成 2014 年目標。

Comments

murmur (6) - Life

到底有多久沒有跟大家見面了呢 ? 其實我也不知道 XD。

不過可能是自己懶性使然,外加覺得自己一直沒有做到事,但是又想休息,就這樣子一直在惡性循環。不過暫時也不想理這麼多,決定能不休息就不休息,盡可能的把現在手上想寫的程式寫完告一個段落吧。

發現自己總是東怕西怕的,但是好像永遠都會是這個樣子,有時候其實也不想管這麼多,就這樣子一直寫程式吧 ~

很多人說過生活像什麼樣子,其實覺得生活像什麼樣子就是什麼樣子,哈。

Comments

murmur (5) - 音樂

在工作的第二個月就從 iTunes store 買了 The Beatles 全集,完成自己以前很想買的心願,但是我一直到現在都還沒聽完全部的專輯,可能要等以後有機會吧。這一年從該 iTuens store 買了約 20 ~ 30 張專輯吧,到底買了幾張我也不知道,但是聽起來有點缺憾,是一種說不出來的感覺,一直到最近我聽了 Linkin Park 的無損和 iTunes store 上買的做比較。在自己的音響上聽起來完全是兩張專輯,The Fray 是另外一個聽起來差很多的專輯 … 可能以後真的想要買正版專輯還是得買 CD 吧。

Comments