[Caml-list] Accessing the nth element in a stream takes time quadratic in n

[Caml-list] Accessing the nth element in a stream takes time quadratic in n

[DURAK Berke]

This happens when streams are defined recursively, as in

let rec nat_stream n = [< 'n; nat_stream (n + 1) >]

and the problem holds for streams built of channels or strings, too.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] Accessing the nth element in a stream takes time quadratic in n

[Daniel de Rauglaudre]

Hi,

On Mon, Mar 05, 2001 at 11:50:55PM +0100, DURAK Berke wrote:

> This happens when streams are defined recursively, as in
> 
> let rec nat_stream n = [< 'n; nat_stream (n + 1) >]
> 
> and the problem holds for streams built of channels or strings, too.

Preprocess by camlp4o (add "-pp camlp4o" among the options of ocamlc or
ocamlopt). The streams and stream parsers in OCaml parser are not
optimized.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] Accessing the nth element in a stream takes time quadratic in n

[kahl]

Daniel de Rauglaudre <daniel.de_rauglaudre@inria.fr> wrote:

 > The streams and stream parsers in OCaml parser are not optimized.

I am surprised!

So that's why they allow you only
to go faster than nsgmls (C++),
but not faster than sgmls (C)!   ;-)

(I must admit that I usually have ``-inline 25'',
 and that the .o/.ml length ratio is unusually high
 for the stream parser module.

 The experimemnt was, in addition, with a not fully validating parser,
 and without part of the entity replacement complexities of SGML.
)

So I still am inclined to consider stream parsers as a fast
and useful alternative.
(But then I haven't tried to define streams recursively...)

The ocamllex/ocamlyacc implemented XML parser ``tony''
posted here quite a while ago could not compare, neither speed-wise,
nor in the size of files it could digest.
(I have never seen an update announcement of tony --- maybe I missed it.)


Wolfram Kahl
kahl@ist.unibw-muenchen.de
http://ist.unibw-muenchen.de/kahl/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr