From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id 1776C7ED46 for ; Sun, 24 Jun 2012 20:59:52 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AooBAGdj50/RVda2kGdsb2JhbABEpSmQSwgiAQEBAQkJDQcUBCOCGAEBAQQSAhMZARsSCwEDDAYFCw0NISEBAREBBQEKEgYTEgkBBgyHTgEDCwuaIwkDjCOCcYN6ChknAwpXiHEBBQyKRGMVhW0DJgKVBoESiBSBXIMiPoQAgVUKCA X-IronPort-AV: E=Sophos;i="4.77,467,1336341600"; d="scan'208";a="164219120" Received: from mail-ob0-f182.google.com ([209.85.214.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 24 Jun 2012 20:59:51 +0200 Received: by obbun3 with SMTP id un3so9491754obb.27 for ; Sun, 24 Jun 2012 11:59:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=ffGaPGgkvhrGHnbI2YULq1+3BETjxQbOiIV6j+l2K8I=; b=EjIDDhiIz+GeCboiQ80gqMzghPcQp68gnvo9IcdIrdsP8QVwQyeSBMmd7WLv2X77Hv /uSwvJLs4uHJN9qKOvVdCqRmPiwepAqG0Pr3U0mBciLIXsMOuurYV8KgQJZmhG3hd6vB a7OgWnTQAJE33e6IvsStyiuc+GjXxNf3AHNeBdMBtle68rtf68rV3RiwNQqXjoDgJMs+ fB+NsB8qP1P7PbFGdqsMdUnP+a9rome8h9rX3AFXkAnuFekuwf6jnMjOWadZviZ8z8/o W1+X4T0DeiMljT7qJbwpD0GpbwDc4Vtz+PQE4kI9sKuq61XsnnFzMzgmZxpintnziY6r 8FPQ== Received: by 10.50.104.228 with SMTP id gh4mr6282621igb.71.1340564389988; Sun, 24 Jun 2012 11:59:49 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.94.39 with HTTP; Sun, 24 Jun 2012 11:59:09 -0700 (PDT) In-Reply-To: References: From: Gabriel Scherer Date: Sun, 24 Jun 2012 20:59:09 +0200 Message-ID: To: Diego Olivier Fernandez Pons Cc: caml-list Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] print_int is too slow 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 wrote: > =A0 =A0Team, > > 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 () =3D Scanf.scanf " %c " (fun i -> i) in > let read_int () =3D Scanf.scanf " %i " (fun i -> i) in > > let > =A0 length =3D ref 0 and > =A0 max_queue =3D ref min_int > in > > let rec push v =3D function > =A0 | [] -> [v] > =A0 | x :: tail when x <=3D v -> decr length; push v tail (* drop x *) > =A0 | queue -> v :: queue > in > > let insert v =3D function > =A0 | [] | _ when v >=3D !max_queue -> > =A0 =A0 =A0max_queue :=3D v; > =A0 =A0 =A0length :=3D 1; > =A0 =A0 =A0[v] > =A0 | (x :: _) as queue when v =3D x -> queue > =A0 | (x :: _) as queue when v < x -> > =A0 =A0 =A0incr length; > =A0 =A0 =A0v :: queue > =A0 | queue -> > =A0 =A0 =A0incr length; > =A0 =A0 =A0push v queue > in > > let visible =3D ref [] in > > let n =3D read_int() in > for i =3D 1 to n do > =A0 match read_char () with > =A0 =A0 =A0| 'Q' -> Printf.printf "%i\n" !length > =A0 =A0 =A0| 'C' -> visible :=3D insert (read_int()) !visible > =A0 =A0 =A0| _ -> failwith "unknown instruction code" > done > > If you replace printf by print_int !length; print_newline () the code > is more than 4 times slower. > > =A0 =A0 =A0 =A0Diego Olivier > > -- > Caml-list mailing list. =A0Subscription 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 >