« 2010年7月 | トップページ | 2010年9月 »

2010年8月

2010年8月30日 (月)

Haskell の fibonacci が遅い理由が分かった

 Haskell の勉強のためにちょくちょく覗かせてもらっているブログに『Haskellの神話』という記事が載っていました。
 詳しいことは元のブログを読んでもらうとして、簡単に説明すると

  • Haskell で有名な "fibs = 0 : 1 : zipWith (+) fibs (tail fibs) " という実装は、実はかなり遅い。
  • その原因は Haskell の特徴である「遅延評価」のせいである。
  • (+) を「正格評価」してくれる "zipWith'" を "seq" を使って自前で定義すると "fibs" はとても速くなる
ということらしいです。
 『Haskellの神話』のコードを基に次のようなコードを書いてみました。
-- test1 fib n = fibs !! n fibs = 1 : 1 : zipWith (+) fibs (tail fibs) main = print $ fib 100000
-- test2 zipWith' f (a:as) (b:bs) = x `seq` x : zipWith' f as bs where x = f a b zipWith' _ _ _ = [] fib n = fibs !! n fibs = 1 : 1 : zipWith' (+) fibs (tail fibs) main = print $ fib 100000
 実際に試してみると、
$ time ./test1 42026927029951543863190051012939151 ..(以下略) real 0m3.122s user 0m2.332s sys 0m0.016s
$ time ./test2 42026927029951543863190051012939151 ..(以下略) real 0m0.858s user 0m0.232s sys 0m0.004s
といった具合で、あまりの差に愕然……。

 自分の場合、「Fibonacci 数列」を

fibonacci :: Integral a => [a] fibonacci = fibs 1 1 where fibs a b = a : fibs b (a + b)
というふうに定義していたのですが、これだと「test1」とほぼ同じでした。
 そこで私も "seq" を使って自前の「Fibonacci 数列」をちょいと改造してみました。
fibonacci :: Integral a => [a] fibonacci = fibs 1 1 where fibs a b = seq a $ a : fibs b (a + b)
 これはほぼ「test2」と同じ性能のようです。

 Haskell は「遅延評価」のおかげで簡単に「無限リスト」を操作する手段を手に入れたけど、そのせいで計算が遅くなることがあるということなんですね。
 "seq" を使った「正格化」での速度改善とかはどこでも使える分けではなさそうだし、素人の私には使いどころが分からない……。
 Haskell の奥はとんでもなく深そうですね。(だいたい、まだ「モナド」がよく分かっていないし……)

2010年8月27日 (金)

Project Euler : Problem 46 ~ Goldbach予想

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 この問題では、まず「Goldbach の予想」に合う数かどうかを判定する「isGoldbach 関数」を定義しました。
 次に、「isGoldbach 関数」が「偽」になる数の先頭を探しました。
 なんの工夫も無いですね……。

import ForEuler (isPrime) isGoldbach :: Integer -> Bool isGoldbach n = or [isPrime (n - s) | s <- takeWhile (< n) wSquare] where wSquare = [2 * x * x | x <- [1 ..]] problem046 :: Integer problem046 = head $ filter (not . isGoldbach) xs where xs = filter (not . isPrime) [3, 5 ..] main :: IO () main = print problem046

2010年8月26日 (木)

Project Euler : Problem 45 ~ 三角数、五角数、六角数

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 六角数は必ず三角数になります。したがって、この問題は 40755 より大きい五角数かつ六角数を探せばいいことになります。
 今回は単純に「五角数」のリストと「六角数」のリストを小さい方から比べていきました。

import ForEuler (polyNumList) -- 40755 より大きい五角数 pentagon :: [Integer] pentagon = dropWhile (<= 40755) $ polyNumList 5 -- 40755 より大きい六角数 hexagon :: [Integer] hexagon = dropWhile (<= 40755) $ polyNumList 6 problem045 :: Integer problem045 = iter hexagon pentagon where iter (h : hs) ps | h == p = h | otherwise = iter hs ps' where ps'@(p : _) = dropWhile (< h) ps main :: IO () main = print problem045
 コンパイルして実行すると私のノートパソコン(Pentium M, 1500MHz)では、約 0.05 秒で答えが出ました。
 リスト操作を繰り返す割には速く結果が出ました。

2010年8月19日 (木)

Project Euler : Problem 44 ~ 五角数

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 Ruby 版と同じ方法で解いてみました。

import ForEuler (polyNumList, isPolyNum) import Data.List (find) import Maybe (isNothing, fromJust) pentagonList :: [Integer] pentagonList = polyNumList 5 isPentagon :: Integer -> Bool isPentagon = isPolyNum 5 problem044 :: Integer problem044 = loop (tail pentagonList) [1] where loop (p : ps) pent | isNothing a = loop ps (p : pent) | otherwise = p - fromJust a where a = find check pent check p' = all isPentagon [p - p', p + p'] main :: IO () main = print problem044
 これが遅い!コンパイルして実行すると、私のノートパソコンで約 8 秒かかりました。いわゆる 1 分ルールには引っかからないのですが、Ruby 版より遅い……。
 リスト操作のコストが高いのでしょうか?それとも「find 関数」のコストが高いのが原因でしょうか?

 他の方法を自分でもいろいろ考えたのですが、いい方法を思いつきませんでした。
 そこで、ネットを探したところ、こちらのブログにいい方法が書いてありました。自分も、式の変形を使って解けないかと考えたこともあったのですが、この解法までたどり着けませんでした。
 ということで、こちらの解法を参考にコードを書いてみました。

import ForEuler (polyNumList, polyNum, isPolyNum, divisor) import Data.List (find) pentagonList :: [Integer] pentagonList = polyNumList 5 pentagon :: Integer -> Integer pentagon = polyNum 5 isPentagon :: Integer -> Bool isPentagon = isPolyNum 5 divsPair :: Integer -> [(Integer, Integer)] divsPair n = takeWhile (\ (a, b) -> a <= b) $ zip ds (reverse ds) where ds = divisor n mn :: Integer -> [(Integer, Integer)] mn k = [(div (a + c) 2, div (c - a) 2) | (a, b) <- divsPair (2 * k), rem b 3 == 2, let c = div (b + 1) 3, a < c] probrem044 :: Integer probrem044 = pentagon m - pentagon n where Just (m, n) = find check $ concatMap mn $ pentagonList check (m, n) = isPentagon (pentagon m + pentagon n) main :: IO () main = print probrem044
 こちらの方法では、コンパイルして実行すると約 0.17 秒で答えが出ました。あまりの違いにビックリしてしまいました。

2010年8月14日 (土)

Project Euler : Problem 43

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 まずは brute force 版です。

import Data.List (permutations) import ForEuler (listToDex) -- ex : convert [1,2,3,4,5,6,7,8,9,0] => [890,789,678,567,456,345,234] convert :: Integral a => [a] -> [a] convert xs = map listToDex $ loop xs [] where loop [a, b, c] prd = [a, b, c] : prd loop xs@(x : xs') prd = loop xs' (take 3 xs : prd) nums :: [Integer] nums = [listToDex xs | xs@(x : _) <- xss, x /= 0, check xs] where xss = permutations [0 .. 9] -- 辞書順である必要は無いので…… check ns = and [z == 0 | z <- zipWith (rem) (convert ns) divs] where divs = [17, 13, 11, 7, 5, 3, 2] problem043 :: Integer problem043 = sum nums main :: IO () main = print problem043
 10 桁の Pandigital な数を作るのに「順列」を使いました。
 今回は順列の結果が辞書順に並んでいる必要は無いので、自作の "permutation" ではなく "Data.List" モジュールの "permutations" を使いました(こちらの方が速いので……)。
 "convert" 関数はコメントにも書いてあるように [d1, d2, d3, d4, d5, d6, d7, d8, d9, d10] というリストを与えると [d8d9d10, d7d8d9, d6d7d8 .. d2d3d4] といったリストを返します。
 この解き方は順列の結果を総当たりするので非常に遅いです。

 次は Pandigital な数を作っていく方法です。

import Data.List ((\\)) import ForEuler (listToDex) -- 条件に合う Pandigital 数の集合 nums :: [Integer] nums = [listToDex (x : xs) | xs <- xss, let x = 45 - sum xs, x /= 0] where xss = foldl func yss [17, 13, 11, 7, 5, 3, 2] yss = [[a, b] | a <- [0 .. 9], b <- [0 .. 9], a /= b] func xss d = concatMap (makeList d) xss makeList d xs = [ys | x <- [0 .. 9] \\ xs, let ys = x : xs, check ys] where check ys = rem (listToDex $ take 3 ys) d == 0 problem043 :: Integer problem043 = sum nums main :: IO () main = print problem043
 こちらの方法では "makeNewList" 関数が非常に大事な役割を演じています。
 "makeNewList" 関数は整数 d と一桁の整数のリスト xs が与えられると、xs に含まれない数を一つずつ xs の先頭につけ足していって、新しいリストの先頭から 3 桁が d で割りきれるものだけを返します。
 具体的には
> makeNewList 3 [1,2,3] [[0,1,2,3],[6,1,2,3],[9,1,2,3]]
といった具合になります。
 新しいリストを作っていく過程で候補がどんどん絞られていくので、こちらの方法はかなり速く答えが出ます。

 次のように "nums" をちょっと書き換えて GHCi 上で実行すると、実際に候補が絞られていく様子が画面に表示されます。

import Debug.Trace import Data.List ((\\)) import ForEuler (listToDex) -- 条件に合う Pandigital 数の集合 nums :: [Integer] nums = [listToDex (x : xs) | xs <- xss, let x = 45 - sum xs, x /= 0] where xss = foldl func yss [17, 13, 11, 7, 5, 3, 2] yss = [[a, b] | a <- [0 .. 9], b <- [0 .. 9], a /= b] func xss d = trace (show xss) (concatMap (makeNewList d) xss) makeNewList d xs = [ys | x <- [0 .. 9] \\ xs, let ys = x : xs, check ys] where check ys = rem (listToDex $ take 3 ys) d == 0
Main> nums [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8]] [[9,0,1],[1,0,2],[2,0,4],[3,0,6],[4,0,8],[5,1,0],[6,1,2],[7,1,4],[8,1,6],[0,1,7],[9,1,8],[4,2,5],[5,2,7],[6,2,9],[7,3,1],[0,3,4],[9,3,5],[1,3,6],[2,3,8],[3,4,0],[7,4,8],[8,5,0],[0,5,1],[9,5,2],[1,5,3],[3,5,7],[4,5,9],[5,6,1],[7,6,5],[8,6,7],[0,6,8],[1,7,0],[3,7,4],[4,7,6],[5,7,8],[6,8,0],[7,8,2],[0,8,5],[9,8,6],[1,8,7],[2,8,9],[3,9,1],[4,9,3],[6,9,7]] [[3,9,0,1],[9,1,0,2],[5,2,0,4],[1,3,0,6],[3,5,1,0],[8,7,1,4],[4,8,1,6],[0,9,1,8],[0,5,2,7],[2,7,3,1],[7,9,3,5],[0,1,3,6],[9,2,3,8],[2,3,4,0],[1,9,5,2],[7,1,5,3],[8,4,5,9],[2,8,6,7],[6,3,7,4],[2,4,7,6],[4,6,8,0],[0,7,8,2],[2,0,8,5],[5,9,8,6],[7,2,8,9],[0,3,9,1],[1,6,9,7]] [[5,3,9,0,1],[8,9,1,0,2],[3,5,2,0,4],[9,1,3,0,6],[9,3,5,1,0],[7,4,8,1,6],[2,0,9,1,8],[6,0,5,2,7],[6,2,7,3,1],[7,9,2,3,8],[3,1,9,5,2],[6,7,1,5,3],[5,2,8,6,7],[9,2,4,7,6],[9,4,6,8,0],[4,0,7,8,2],[7,5,9,8,6],[5,7,2,8,9],[8,0,3,9,1]] [[7,3,5,2,0,4],[7,9,1,3,0,6],[6,9,3,5,1,0],[5,7,4,8,1,6],[4,2,0,9,1,8],[4,6,2,7,3,1],[6,7,9,2,3,8],[9,5,2,8,6,7],[3,9,2,4,7,6],[2,9,4,6,8,0],[1,4,0,7,8,2],[1,7,5,9,8,6],[3,5,7,2,8,9],[2,8,0,3,9,1]] [[0,9,5,2,8,6,7],[1,9,5,2,8,6,7],[3,9,5,2,8,6,7],[4,9,5,2,8,6,7],[0,3,5,7,2,8,9],[1,3,5,7,2,8,9],[4,3,5,7,2,8,9],[6,3,5,7,2,8,9]] [[3,0,9,5,2,8,6,7],[0,3,9,5,2,8,6,7],[6,0,3,5,7,2,8,9],[0,6,3,5,7,2,8,9]] [4130952867,1430952867,4160357289,1460357289,4106357289,1406357289]
 こんな風に内部データを見たいときには「trace 関数」 は便利ですね。

※「trace 関数」に関してはここを参考にさせて頂きました。

2010年8月 6日 (金)

Project Euler : Problem 42

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 すみません。何の工夫もしていません。

import ForEuler (isPolyNum) import Data.Char problem042 :: [String] -> Int problem042 ns = length $ filter isTriangle [wordValue x | x <- ns] where isTriangle = isPolyNum 3 wordValue cs = sum [ord c - ord 'A' + 1 | c <- cs] main :: IO () main = do ss <- readFile "words.txt" print $ problem042 $ read ("[" ++ ss ++ "]")

2010年8月 5日 (木)

Project Euler : Problem 41 ~ Pandigital な素数

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 解き方の基本的な考え方は「Ruby 版」をご覧ください。
 まずは、素直に数字を使って調べていくもの……。

import ForEuler (isPrime, isPandigital) problem041 = head (check xs ++ check ys) where check ns = [n | n <- ns, isPrime n, isPandigital n] xs = [7654321, 7654320 .. 1234567] ys = [4321, 4320 .. 1234] main :: IO () main = print problem041
 次に、順列を使うことで Pandigital 数かどうかのチェックを省いたもの……。
import ForEuler (isPrime, listToDex, permutation) problem041 :: Int problem041 = head $ check 7 ++ check 4 where check n = [x | x <- map listToDex ns, isPrime x] where ns = permutation [n, n - 1 .. 1] n main :: IO () main = print problem041

2010年8月 1日 (日)

Ruby の「メソッド」と Python の「関数」の違いは…

 Ruby と Python はどちらも「オブジェクト指向言語」として認識されていると思いますが、違う言語ですから当然文法や言語仕様はそれぞれ独自のものを持っています。そのため、 Python の知識で Ruby を理解しようとすると、ちょっとした誤解を招くことがあります(その逆もまた然り)。

 私がこの記事を書こうと思ったきっかけは、こちらブログでのやりとりでした。
 西尾さんが「引数のない関数呼び出しに括弧がいらない、かつ関数がファーストクラスの言語」の例として Ruby を挙げていらしたので、「それはちょっと違うのでは…」と思い、「ツムジ」の名前でコメントを書いたのですが、どうもうまく誤解を解くことができないようでした。
 以前も同じような記事を書いたことがあったのですが、「同じような勘違いをされている人が結構いるのかも?」と思ったので、自分なりにまとめてみようと思ったのでした。
 私は Ruby との付き合いは結構長いので、 Ruby に関してはある程度知っているつもりです。ところが、 Python に関しては表面をちょっとなぞった程度の知識しかありません。以下の記事の内容で、もし Python に関して間違ったことを書いていた場合は、コメント欄にその旨をご指摘いただけるとありがたいです。

 Python は「オブジェクト指向言語」であると同時に「関数型言語」の要素も持っている(マルチパラダイムってやつですね)ので、「関数オブジェクト」が存在しています。そのため Python では「関数」はファーストクラスになります。
 ところが Ruby はパラダイムとしては「オブジェクト指向」しか持っていません。そのため Ruby には「関数」は存在しません。
 Ruby で Python の「関数」に相当するのは「メソッド」ですが、 言語仕様上 Ruby の「通常のメソッド」はクラス、インスタンス、またはモジュールのいずれかに所属することになっています。そして Ruby における「オブジェクト」は「データ+メソッド」の形をとります。つまり「通常のメソッド」単独では「オブジェクト」として扱われないのでファーストクラスではありません。
 レシーバを指定せずに使える「puts」や「print」などは一見関数のように見えますが、実は「Kernel クラス」のメソッドです。またトップレベルで定義したメソッドもレシーバを指定せずに使えますが、こちらは「Object クラス」のプライベートメソッドとして扱われます。
 西尾さんはこちらブログのコメントに

オブジェクト指向であるかどうかとメソッドや関数がファーストクラスであるかどうかは背反ではなく…
と書いておられますが、「背反する・しない」ではなく Ruby では言語仕様上「通常のメソッド」は単独で「オブジェクト」として扱われないのです。

 また西尾さんは同じくコメントの中で

>> bar = Object.method(:foo) => #<Method: Class(Object)#foo> このメソッドオブジェクトはファーストクラスであるように見えますが、そうではないという主張でしょうか?
と書いておられます。
 これに関しては Ruby マニュアルのclass Methodの項目に
Object#method によりオブジェクト化されたメソッドオブジェクトのクラスです。
と書いてあります。これは「通常のメソッド」が単独では「オブジェクト」になれないので、わざわざ「Object#method」を使って「メソッドをオブジェクト化」するということです。
 ですから、 Ruby に関しては
引数のない関数呼び出しに括弧がいらない、かつ関数がファーストクラスの言語では、逆に「その関数自体」を意味する式をつくるために新しい文法が必要になる。
のではなく、
「メソッド」がもともとファーストクラスではないので、「メソッド」をファーストクラスとして扱うためには「Object#method」や「Method#call」といったものが必要になった。
ということなのです。

« 2010年7月 | トップページ | 2010年9月 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ