From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 029707EF0D for ; Mon, 22 Feb 2016 21:12:21 +0100 (CET) IronPort-PHdr: 9a23:Eqi1MROlm8+cqsXhy+Al6mtUPXoX/o7sNwtQ0KIMzox0Kfz7rarrMEGX3/hxlliBBdydsKIbzbeK+Pm7BSQp2tWojjMrSNR0TRgLiMEbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpQAbFhi3DwdpPOO9QteU1JTokb3usMSIP01hv3mUX/BbFF2OtwLft80b08NJC50a7V/3mEZOYPlc3mhyJFiezF7W78a0+4N/oWwL46pyv+YJa6jxfrw5QLpEF3xmdjltvIy4gyLeVhOC7WcwVWAfkxwAQ1SUrUKyYpCkmy3msew18iCRPczwBeQ9Xyi46KFhQRToiSEvODsw8WWRgct12vF1uhWk8jl+x4fSV7qJPfx5fK7DfNhSEW9AWs9XTDBpDYa1bo9JBO0Ea7UL57LhrkcD+EPtTTKnA/nin3oV33I= Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=milanst@gmail.com; spf=Pass smtp.mailfrom=milanst@gmail.com; spf=None smtp.helo=postmaster@mail-io0-f181.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of milanst@gmail.com) identity=pra; client-ip=209.85.223.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="milanst@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of milanst@gmail.com designates 209.85.223.181 as permitted sender) identity=mailfrom; client-ip=209.85.223.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="milanst@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-io0-f181.google.com) identity=helo; client-ip=209.85.223.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="postmaster@mail-io0-f181.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0A3AABnastWmLXfVdFehAxeDwaqKpAkAQ2BZhcBCYVsAoE9BzgUAQEBAQEBAQEQAQEBAQEGCwsJIS+CLYIUAQEBAwESEQQZARsSCwEDAQsGBQsDCg0dAgIhAQERAQUBChIGExIQh2MBAwoIDp03gTE+MYs0gWmCV4UCChknAwpRg3kBAQEBAQEBAQIBAQEBAQEBAQEBEAEFCgSGBIQ6gjqCKIIbOBOBJwWGFwyHe4hphVeGFIFzgiaMTYcFhgYRHoEPDw8BAYI4DREIgWYeLgGIOAEBAQ X-IPAS-Result: A0A3AABnastWmLXfVdFehAxeDwaqKpAkAQ2BZhcBCYVsAoE9BzgUAQEBAQEBAQEQAQEBAQEGCwsJIS+CLYIUAQEBAwESEQQZARsSCwEDAQsGBQsDCg0dAgIhAQERAQUBChIGExIQh2MBAwoIDp03gTE+MYs0gWmCV4UCChknAwpRg3kBAQEBAQEBAQIBAQEBAQEBAQEBEAEFCgSGBIQ6gjqCKIIbOBOBJwWGFwyHe4hphVeGFIFzgiaMTYcFhgYRHoEPDw8BAYI4DREIgWYeLgGIOAEBAQ X-IronPort-AV: E=Sophos;i="5.22,486,1449529200"; d="scan'208,217";a="204184939" Received: from mail-io0-f181.google.com ([209.85.223.181]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 21:12:19 +0100 Received: by mail-io0-f181.google.com with SMTP id 9so191617096iom.1 for ; Mon, 22 Feb 2016 12:12:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=yGzxWapqm/1+EJsqnQAvPQdzJWhoit5ahq0J6nJ6Hyw=; b=j549yOGxAydNFU/N7XlahGpP2HPLCLPAl0V9I/+Rh1fHf14HdXKUI5Uh0S0+wCnHZo kU8UZDlNzQr6cEl70IscXRt62vBJ1anga2ufiWTGZAGcJmFx5yaPciR1ncX8e4SryY1z DvWKDhm+undWj7zPZeS2miDqCPuQrPchuOMlfZwCXRtdNzVtoZsAyD5Bt26TuxSD1Skl 0iugKnAtpfieBvN+5ZZh74TMZ9WZl23hElopf5kr43fbKEhzyQJJxNdhfgSs5wH3kbx8 m2Ia7JN+P85UN9YSzrjbmuBAHjTpi31G4wGGY8lbmlt5/tOIZOd0mrLQqiMH0pRReiT0 afgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=yGzxWapqm/1+EJsqnQAvPQdzJWhoit5ahq0J6nJ6Hyw=; b=FxIYAcSHymEW30HTP9DsUzq4X6XiN+ZTyewR7roegR4SyaLaCj58ob0gEcGuOJSFNP hIWv8r4rEfWMiq2lmJGdP3cqwtbl8l7McJgJR/VfZzwOG/z2vswn3LIzMMjFoQxZAxIz mgKpxbBMPE3o71qgNpED79NJ/roxYcUY3wFqj+J7gi9vtKriVEg3gShZI7b8+MD5knUx Voi6ZGKgOIXXrzDh6EpSVTJuisUDiFl5k54JpjujKmyWOElUTWfeoPsxTSGOFhJXDZyS ukDWR7kA+D0ItdFDjsVPkv3W16NJchEmo6SXwAJKQayE2xh4+hzOlkhugg0FEZjD//x0 fZQg== X-Gm-Message-State: AG10YOQVGkOTHdx0pw/cdGOdt0Y86IdbEZgtYEWDEoAFdJ8cFzcG74ITRlX4rGHwrCYPkjscptd2doAwwUU8tA== MIME-Version: 1.0 X-Received: by 10.107.166.195 with SMTP id p186mr30434678ioe.146.1456171938321; Mon, 22 Feb 2016 12:12:18 -0800 (PST) Received: by 10.79.12.80 with HTTP; Mon, 22 Feb 2016 12:12:17 -0800 (PST) Received: by 10.79.12.80 with HTTP; Mon, 22 Feb 2016 12:12:17 -0800 (PST) In-Reply-To: <3DA136DD-0A26-4247-852E-DA596EBFE031@gmail.com> References: <20160222094853.GH1544@nunchakus.loria.fr> <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> <4BDBBF0B-1783-4F91-9EFA-D3E9FF9EF1EF@gmail.com> <3DA136DD-0A26-4247-852E-DA596EBFE031@gmail.com> Date: Mon, 22 Feb 2016 15:12:17 -0500 Message-ID: From: =?UTF-8?Q?Milan_Stanojevi=C4=87?= To: Anton Bachin Cc: Caml List , Chan Ngo Content-Type: multipart/alternative; boundary=001a11377af21d9e2b052c617315 Subject: Re: [Caml-list] Constant-time function --001a11377af21d9e2b052c617315 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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" 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 =E2=80=9Couter iteration= =E2=80=9D is > performed that many times, and the =E2=80=9Cinner" 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 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 > 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.leng= th > 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 wrote: > >>> > >>> Dear all, > >>> > >>> I have write a simple function to compare two lists as below: > >>> > >>> let rec lcomp l1 l2 =3D > >>> if (List.length l1 !=3D List.length l2) > >>> then false > >>> else match l1, l2 with > >>> | h1::t1, h2::t2 -> h1 =3D 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 --001a11377af21d9e2b052c617315 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Chan, I think you're confused because you expect that th= e 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 sho= uld get the behavior of visiting all elements (which is of course undesirab= le in practice)

On Feb 22, 2016 15:02, "Anton Bachin" = <antronbachin@gmail.com>= ; wrote:
But the com= plexity of this function is not constant if you fix only the list length. I= t still varies quadratically in the location of the first pair of elements = that are different, because the =E2=80=9Couter iteration=E2=80=9D is perfor= med that many times, and the =E2=80=9Cinner" List.lengths visit at lea= st 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 exe= cution 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 d= oes 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 t= he 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 quadr= atic in the maximum of (length l1, length l2), as written. List.length itse= lf 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:<= br> >>>
>>> let rec lcomp l1 l2 =3D
>>> if (List.length l1 !=3D List.length l2)
>>> then false
>>> else match l1, l2 with
>>> | h1::t1, h2::t2 -> h1 =3D h2 && lcomp t1 t2
>>> | _, _ -> true;;
>>>
>>> In theory, we can see that the execution is a function of leng= th of l1 and l2 (in case they are same length, otherwise it return immediat= ely) and it is constant time (i.e., we fixed the length of l1 and l2). Howe= ver, in fact, when I run this function with two lists of around 100 element= s,
>>> + 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 wond= er 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 dea= ling 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.= =C2=A0 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=C2=A0 7= D8D 4AC0 1D08 49AA 62B6
>>>
>>>
>>> --
>>> Caml-list mailing list.=C2=A0 Subscription management and arch= ives:
>>> https://sympa.inria.fr/sympa/arc/caml-list
>>> Beginner's list: http://groups.yahoo.c= om/group/ocaml_beginners
>>> Bug reports: http://caml.inria.fr/bin/caml-bugs >>
>


--
Caml-list mailing list.=C2=A0 Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocam= l_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
--001a11377af21d9e2b052c617315--