最近のキーワード

2006年07月16日

キミならどう書く 2.0 - ROUND 2 - 「collatz問題」(第1回)

http://ll.jus.or.jp/2006/blog/doukaku2
まぁなぜか関数型言語に触れられているので、ひとまず、gをCPS変換して末尾再帰にすることで実装することを考える。実装言語はML。実際に使った処理系はSML.NET
(7/17追記) closureを作らずに末尾再帰にしてみた。あとInt64を使うようにした。
structure Collatz :>
sig
  val main : unit -> unit
end
=
struct

open Int64

fun f(1) = 1
  | f(n) = if Int64.rem(n,2)=0 then Int64.div(n,2) else 3*n+1

(*
fun g(1) = 1
  | g(n) = 1 + g(f(n))
*)

(* CPS変換したもの *)
(*
fun g(n) = let
  fun g'(1,cont) = cont(1)
    | g'(n,cont) = g'(f(n), fn n => 1+cont(n))
in
  g'(n, fn n => n)
end
*)

(* CPS変換後、closure使うのやめたもの *)
fun g(n) = let
  fun g'(1,cont) = cont
    | g'(n,cont) = g'(f(n), 1+cont)
in
  g'(n, 1)
end

fun h(n) = let
  fun h'(1,m,xs) = (1,m,xs)
    | h'(n,m,xs) = let
        val gn = g(n)
      in
        if gn = m then
          h'(n-1,m,n::xs)
        else
          if gn > m then
            h'(n-1,gn,[n])
          else
            h'(n-1,m,xs)
      end
in
  h'(n,1,[1])
end

fun main() = let
  fun listToString xs =
      "[" ^ (foldl (fn (x,y) => ((Int64.toString x) ^ ", " ^ y)) "" xs) ^ "]"
  fun printResult n (m,maxStep,result) =
      (print("h(" ^ (Int.toString n) ^ "):\n");
       print("  maxStep = " ^ (Int64.toString maxStep) ^ "\n");
       print("  result  = " ^ (listToString result) ^ "\n"))
in
  printResult 20 (h 20);
  printResult 100 (h 100);
  printResult 100000 (h 100000);
  printResult 1000000 (h 1000000);
  ()
end

end
113383は大きなステップ数になるようだ。100000までは1,2秒程度。コンパイラが頑張っているようだ。結果は以下の通りで、h(100000)までは求めてみた。 どうやらInt32の範囲を超えてしまっていたらしい。そこでInt64を使うようにしてみた。
~$ time ./Collatz.exe
h(20):
  maxStep = 21
  result  = [19, 18, ]
h(100):
  maxStep = 119
  result  = [97, ]
h(100000):
  maxStep = 351
  result  = [77031, ]
h(1000000):
  maxStep = 525
  result  = [837799, ]

real    0m21.170s
user    0m0.015s
sys     0m0.078s

CPS変換について、調べればあちこちに書いていることではあるが、例えば、g'(4, fn n => n)のときの呼び出し系列を以下の通り。ここで、fn n => expr という式は無名関数λn . expr のMLの表現方法だと思えばよい。
g'(4, fn n => n)
= g'(f(4), λn . 1 + (λn . n)(n)) = g'(2, λn . 1 + (λn . n)(n))
= g'(f(2), λn . 1 + (λn . 1 + (λn . n)(n))(n)) = g'(1, λn . 1 + (λn . 1 + (λn . n)(n))(n))
= (λn . 1 + (λn . 1 + (λn . n)(n))(n))(1)
= 1 + (λn . 1 + (λn . n)(n))(1)
= 1 + 1 + (λn . n)(1)
= 1 + 1 + 1
ようするに、g'(n,cont)が行っていることは、計算(1の加算)を行うための無名関数をfの適用でnが1になるまで次々と連鎖させていると思えば良い。そして、nが1になったときに、構成した無名関数を次々と計算する。
また、この方法によって、g'を末尾再帰の形で定義できるようになる。末尾再帰の良い点は、コンパイラによっては、これをループのように扱ってコンパイルすること。そうすると、スタックが足りないという問題は起きない。
posted by ttate at 05:33| ☁| Comment(0) | TrackBack(0) | プログラム言語 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。