« Project Euler --- Problem 27 | トップページ | Project Euler --- Problem 27 再び »

2009年3月14日 (土)

アルゴリズムの重要性 Project Euler --- Problem 36

Project Euler の問題を解いていると、やっぱり他の人の解き方も見てみたくなりますよね。

そこでネット上にある解答例を探したりするのですが、最近、ちょっと気になることがあります。「取り合えず答えが出ればいい」といった雰囲気のコードが多いのです。

Project Euler に対するスタンスにはいろいろあると思います。

「なるだけ速く、多くの問題を解きたい」というのであれば、アルゴリズムを吟味する意味はあまりないのかもしれません。でも、プログラミングの勉強のために Project Euler の問題を解いているのなら、もう少しアルゴリズムに気を配るべきではないでしょうか?

ひとつの問題を解くためのアルゴリズムはいくつもあります。

中には膨大な計算量が必要となり、メモリや CPU の無駄使いをするものもあるかもしれません。しかし、ちょっと工夫をしたり、アルゴリズムを見直すと、驚くほど計算量を減らせることがあります。

例えば、Problem 36 を考えてみます。

「100 万未満で 10 進でも 2 進でも回文数になるような数の総和を求めよ。」という問題でした。

まず考えつくのが、1 から 999999 までの総ての数に対して条件にあるものを探して行くという方法だと思います。(今回のコードには「リスト内包表記」が含まれています。詳しくは、以前の記事を読んでください)

(define integer->list (lambda (n . radix) (let ([r (if [null? radix] 10 (car radix))]) (do ([n n (quotient n r)] [result '() (cons (remainder n r) result)]) ([< n r] (cons n result)))))) (define palindromic-list? (lambda (lst) (equal? lst (reverse lst)))) (define problem-036 (lambda () (let ([lst (set-of a (a in (cdr (iota 999999))) (odd? a) (palindromic-list? (integer->list a)) (palindromic-list? (integer->list a 2)))]) (printf "~d~%" (apply + lst))))) (time (problem-036))

探す範囲が広いのでかなり時間がかかります。私のパソコンでは "1558 ms elapsed cpu time" と表示されました。

ここでちょっと考え方を変えてみます。まず 10 進法で回文数を作っておいて、その数が 2 進法で回分数になるかを調べてみます。

(define make-palindromic-number (lambda (n . flag) (let* ([a (integer->list n)] [b (reverse a)]) (list->integer (append a (if [null? flag] (cdr b) b)))))) (define problem-036 (lambda () (let* ([base-lst (cdr (iota 999))] [lst-odd (set-of a (b in base-lst) (a is (make-palindromic-number b)) (odd? a) (palindromic-list? (integer->list a 2)))] [lst-even (set-of a (b in base-lst) (a is (make-palindromic-number b #t)) (odd? a) (palindromic-list? (integer->list a 2)))]) (apply + (append lst-odd lst-even))))) (time (problem-036))

この方法では "29 ms elapsed cpu time" となりました。速さにして、約 50 倍です。速さが総てとはいいませんが、アルゴリズムを見直すだけで、こんなに変わってくるものなのです。

使い捨てのスクリプトを作るのなら、あれこれアルゴリズムを吟味する前に、思いつくままにコードを書くほうが結果的に速いかもしれません。しかし、長い間使われ続けるプログラムを作る場合はアルゴリズムを十分吟味するべきだと思います。

最近のソフトは CPU の性能やメモリの量をかなり要求しているものがありますが、しっかりとしたアルゴリズムの検討がなされているのか疑問に思うことがあります。

私はアルゴリズムを考えるのが好きなので、一度解いた問題も、「もっといい方法があるのでは?」と見直し、考え直すことが多いので、なかなか先に進めません。

« Project Euler --- Problem 27 | トップページ | Project Euler --- Problem 27 再び »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

日記・コラム・つぶやき」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/44343091

この記事へのトラックバック一覧です: アルゴリズムの重要性 Project Euler --- Problem 36:

« Project Euler --- Problem 27 | トップページ | Project Euler --- Problem 27 再び »

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

最近のトラックバック

無料ブログはココログ