DouKaku? 4551 xsd: >これも >> -...(自然数の分割（別表現）)

Comment detail

This comment is reply for 4534 shiro: これも > - 分割は長さが短い...(自然数の分割（別表現）). Go to thread root.

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

ご指摘ありがとうございます。
要件を満たし、出力も'□'としするように修正しました。(ただし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