DouKaku? 4512 xsd: □の代わりに'O'にしてます。 P...(自然数の分割（別表現）)

Comment detail

□の代わりに'O'にしてます。

Pentium M 1.73MHz, Fedora 7という環境で/dev/nullへのリダイレクトで0.681秒、ファイルへのリダイレクトで0.726秒です。

[xsd@celldev dk96]$ time ./dk96 50 > /dev/null

real    0m0.681s
user    0m0.679s
sys     0m0.001s

[xsd@celldev dk96]$ time ./dk96 50 > out.txt

real    0m0.726s
user    0m0.691s
sys     0m0.036s

ちなみに、n=80のときで69秒でした。

[yamaken@celldev dk96]$ time ./dk96 80 > /dev/null

real    1m9.190s
user    1m9.100s
sys     0m0.077s

let young n =
  let makeO x acc = ((String.make x 'O') ^ "\n") :: acc in
  let rec out = function [] -> print_char '\n' | hd :: tl -> let _ = out tl in print_string hd in
  let rec loop r c acc =
    if c <> 0 then match r - c with
      | 0            -> let _ = out      (makeO c acc) in loop r (c-1) acc
      | x when x > 0 -> let _ = loop x c (makeO c acc) in loop r (c-1) acc
      | _            -> loop r r acc in
    loop n n []

let _ = young (int_of_string Sys.argv.(1))

＞Pentium M 1.73MHz

すいません。Pentium M 1.73GHzの間違いでした。

これも
> - 分割は長さが短いものが先
を満たしていないような。

ただ、それにしてもこの速さ(I/O性能)はたいしたものだと思います。I/O性能として比べるなら"□"を使う場合とデータ量を合わせるべきでしょうが、それにしても。ocamlのランタイムは、バッファリングI/Oなどは独自実装なのでしょうか。

>これも 
>> - 分割は長さが短いものが先 
>を満たしていないような。 

ご指摘ありがとうございます。
要件を満たし、出力も'□'としするように修正しました。(ただしutf-8固定)
あわせて、無駄ヅモを無くすように(行き止まりの経路を選ばないように)したところ、前よりも速くなりました。
ファイル出力時で0.554sです (PentiumM 1.73GHz, Fedora7)

[xsd@celldev dk96-2]$ time ./dk96-2 50 > /dev/null

real    0m0.486s
user    0m0.482s
sys     0m0.004s
[xsd@celldev dk96-2]$ time ./dk96-2 50 > out.txt

real    0m0.554s
user    0m0.475s
sys     0m0.079s
[xsd@celldev dk96-2]$ ls -l out.txt
-rw-rw-r-- 1 xsd     xsd     33643344 Dec  2 18:34 out.txt

OCamlのI/Oが速いのは、内部でcharをUnicodeで持っていたりしないので、変換コストがかからないことと、
flushしていないのが効いているのかもしれません。

let initbuf maxn =
  let subblock subn =
    let block    = "\xe2\x96\xa1" in (* hard-encoded in utf-8 *)
    let len      = String.length block in
    let maxblock =
      let rec addbuf buf n =
        if n = 0 then buf ^ "\n" else addbuf (buf ^ block) (n-1) in
      addbuf "" maxn in
    String.sub maxblock (len * (maxn - subn)) (len * subn + 1) in
  Array.init maxn subblock

let rec out = function
  | []       -> print_string "\n"
  | hd :: tl -> let _ = out tl in print_string hd

let young n =
  let arr = initbuf (n+1) in
  let rec loop' n r c acc =
    if c <> 0 && n * c >= r then (
      if n = 1 then (
        if r <= c then out (arr.(r) :: acc)
      ) else (
        let x = r - c in
        let _ = if x > 0 then loop' (n-1) x (min c (x-n+2)) (arr.(c) :: acc) in
                loop' n r (c-1) acc
      )
    ) in
  let rec loop n r =
    if n <= r then let _ = loop' n r (r-n+1) [] in loop (n+1) r in
  loop 1 n

let _ = young (int_of_string Sys.argv.(1))

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq