Re: [Caml-list] Constant-time function

[Anton Bachin <antronbachin@gmail.com>]

1. You are computing the length of l1 and l2 every iteration. On the first iteration, it is the lengths of the original lists. On the second iteration, it is the lengths of their tails. This function takes time quadratic in the maximum of (length l1, length l2), as written. List.length itself takes linear time.

2. If h1 and h2 are nontrivial types, structural equality may take a nontrivial amount of time to compute.

> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
> 
> Dear all,
> 
> I have write a simple function to compare two lists as below:
> 
> let rec lcomp l1 l2 = 
>  if (List.length l1 != List.length l2) 
>  then false
>  else match l1, l2 with 
>  | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
>  | _, _ -> true;;
> 
> In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
> + with only 10th element is different: it takes 0.000027s
> + with only 90th element is different: it takes 0.000116s
> 
> You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?
> 
> Thanks,
> Chan
> 
> 
>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
>> 
>> Hello,
>> 
>> I released bigstring.0.1 yesterday, a small module for dealing with
>> bigarrays of chars. It used to be part of containers, but is useful on
>> its own for low level IO, mirage, etc.; hence the split.  The license is
>> BSD-2-clauses.
>> 
>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
>> and contributions and criticism are welcome.
>> 
>> Cheers,
>> 
>> -- 
>> Simon Cruanes
>> 
>> http://weusepgp.info/
>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6
> 
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs