From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <dofp.ocaml@gmail.com>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by sympa.inria.fr (Postfix) with ESMTPS id 7451E7ED45
	for <caml-list@sympa.inria.fr>; Sun, 24 Jun 2012 20:40:18 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AocBAGte509KfVK2kGdsb2JhbABEtXQIIgEBAQEJCQ0HFAQjgjECExkBGx4DEhBdAREBBQEiLgEGh1oBAwuXT4JhCQOMI4Jxg3wKGScNV4hxAQUMizyFbQMmApUGiSaEfj6EAIFVEg
X-IronPort-AV: E=Sophos;i="4.77,467,1336341600"; 
   d="scan'208";a="148591284"
Received: from mail-we0-f182.google.com ([74.125.82.182])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 24 Jun 2012 20:40:17 +0200
Received: by werg1 with SMTP id g1so3609566wer.27
        for <caml-list@inria.fr>; Sun, 24 Jun 2012 11:40:17 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:date:message-id:subject:from:to:content-type;
        bh=JWhfW8DMnshAcyPjsWLuDNmbdsiOFqMypNMDVoC0q4I=;
        b=y4I9m1iXtwmRBX/eYf5UoTDwqhTvOKg6W17u0iByshsn4+vkZKU+1Sli0Uk9Rrkg2h
         EFutaGxiWfGV+TDfveFzU9CJoORjHvFoWq4R+kcoprZt4dhB2BRX7aZcTI1cezQinjU1
         tUzNnrCKzRNnm9ZVy+BWb5uD3pLEAvE980oAjxQYaZ8/ssk3B5d391J8ti6raf90wZbk
         jcfae62iadd0OxSMmkIBhbnl2vu3Hx9o540FGYmffJ7wuRYKDM719F20YnupStxcRgp1
         ww+0ocMNuCQtI5GK2dnAjRp5lBwemKsfq+5BxHiPxs5/P68/YswnyHNY6rHXA3Cje//q
         hr4g==
MIME-Version: 1.0
Received: by 10.216.150.166 with SMTP id z38mr4902582wej.78.1340563217572;
 Sun, 24 Jun 2012 11:40:17 -0700 (PDT)
Received: by 10.217.1.8 with HTTP; Sun, 24 Jun 2012 11:40:17 -0700 (PDT)
Date: Sun, 24 Jun 2012 20:40:17 +0200
Message-ID: <CAHqiZ-+6DPuutYdT0dtPZWLR_ePwdjE_UaE0Jzh_WhBDOHb+0w@mail.gmail.com>
From: Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com>
To: caml-list <caml-list@inria.fr>
Content-Type: text/plain; charset=ISO-8859-1
Subject: [Caml-list] print_int is too slow

    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