Re: [Caml-list] Constant-time function

["Milan Stanojević" <milanst@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4260 bytes --]

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)
On Feb 22, 2016 15:02, "Anton Bachin" <antronbachin@gmail.com> wrote:

> 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

[-- Attachment #2: Type: text/html, Size: 6105 bytes --]