« Project Euler --- Problem 9 | トップページ | Subversion : memo »

2009年1月22日 (木)

ジレンマ

またしても Scheme のネタです。

実は、最近ある種のジレンマに陥っています。

以前ブログに書いたように、Scheme のプログラミングでは、map や filter を使ってリストの中のデータを加工していくのがかっこいいスタイルではないかと思っています。ところが、このスタイルは結構遅いことが多いんです。

例えば、素因数分解をするスクリプトの場合。

とあるブログで見つけたスクリプトをちょっとだけ改変したのがこれです。

(define factorize (lambda (n) (let ([f-lst (filter (lambda (x) (and (<= x n) (zero? (modulo n x)))) (prime-list n))]) (map (lambda (x) (cons x (let loop ([n n] [c 0]) (if [not (zero? (modulo n x))] c (loop (quotient n x) (+ c 1)))))) f-lst))))

ちなみに、 prime-list は以前このグロブに私が書いた関数です。

map や filter をうまく使っていて、私の感覚からすると「かっこいい」のですが、私が書いた手続きを並べて作った関数と比べると、約 10 倍位時間がかかります。( 3 ~ 1000 までの数を順に素因数分解して約 200 ms なので遅いとは言えないかもしれませんが……) 原因は、f-lst を求める際にかなり無駄な計算をしているためだと思われます。

例えば、 1000 を因数分解する際、素因数の 2 と 5 を見つけるのに 1000 回割り算をすることになります。

1 回だけしか使わないような関数であれば、「少々遅くてもかっこいい方がいいのかな?」とも思いますが、Project Euler の問題を解くときなど、素因数分解を繰り返し、大量に使用する可能性があります。そうするとやっぱり速い方がいいような気もするし……。

どこにかっこよさを感じるかは人それぞれでしょうが、私の場合、かっこよさとスピードはなかなか両立しそうにないので、しばらくはジレンマが続きそうです。

ちなみに、現在、私が使っている素因数分解を求める関数はこれです。

(define factorize (lambda (n) (define result '()) (define factor-count (lambda (n i) (let loop ([n n] [c 0]) (if [zero? (remainder n i)] (loop (/ n i) (+ c 1)) (begin (if [> c 0] (set! result (cons (cons i c) result))) n))))) (let loop ([n (factor-count n 2)] [i 3]) (cond ([= n 1] (reverse result)) ([> (* i i) n] (reverse (cons (cons n 1) result))) (else (loop (factor-count n i) (+ i 2)))))))

« Project Euler --- Problem 9 | トップページ | Subversion : memo »

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: ジレンマ:

« Project Euler --- Problem 9 | トップページ | Subversion : memo »

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

最近のトラックバック

無料ブログはココログ