« 2010年3月 | トップページ | 2010年5月 »

2010年4月

2010年4月29日 (木)

人のブログの間違いが気になって……

 基本的に、ほかの人のブログの内容に口を出すのは好きじゃないんですが、どうしても気になることがあるので……。

 

 先日、Ruby に関するこんな記事を見かけました。

Rubyでは、すべてがオブジェクト。じゃないよ!

 この記事を書いた人は、Ruby の根本的なところで勘違いをしているようです。
 ある程度 Ruby や「オブジェクト指向プログラミング」について知識にある人ならすぐに分かる間違いなので、「そのままスルーしてもいいかな?」とも思ったのですが、もし Ruby のことをよく知らない人が読んだら混乱するのではないかと心配になったので、この記事を書くことにしました。

 問題の記事では、冒頭にこんなことが書いてあります。

 Rubyでは、すべてがオブジェクト。と説明される場合があります。確かに、「1」も「+」もクラス自体もすべてオブジェクトです。ですが、「ほぼ」すべてがオブジェクトであって、すべてではないんです。
 例をひとつ。ブロックはオブジェクトではありません。
 確かに Ruby では「すべてがオブジェクトである」と表現されることがあります。しかしこの場合の「すべて」は「すべてのデータ(例えば、文字列、配列など)」という意味になります。
 Ruby には「オブジェクト」以外に「オブジェクト」に属する「メソッド(例えば、 Array#size など)」や「制御構造(例えば、 if や while など)」なども含まれます。そして、一部のメソッド(%, + など)や制御構造(and, or など)は、「演算子」の形をとっています。
 上の文章の例で言えば、「1」はオブジェクトですが、「+」はメソッドです。また「ブロック」は制御構造ということになります。

 さらに記事の最後には

 このように、ブロックはオブジェクトではありません。他にRubyでもオブジェクトでないものに、「and」や「or」、「&&」や「||」などがあります。演算子が特別なのは当たり前だろと思う人は、LISPを調べてみると面白いかもしれません。
といった文章が書いてあります。
 すでに書いたように「ブロック」は制御構造です。「and」、「or」、「&&」、「||」も制御構造です。
 それから、LISP が引き合いに出されていますが、文章の流れからすると「LISP の演算子はすべて手続きである」といったことを表現したかったのでしょうか?
 確かに LISP ほとんどの演算子は手続きといっていいのですが、「and」や「or」など一部の演算子は、引数の評価を通常の手続きと同じようにしてしまうと異常事態に陥る可能性があるため、通常の手続きとは引数の評価のタイミングが違うマクロとして実装されているのが普通です。

 インターネット上のホームページやブログを見ていくと、簡単にいろいろな情報を手に入れることができます。しかし、中には不正確だったり、間違った情報もたくさんあります。
 正しい情報のみをふるい分けるのはなかなか難しいですけどね……。いろいろな記事を見比べたり、人に話を聞いたり、正しい情報を得るにはそれなりに努力が必要ってことでしょうか……。
 かくゆう私のブログの記事も、「思い込み」や「勘違い」で間違った情報を書いている可能性は十分にあります。記事の内容をあんまり鵜呑みにしないほうがいいかも……。

2010年4月24日 (土)

Project Euler : Problem 21 〜 友愛数

 問題はこちらをご覧ください。

 

 「約数の和」は素因数分解の結果から簡単に出すことができます(詳しくは『数学ガール』をご覧ください)。

 前に投稿した記事にも書きましたが、一回だけ素因数分解を行う場合、Ruby などの通常の手続き型の言語であれば、素数を求める事自体にかなりのコストがかかるため、素数列を作ってから素因数分解を行うより、2 及び奇数で割り続けた方が速く結果が出ます。
 ところが今回のように大量の素因数分解を繰り返し行う場合は、あらかじめ素数列を作っておいた方が速いようです。ただし処理を開始する時点では必要な素数の上限が分からないため、通常のプログラム言語では、あらかじめ多めに素数列を求めておいて素因数分解を始めるといった、少し無駄な計算を行うことになるかもしれません。

 その点、Haskell は遅延評価で処理を行うので、その時点で必要になった分だけ素数を計算しますし、一度計算して得られた素数列は処理が終わるまでずっと保持されるので、無駄はありません。
 そこで、今回は素数を求めながら素因数分解を行うようにしました。

import Data.List(group) -- 素数列 primes :: Integral a => [a] primes = map fromIntegral ([2, 3] ++ primes' :: [Int]) where isPrime m (x : xs) | x * x > m = True | rem m x == 0 = False | otherwise = isPrime m xs primes' = 5 : sieve 1 sieve n = filter (`isPrime` primes') ns ++ sieve (n + 1000) where ns = [6 * x + y | x <- [n .. n + 999], y <- [1, 5]] -- 素因数分解 factorize :: Integral a => a -> [(a, Int)] factorize 1 = [(1, 0)] factorize n = format $ factorize' n primes where factorize' n ps@(p : ps') | p * p > n = [n] | rem n p == 0 = p : factorize' (div n p) ps | otherwise = factorize' n ps' format ps = [(x, length xs) | xs@(x : _) <- group ps] -- 真の約数の和 sumOfDivs :: Integral a => a -> a sumOfDivs 1 = 0 sumOfDivs n = product [calc f i | (f, i) <- factorize n] - n where calc f i = div (f ^ (i + 1) - 1) (f - 1) -- 友愛数のペアのうち、小さい値が引数の範囲内にあるものを返す。 -- ex : amicablePairs 2 1200 => [(220,284),(1184,1210)] amicablePairs :: Integral a => a -> a -> [(a, a)] amicablePairs from to = [(x, y) | x <- [from .. to], let y = sumOfDivs x, x < y, x == sumOfDivs y] problem021 :: Int problem021 = sum [a + b | (a, b) <- amicablePairs 2 10000] main = print problem021
 以前紹介した素数列を求める関数と素因数分解を行う関数ががんばってくれたおかげで、私のパソコン (Ubuntu 9.10, Pentium M, 1500MHz) では約 0.04 秒で答えが出ました。これは、この問題を Ruby 1.9 で解いたときの約 10 倍の速さです。

 コンパイルをするのが面倒くさいと思うこともたまにはありますが、比較的簡潔なコードでかなり速いコードが書けるので、私のようなアマチュアプログラマーには Haskell は非常に魅力的な言語です。

Project Euler : Problem 20 ~ 整数 ⇌ リスト

 問題はこちらをご覧ください。

 

 この問題は、実際に "100!" を求めて、その答えを各桁にばらしてリストに収めた後に、その合計を求めるという方針で解くことにしました。
 そこで、整数をリストに変形する関数とリストを整数に変形する関数を考えました。

 

import Data.Char -- 整数をリストに変換 (十進法限定) -- ex : dexToList 123 => [1,2,3] dexToList :: Integral a => a -> [Int] dexToList = (map digitToInt) . show -- リストを整数に変換 (十進法限定) -- ex : listToDex [1,2,3] => 123 listToDex :: Integral a => [Int] -> a listToDex = fromIntegral . read . (map intToDigit)
 こちらは「十進法限定」ですが、非常にシンプルな関数になりました。

 

-- 整数をリストに変換 -- ex : intToList 10 123 => [1,2,3] -- ex : intToList 2 123 => [1,1,1,1,0,1,1] intToList :: Integral a => a -> a -> [Int] intToList radix n = map fromIntegral $ iter n [] where iter n prd | n < radix = n : prd | otherwise = iter q (r : prd) where (q, r) = quotRem n radix -- リストを整数に変換 -- ex : listToInt 10 [1,2,3] => 123 -- ex : listToInt 2 [1,1,1,1,0,1,1] => 123 listToInt :: Integral a => Int -> [Int] -> a listToInt radix ns = fromIntegral $ foldl calc 0 ns where calc x y = x * radix + y
 こちらは基数を指定して変換することができます。

 

 では実際のコードですが、今回はシンプルな関数の方を使うことにしました。

import Data.Char(digitToInt) dexToList :: Integral a => a -> [Int] dexToList = (map digitToInt) . show problem20 :: Int problem20 = sum $ dexToList $ product [2 .. 100] -- problem20 = (sum . dexToList . product) [2 .. 100] main = print problem20

2010年4月20日 (火)

Project Euler : Problem 19

 問題はこちらをご覧ください。

 

 地道に計算するのが嫌だったのでネットで調べていたら、日付から曜日を算出する「Zeller の公式」というものを見つけました。
 いくつかのバリエーションがあるようだったので Haskell のコードに落としやすそうなものを一つ選んで、関数を作ってみました。

-- Zeller の公式(の変形 ?) -- 0 : Sun, 1 : Mon, 2 : Tue .. zeller :: Int -> Int -> Int -> Int zeller y m d | m < 3 = zeller (y - 1) (m + 12) d | otherwise = rem (y + a - b + c + d + e) 7 where [a, b, c] = map (div y) [4, 100, 400] e = div (13 * m + 8) 5 problem019 :: Int problem019 = length [(y, m) | y <- [1901 .. 2000], m <- [1 .. 12], zeller y m 1 == 0] main = print problem019

 さらに調べたところ、Haskell には "Data.Time.Calendar", "Data.Time.Calendar.WeekDate" などという便利なライブラリがありました。(ただし、私の環境 (Ubuntu 9.10) では別途インストールする必要がありました)

import Data.Time.Calendar import Data.Time.Calendar.WeekDate problem019 :: Int problem019 = length sundays where years = [1901 .. 2000] days = [fromGregorian y m 1 | y <- years, m <- [1 .. 12]] sundays = [d | d <- days, let (_, _, w) = toWeekDate d, w == 7] main = print problem019

2010年4月 5日 (月)

Project Euler : Problem 18

 問題はこちらをご覧ください。

 

 今回も、前回 Ruby で解いた時と同じ方針で、下から上に数字をたどって行きました。

nss :: [[Int]] nss = [[75], [95, 64], [17, 47, 82], [18, 35, 87, 10], [20, 04, 82, 47, 65], [19, 01, 23, 75, 03, 34], [88, 02, 77, 73, 07, 63, 67], [99, 65, 04, 28, 06, 16, 70, 92], [41, 41, 26, 56, 83, 40, 80, 70, 33], [41, 48, 72, 33, 47, 32, 37, 16, 94, 29], [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14], [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57], [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48], [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31], [04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23]] problem018 :: Int problem018 = head $ foldr1 plusMax nss where selectMax ns = zipWith max ns (tail ns) plusMax ns1 ns2 = zipWith (+) ns1 (selectMax ns2) main = print problem018

 いろいろ推敲してがんばった結果、かなりシンプルなコードになりました。
 こういった簡潔なコードにまとまるのは Haskell のすごいところかな?でも、Haskell の文法をよく知らない人には、「なんのこっちゃ?」でしょうね。

2010年4月 3日 (土)

Project Euler : Problem 17

 問題はこちらをご覧ください。

 

 以前、「Ruby」で解いたときと同じ方針で、数字の読みを文字列で返す関数を作ってみました。

import Maybe (fromMaybe) nums1, nums2 :: [(Int, String)] nums1 = zip [0 .. 19] ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"] nums2 = zip [2 .. 9] ["twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"] numToStr :: Int -> String numToStr n | n == 1000 = "one thousand" | n >= 100 = let (q, r) = quotRem n 100 in toStr q nums1 ++ " hundred" ++ lower r " and " | n >= 20 = let (q, r) = quotRem n 10 in toStr q nums2 ++ lower r "-" | otherwise = toStr n nums1 where toStr n assocs = fromMaybe "" (lookup n assocs) lower r a = if lower' == "" then "" else a ++ lower' where lower' = numToStr r problem017 :: Int problem017 = length chars where chars = foldr remove (concat nums) [' ', '-'] nums = map numToStr [1 .. 1000] remove x ys = [y | y <- ys, y /= x] main = print problem017

« 2010年3月 | トップページ | 2010年5月 »

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            
フォト

最近のトラックバック

無料ブログはココログ