« 2008年12月 | トップページ | 2009年2月 »

2009年1月

2009年1月28日 (水)

Subversion : memo

私は Subversion を使用しています。家のパソコンと職場のパソコンの同期も兼ねて、リポジトリを USB メモリに入れています。

今日、コミットしようとしたら "svn failed: Can't read file '/media/disk/svn-repos/db/txn-current': End of file found" というエラーが出て受け付けてくれませんでした。USB メモリを抜き差しするときにやらかしたようです。

svnadmin recover しても効果なし。 svnadmin verify しても異常なし。でも受け付けてくれない……。

あきらめて、以前とっておいたバックアップからデータベースを再構築しようかとも思いましたが、ダメもとで試した方法がうまくいったので、忘れないようにここに書いておきます。

  1. いつもの様に、ダンプファイルを抽出してバックアップをとる。→ svnadmin dump
  2. 前のリポジトリと同じ名前で空のリポジトリをつくる。→ svnadmin create
  3. 新しいリポジトリにバックアップしてあったデータをリストアする。→ svnadmin load

以上のやり方で、リポジトリが復活しました。問題なくコミットもできたので、大丈夫だと思います。

何はともあれ、よかった。

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)))))))

2009年1月17日 (土)

Project Euler --- Problem 9

今日は時間があるので、「Project Euler」ネタをもう一つ。

Problem 9 は「a + b + c = 1000 となるピタゴラスの三つ組を見つけて a, b, c の積を計算しなさい」という問題でした。

いろいろな解き方があると思いますが、自分が考えた方法のうち、最速なものを紹介します。


a² + b² = c² ...(1)
a + b + c = n ...(2)

とすると、(2) を変形して

c = n - (a + b) ...(3)

が導かれます。これを (1) に代入してさらに変形すると、

b = (n² - 2 * a * n) / (2 * (n - a))
  = n - n² / (2 * (n - a)) ...(4)

実際に (4) を計算して、b が整数になれば、それが答えになります。

(define pythagorean-triples
  (lambda (n)
    (if (odd? n)
        '()
        (let loop ([a 1][result '()])
          (let ([b (- n (/ (* n n) (- n a) 2))])
            (cond
              ([> a b] (reverse result))
              ([integer? b]
               (loop (+ a ) (cons (list a b (- n a b)) result)))
              (else (loop (+ a 1) result))))))))

  

(define problem-009
  (lambda (n)
    (printf "~d~%"
      (apply * (car (pythagorean-triples n))))))

  

(problem-009 1000)

Project Euler --- Problem 2

またしても、「Project Euler」ネタです。

Problem 2 は「フィボナッチ数列の項が 400 万を超えない範囲で、偶数の項の総和を求めよ」という問題でした。

フィボナッチ数列を再帰的に求めようとすと無駄な計算が多くなるので、反復的に求めます。

Scheme は、データを一度リストの形にしてしまえば、後の加工が非常に簡単になります。

(define problem-002
  (lambda (n)

 

    (define fib-list
      (lambda ()
        (let loop ([a 1] [b 1] [result '()])
          (if (>= a n)
              result
              (loop (+ a b) a (cons a result))))))

 

    (printf "~d~%" (apply + (filter even? (fib-list))))))

 

(problem-002 4000000)

2009年1月 9日 (金)

Project Euler --- Problem 5

Problem 5 は「 1 から 20 までの整数全てで割り切れる数字の中で最小の値を求める」というものでした。

これは、「 1 から 20 までの全ての整数の最小公倍数を求める」ということになります。

Scheme には最小公倍数を求める lcm という手続きがあるので、

 (apply lcm (cdr (iota (+ 20 1))))

とすれば、一発で答えが出ます。

二つの整数 a, b の最大公約数を GCM(a, b), 最小公倍数を LCM(a, b) とすると、

  LCM(a, b) = a * b / GCM(a, b)

となるので、最小公倍数を求める手続きのないプログラム言語でも、ユークリッドの互除法を使って二つの整数の最大公約数を見つける手続きを自分で作ってしまえば、あとは、 1 から 20 までの数の最小公倍数を順に探していけばいいはずです。

2009年1月 8日 (木)

Turtle Graphics on Ruby/SDL ver.2.0

Sample_8

 

約一年半前にリリースした「Turtle Graphics on Ruby/SDL」をバージョンアップしました。

前回リリースした後も、自分で使いやすいように手を加えていった結果、メソッドの挙動やメソッド名がかなり変わってしまいました。以前のバージョンとは互換性はありません(以前のバージョンを使い込んでいた人がいたらごめんなさい)。

今回の変更で見てもらいたいのは、Screen#main_loop メソッドと Graph クラスです。

Screen#main_loop 実行中にマウスで拡大させたい領域を選択できるようになりました。 loop や while などのループ内に Screen#main_loop を含む処理を書いておくと、画面の一部をどんどん拡大して表示していくことができます。 (sample/Turtle_Graphics/koch_curve.rb 参照)

Graph クラスでは、通常の y = f(x) といった形の関数の他に、媒介変数を用いた、 y = f(t), x = g(t) といった形の関数も表示できます。

タートル・グラフィックスに関心のある方、手軽に関数のグラフを可視化してみたい方は、ぜひ一度、このライブラリで遊んでみてください。

「Turtle_Graphics_2.0.zip」をダウンロード

« 2008年12月 | トップページ | 2009年2月 »

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

最近のトラックバック

無料ブログはココログ