« 2008年10月 | トップページ | 2009年1月 »

2008年12月

2008年12月16日 (火)

素数の和

Project Euler の Problem 10 は「200万以下の素数の和を求めよ」というものです。
Scheme で解くなら、昨日の記事に書いた prime-list が使えます。

(define problem-010
  (lambda (n)
    (printf "~d~%"
      (apply + (prime-list n)))))


> (time (problem-010 2000000))
142913828922
(time (problem-010 2000000))
    10 collections
    664 ms elapsed cpu time, including 167 ms collecting
    698 ms elapsed real time, including 173 ms collecting
    45340088 bytes allocated, including 45432536 bytes reclaimed

Chez Scheme はかなり高速だと思います。

私は Ruby も大好きです。Ruby で解くなら……

# problem_10.rb
def prime_list(n)
  return([]) if (n == 1)

  size = n / 2 - 1
  max  = Math::sqrt(n).to_i

  a = Array.new(size)
  size.times do |i|
    a[i] = 2 * i + 3
  end

  max.times do |i|
    j = a[i]
    next unless j
    ((j * j - 3) / 2).step(size, j) do |k|
      a[k] = nil
    end
  end

  return a.unshift(2).compact
end

sum = 0
prime_list(2000000).each do |i|
  sum = sum + i
end

puts sum


$ time ruby problem_10.rb
142913828922

real    0m4.512s
user    0m3.832s
sys    0m0.644s

4 秒ちょっとで解けました。まあ、Ruby に速度を求めているわけではないので、これで十分満足ですが……。

2008年12月15日 (月)

Project Euler --- 素数を扱う問題

Project Euler では素数を扱う問題もいくつかみられますが、私が使っている素数関連のスクリプトを紹介してみます。

Petite Chez Scheme を使用していますので、他の処理系を使っている人は、適宜修正をしてください。ちなみに '[...]' は '(...)'に置き換えてください。


まずは、素数の判定法から……

これはオーソドックスに「試し割法」です。(実際に自分が使用しているものは大きな整数にも対応できるように、「Miler-Rabin 法」を組み合わせています)

(define prime? (lambda (n) (cond ([< n 2] #f) ([= n 2] #t) ([even? n] #f) (else (let ([max (sqrt n)]) (let loop ([i 3]) (cond ([> i max] #t) ([zero? (remainder n i)] #f) (else (loop (+ i 2))))))))))

もし、「n 番目までの素数のリストを求める」のであれば……

(define p-list (lambda (n) (let loop ([i 2] [a 3] [result '(2)]) (cond ([> i n] (reverse result)) ([prime? a] (loop (+ i 1) (+ a 2) (cons a result))) (else (loop i (+ a 2) result))))))


次は「n 以下の素数のリストを求める」場合です。

"prime?" を使ってもいいのですが、「エラトステネスの篩」を使うとかなり高速になります。

私が使っているものは Ruby の sample に含まれている "sieve.rb" を改良したものです。

(define sequence (lambda (start end . step) (let* ([step (if [null? step] 1 (car step))] [size (+ 1 (quotient (- end start) step))]) (map (lambda (x) (+ (* x step) start)) (iota size))))) (define prime-list (lambda (n) (cond ([= n 1] '()) ([= n 2] '(2)) (else ;; エラトステネスの篩 (let* ([p-vct (list->vector (cons 0 (sequence 3 n 2)))] ;; p-vct = #(0 3 5 7 ...) [size (vector-length p-vct)] [max (sqrt n)]) (let loop1 ([i 0]) (let ([j (vector-ref p-vct i)]) (cond ([zero? j] (loop1 (+ i 1))) ([> j max] (cons 2 (remv 0 (vector->list p-vct)))) (else (let loop2 ([k (* 2 i (+ i 1))]) (if (>= k size) (loop1 (+ i 1)) (begin (vector-set! p-vct k 0) (loop2 (+ j k))))))))))))))

ちなみに、私のマシン (T1300, 1.66GHz) で実行すると

> (time (car (prime-list 10000)))
(time (car (prime-list 10000)))
    no collections
    3 ms elapsed cpu time
    3 ms elapsed real time
    154832 bytes allocated

という結果が出ました。結構速いと思いません?

2008年12月11日 (木)

プログラム言語について語るなら……

 先日、あるブログで「Ruby には goto 文がないので、大域脱出ができずに使いづらい」といった主旨の記事を見ました。→iSAMrx72's思いつきblog
 結論から言うと、Ruby では大域脱出をする場合には "goto" ではなく "catch and throw" を使うので、記事を書いた人が Ruby のことを良く分かっていなかっただけのことでした。

 

 この記事を読んで、いくつか思ったことがありました。

 まず一つは、プログラム言語を批判することについて。
 対象となるプログラム言語を使い込んで、本当に深いところまで知っている人がその言語を批判をしているのは少ない気がします。
 どちらかというと、今回のように本来その言語に標準で備わっている機能を知らずに、「あの機能がない、この関数がない」といった内容の批判が目につくように思います。

 また、自分の得意な言語(使っている言語)の常識を、批判対象となる言語に押し付けて批判をしてしている人も多いように思います。
 それぞれの言語にはそれぞれのプログラムスタイルがあります。その言語に合わないスタイルでプログラムを書けば、プログラムを書きづらいだろうし、速度も上がらないのは当然です。

 「言語には優劣はない。あるのは得意な分野と不得意な分野である」といった内容のことを言っていた人がいます。名言だと思います。
 その言語の不得意とする分野での性能が悪いといって批判するのはある意味卑怯だと思います。

 各言語の理論的な「比較」は、これからプログラム言語を学ぼうとする人にはとても有益だと思います。でも、感情的な「批判」は何の役にも立たちません。

 どのプログラム言語にも長所と短所があります。長所の部分が大好きで、短所の部分に目がつぶれるのであれば、その言語を使えばいいし、短所の部分がどうしても許せなければ、その言語にしがみつかずに、他の言語を使えばいいのではないのでしょうか?
 上司の命令で、自分の嫌いな言語をいやいや使わされている人以外は、嫌いな言語の批判をする暇があったら、自分の大好きな言語で自分や他の人に役に立つプログラムをガンガン作ってもらいたいものです。

 

 もうひとつ気になったのが、「なんで今さら "goto" なのか?」ということです。
 "goto" の乱用の反省から構造化プログラミングは生まれたはず。"goto" を使わなければ困るほど深いネストが出来上がった場合、アルゴリズム自体に問題がある場合がほとんどだと思います。

 私は、N88-BASIC、アセンブラ、C、Ruby、Scheme と使ってきましたが、BASIC とアセンブラはともかく、C や Ruby で "goto" や "catch and throw" を使った記憶がありません。
 私のような趣味でプログラミングをしている者が知らないだけで、もしかしたら業務用のプログラムを作るようなシビアな場面では "goto" はまだまだ必要なのでしょうか?

 別に 「"goto" が諸悪の根源で絶対使ってはいけない」なんてことは思ってもいませんが、"goto" を使いたくなったら、アルゴリズムを見直すべきじゃないでしょうか?

 

 最後にもう一つ。
 この記事を書くきっかけになったブログのコメント蘭に

変数を宣言しないで使うのは、どんなもんなんでしょうね。Rubyは。昔Basicは宣言無で使ってました。ただし、綴り間違いが多いので、Dimとかで宣言したのですが、Rubyも綴り間違いに悩まされるのでないでしょうかね。
というコメントがありました。

 これも、「Ruby のことが分かってないなー」って感じですね。
 そもそも Ruby は「動的言語」ですから、変数と型が無関係なのが「売り」なのです。(それゆえ、「ダックタイピング」なんかもできるわけで……)
 Ruby の場合、クラスの中に小さいメソッドを埋め込んでいくスタイルが主流なので、思い切り離れた場所で初期化した変数を使う場合はほとんどありません。
 多くの場合、エディタの一画面に収まる範囲でしか変数を使用しないので、変数の綴り間違いはあまりないと思います。
 だいたい、変数の綴り間違いは言語のせいではなく、間違いやすい変数名を付けたプログラマーのせいではないでしょうか?

 Ruby は最近注目されているせいか、Ruby 批判も多い気がします。ただし、そのほとんどは勘違いか言いがかりですけど……。
 それに比べて Scheme の場合はあんまり批判をされてませんね。あるのは Common Lisp ファンとの間の Lisp-1, Lisp-2 論争くらいか?さすがに C や Perl と Scheme を直接比べるのは無理がありますよね。(単にマイナーなだけか?)

« 2008年10月 | トップページ | 2009年1月 »

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

最近のトラックバック

無料ブログはココログ