Chan, I think you're confused because you expect that the function will visit each element of the lists (if they are the same size).
Compiler short circuits && operator so your loop runs only til the first element that differs. If you swap the arguments to && you should get the behavior of visiting all elements (which is of course undesirable in practice)
But the complexity of this function is not constant if you fix only the list length. It still varies quadratically in the location of the first pair of elements that are different, because the “outer iteration” is performed that many times, and the “inner" List.lengths visit at least that many elements each time, since this location (if it exists) is less than the list length. Hence, the behavior you are observing.
> On Feb 22, 2016, at 13:57, Chan Ngo <chan.ngo2203@gmail.com> wrote:
>
> Hi Johannes and Anton,
>
> thanks for the information, but I did not mean the time complexity of the function is constant (Big O notation). I mean the amount of time of execution is constant when we fix the list length.
>
> In fact, I want to write a function that the running time is constant (not the time complexity) given the size of input is fixed. That means it does not depend on the characteristic of the input.
>
> Best,
> Chan
>
>> On Feb 22, 2016, at 2:51 PM, Anton Bachin <antronbachin@gmail.com> wrote:
>>
>> 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
>>
>
--
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