星期二, 3月 09, 2010

Haskell Practice - Prime (2)

在寫了一個第一篇之後,scm 老師給予了很多建議

scm 提到...
Interesting code :). Some comments:
  1. 如你所說 isPrime 是 map 加上 foldr (不過這個 isPrime 測的好像是「不是質數」?)。另外,makePrimeList 是 filter.
  2. 其實 (&&) 這個 operator 碰到第一個參數是 False 的時候也並不會去算第二個。isPrime2 和 isPrime 的另一個不同點是碰到 y < sq 就停下來吧?這也可以用先做一個 takeWhile 達成。
  3. 用 makeList 的版本為什麼比較慢不能馬上斷定,一個猜測是和 x ++ [c] 有關係。串列的 (++) 花的時間和第一個參數的長度成正比,所以每產生一個新的 c 都得從最開頭把這個串列旅行一遍。
    另外,由於 makeList 是 tail recursive 的,makePrimeList 必須等到整個 6n+1 6n+5 的串列產生完畢後才能動作。(比較之下 makePrimeList_2 則可以隨到隨做,[2..x] 這個 list 的元素生出來、測試過後,就丟掉了,並不佔空間。)不知道 makeList 會不會使得 heap 使用量變大,GC 變多,程式就慢了。你可寫一個不是 tail recursive 的 makeList 試試看嗎?

所以第一個問題 isPrime 是錯的,因為我一開始是寫 notPrime XD,但是問題算小,我馬上重寫了一下(順帶一提, scm 老師說的 && 特性,我不確定 Haskell 有,現在知道有了,記得這有一個名詞稱呼這種特性,但是忘了是什麼,在寫 C/C++ 時很常用,大部分是用在 pointer check is not null 上。)

prime :: Integer -> Bool
prime x 
    | x == 2 = True
    | otherwise = 
        isPrime x [2..sq]
        where sq = truncate (sqrt (fromIntegral x)) + 1

isPrime :: Integer -> [Integer] -> Bool
isPrime x y
    | x == 2 = True
    | otherwise =
         case y of 
             [] -> True
             y:ys -> (x `mod` y /= 0) && isPrime x ys

這樣子應該就沒有錯了...(汗),然後我們再很快速的寫成 map 格式,也連帶的使用到 lambda function ,因為我不知道怎麼樣寫的比較精簡了 XD

isPrime4 :: Integer -> [Integer] -> Bool
isPrime4 x y
    | x == 2 || y == [] = True
    | otherwise = and (map ( \e -> x `mod` e /= 0) y)
--     | otherwise = and (map (/=0) (map (x `mod`) y)) 

接著我再把稍微改版的程式試著用 takeWhile 改寫(takeWhile 的相對是 dropWhile)

isPrime5 :: Integer -> [Integer] -> Bool
isPrime5 x y 
    | x == 2 = True
    | otherwise =
        isPrime5' x (takeWhile  (< (truncate (sqrt (fromIntegral x)) + 1)) y)

isPrime5' :: Integer -> [Integer] -> Bool
isPrime5' x y =
     case y of
         [] -> True
         y:ys -> (x `mod` y /= 0) && isPrime5' x ys

最後一個問題就是 makeList,我就沒有寫了,我把 makePrimeList 寫成如下型式

makePrimeList4 :: Integer -> [Integer]
makePrimeList4 x = [2, 3] ++ makePrimeList4' 5 x False [] 

makePrimeList4' :: Integer -> Integer -> Bool -> [Integer] -> [Integer]
makePrimeList4' c e b x
    = if c < e then
          if isPrime5 c x then
              makePrimeList4' (c+add) e (not b) (x ++ [c])
          else 
              makePrimeList4' (c+add) e (not b) x
      else x
      where add = if b then 4 else 2

這樣子的 code 就不需要另外產生 list ,因為產生的當下就檢查,不要就丟掉了,然而在生成 prime list 的時候還是 tail recursive ,有嘗試過另外的方法,卻發現快不起來。

如果要將 (x ++ [c]) 變成 ([c] ++ x),我嘗試寫了另外一個 isPrime7

isPrime7 :: Integer -> [Integer] -> Bool
isPrime7 x y 
    | x == 2 = True
    | otherwise =
        isPrime5' x (dropWhile (> (truncate (sqrt (fromIntegral x)) + 1)) y)

這樣子的確可以完全避免掉 tail recursive 的問題,但是速度會比較慢,因為產生的數列是 11 7 5 3 2 這樣子的排序,一般檢查是否為質數是正向檢查,逆向的時候能夠在檢查次數上佔到的便宜其實不多 (如果該數是被 5 整除的話...),所以這樣子寫反而比較慢,目前的想法是,如果想要完全漂亮的解決 tail recursive 問題的話,勢必是得重新設計方法而且更了解這個語言的。

---
可見自己數學真的不好 ... Orz

張貼留言