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 BE9E87EF0D for ; Mon, 22 Feb 2016 21:02:13 +0100 (CET) IronPort-PHdr: 9a23:adOB0B0sdzlqcmlXsmDT+DRfVm0co7zxezQtwd8ZsegfLfad9pjvdHbS+e9qxAeQG96LtLQZ16GP6PmocFdDyKjCmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TWM5DIfUi/yKRBybrysXNWC0ILqi6vroMSbSj4LrQT+SIs6FA+xowTVu5teqqpZAYF19CH0pGBVcf9d32JiKAHbtR/94sCt4MwrqHwI6LoJvvRNWqTifqk+UacQTHF/azh0t/vQqALbQACTynwZW2QQ2loUUkmWpC39C7zxuy2ykOV6kH2RPcTwC7Y7Xm74t/xDRxrhiSNBPDk8pjL5kMt12YtdvBWn7zZ2yI7VZsnBPfxiZKTbd9oRRWtHdslUXi1FRIi7at1cXKI6Ie9Eotyl9BM1phykCFzpWbri Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=antronbachin@gmail.com; spf=Pass smtp.mailfrom=antronbachin@gmail.com; spf=None smtp.helo=postmaster@mail-io0-f172.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of antronbachin@gmail.com) identity=pra; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="antronbachin@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of antronbachin@gmail.com designates 209.85.223.172 as permitted sender) identity=mailfrom; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="antronbachin@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-f172.google.com) identity=helo; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="postmaster@mail-io0-f172.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0AxAAAKaMtWmKzfVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhEEGQEbEgsBAwELBgULDQICCR0CAiECEQEFAQoSBhMSEIdjAQMKCA6dNoExPjGLNIFpgleFAgoZJwMKUYN5AQEBAQEBAQEBAQEBAQEBAQEBAQEBDwEFCgRthwMIgkaCOoF5gwIrgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IPAS-Result: A0AxAAAKaMtWmKzfVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhEEGQEbEgsBAwELBgULDQICCR0CAiECEQEFAQoSBhMSEIdjAQMKCA6dNoExPjGLNIFpgleFAgoZJwMKUYN5AQEBAQEBAQEBAQEBAQEBAQEBAQEBDwEFCgRthwMIgkaCOoF5gwIrgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IronPort-AV: E=Sophos;i="5.22,485,1449529200"; d="scan'208";a="204184229" Received: from mail-io0-f172.google.com ([209.85.223.172]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 21:02:12 +0100 Received: by mail-io0-f172.google.com with SMTP id 9so191293341iom.1 for ; Mon, 22 Feb 2016 12:02:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=0+pLYj78vQscK/4e7+mMNQ0Tgxp00jCYJgmIeIq2gUo=; b=dCJnDv6DZJ4GsG/02cXTSwAJ0DXCFPoLY4WG1mUI1ppOXrxFV6jEhMO2b15zC/Qy5K JwF+aMagO+se8rT3taVBlXvTjhG5B6hd7YyyI7Ii2MrgFALVrCxFZFsvw5MIATIaX9mn vtSf4DRfsqIPJO4Smn8SldPVGDciyyxjmqIcRtNf9/gzqzT2FsH+jNrkb/AHduGGwZlo QLI7mA9xJXoQgZoGjMWSjb4MFOuTvPhlFjkflsB0uy+/0zG4PvcbcEW/iNGunO5cdTaE e9qhhRXM0lpXwx3MflQUAXkRV0ZYwkUnwd2oHg0FgQRZRl1f2YusC6GBV30toaB7hUHL Wrdw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=0+pLYj78vQscK/4e7+mMNQ0Tgxp00jCYJgmIeIq2gUo=; b=hN1yGHKF6IhVMVbye6//u8RIOTfr7dZ2OKriRa7N7X3eAkZ4mIYru3Cb8Ekar5WyT+ /f1uQhbUdo8UjuFj+uMqJ/ImCFP1SmBGp1PG0XluDhJQxUJVvGn5qCgIutVS6BY0crY8 oSG6m9V9M1s/CNCxXdBsFDqcGVxFtuxB1ZnQByoiNSYsKEHEBNIb5xDPy31kL5anmxmh EmCwfhRIolLJEcRXMcS+jq1Pdtf0gutYSuScA2Y+xryZGcxUOjxeCZRu0ekhxfkswuxN K44ZLOITuQwYmz4I/ReQ7i+tQE82E6GqNM3K6+PU2zGfm8bsZl37ygXcamAfXQjlWsYc MKoQ== X-Gm-Message-State: AG10YOQwLK9IsDILiIRALQzXORGMJj2rDZ9rkX3LmOqZhS7Y2/mc/RO9OfWF5w/cknGrmg== X-Received: by 10.107.11.93 with SMTP id v90mr29660062ioi.188.1456171331597; Mon, 22 Feb 2016 12:02:11 -0800 (PST) Received: from [192.168.0.10] (c-73-9-77-177.hsd1.il.comcast.net. [73.9.77.177]) by smtp.gmail.com with ESMTPSA id l6sm9807621igv.10.2016.02.22.12.02.11 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 22 Feb 2016 12:02:11 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) From: Anton Bachin In-Reply-To: <4BDBBF0B-1783-4F91-9EFA-D3E9FF9EF1EF@gmail.com> Date: Mon, 22 Feb 2016 14:02:10 -0600 Cc: OCaml users X-Mao-Original-Outgoing-Id: 477864130.500011-9b592b55452e3cd8e20f09c8973ba120 Content-Transfer-Encoding: quoted-printable Message-Id: <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> To: Chan Ngo X-Mailer: Apple Mail (2.2070.6) Subject: Re: [Caml-list] Constant-time function But the complexity of this function is not constant if you fix only the lis= t length. It still varies quadratically in the location of the first pair o= f 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 visi= t 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: >=20 > Hi Johannes and Anton, >=20 > 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 execut= ion is constant when we fix the list length. >=20 > In fact, I want to write a function that the running time is constant (no= t the time complexity) given the size of input is fixed. That means it does= not depend on the characteristic of the input. >=20 > Best, > Chan >=20 >> On Feb 22, 2016, at 2:51 PM, Anton Bachin wrote: >>=20 >> 1. You are computing the length of l1 and l2 every iteration. On the fir= st iteration, it is the lengths of the original lists. On the second iterat= ion, it is the lengths of their tails. This function takes time quadratic i= n the maximum of (length l1, length l2), as written. List.length itself tak= es linear time. >>=20 >> 2. If h1 and h2 are nontrivial types, structural equality may take a non= trivial amount of time to compute. >>=20 >>> On Feb 22, 2016, at 13:45, Chan Ngo wrote: >>>=20 >>> Dear all, >>>=20 >>> I have write a simple function to compare two lists as below: >>>=20 >>> let rec lcomp l1 l2 =3D=20 >>> if (List.length l1 !=3D List.length l2)=20 >>> then false >>> else match l1, l2 with=20 >>> | h1::t1, h2::t2 -> h1 =3D h2 && lcomp t1 t2 >>> | _, _ -> true;; >>>=20 >>> 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 f= act, when I run this function with two lists of around 100 elements,=20 >>> + with only 10th element is different: it takes 0.000027s >>> + with only 90th element is different: it takes 0.000116s >>>=20 >>> You see the execution times are really different. Thus, I wonder that t= he compiler did some optimization? Does anyone have some pointers? >>>=20 >>> Thanks, >>> Chan >>>=20 >>>=20 >>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes wrote: >>>>=20 >>>> Hello, >>>>=20 >>>> 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. >>>>=20 >>>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-big= string , >>>> and contributions and criticism are welcome. >>>>=20 >>>> Cheers, >>>>=20 >>>> --=20 >>>> Simon Cruanes >>>>=20 >>>> http://weusepgp.info/ >>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 49A= A 62B6 >>>=20 >>>=20 >>> --=20 >>> 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 >>=20 >=20