Re: [Caml-list] print_int is too slow

[Gabriel Scherer <gabriel.scherer@gmail.com>]

I have no time for empirical checks right now, but is the problem
really with print_int, or does replacing (print_newline ()) by
(print_string "\n") similarly improves performances? That may very
well be related to when buffering happens.

On Sun, Jun 24, 2012 at 8:40 PM, Diego Olivier Fernandez Pons
<dofp.ocaml@gmail.com> wrote:
>    Team,
>
> I was double checking some OCaml exercises in the France IOI website
> (training for the international Olympiads of informatics
> http://www.france-ioi.org/)
>
> There is an exercise where my OCaml solution was breaking the time
> limit without reason
> The issue ended being because print_int seems to be much much slower
> than Printf.printf (> 2s for print_int, 0.25s for printf)
>
> The exercise is as follows
> A sequence of posters of different lengths L_k are pasted one over the
> other (one dimension problem, all starting at the same zero point,
> same width, same orientation)
> After some time, the program is asked to tell how many posters are still visible
>
> Inputs
> - "C %i" means a poster of length x was pasted
> - "Q" queries the program for the number of visible posters
> Outputs
> - number of visible posters after each query
>
> example
>
> input:
> 12 [number of lines in input]
> C 2
> Q
> C 4
> C 2
> Q
> C 9
> Q
> C 9
> C 2
> Q
> C 8
> Q
>
> output :
> 1
> 2
> 1
> 2
> 2
>
> Here is my code
>
> let read_char () = Scanf.scanf " %c " (fun i -> i) in
> let read_int () = Scanf.scanf " %i " (fun i -> i) in
>
> let
>   length = ref 0 and
>   max_queue = ref min_int
> in
>
> let rec push v = function
>   | [] -> [v]
>   | x :: tail when x <= v -> decr length; push v tail (* drop x *)
>   | queue -> v :: queue
> in
>
> let insert v = function
>   | [] | _ when v >= !max_queue ->
>      max_queue := v;
>      length := 1;
>      [v]
>   | (x :: _) as queue when v = x -> queue
>   | (x :: _) as queue when v < x ->
>      incr length;
>      v :: queue
>   | queue ->
>      incr length;
>      push v queue
> in
>
> let visible = ref [] in
>
> let n = read_int() in
> for i = 1 to n do
>   match read_char () with
>      | 'Q' -> Printf.printf "%i\n" !length
>      | 'C' -> visible := insert (read_int()) !visible
>      | _ -> failwith "unknown instruction code"
> done
>
> If you replace printf by print_int !length; print_newline () the code
> is more than 4 times slower.
>
>        Diego Olivier
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>