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 F1FB67EF0D for ; Mon, 22 Feb 2016 20:57:15 +0100 (CET) IronPort-PHdr: 9a23:B7Df8h9OPAy3Qv9uRHKM819IXTAuvvDOBiVQ1KB92u0cTK2v8tzYMVDF4r011RmSDdqdtq4P0rGP+4nbGkU+or+5+EgYd5JNUxJXwe43pCcHRPC/NEvgMfTxZDY7FskRHHVs/nW8LFQHUJ2mPw6anHS+4HYoFwnlMkItf6KuStGU0pj8jrvrs7ToICx2xxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cYk7sb+sVBSaT3ebgjBfwdVWx+cjMD39DwrRTIUSeI43IdVC1WzksJUED560TTWIv2tGPQv+F92S/SacTwUaozXz6r5KdqTjfnjS4GM3gy92SB2eJqi6cOixKooVRZzImcNIqVPfw4eKzaJ4lCHkJOW89QU2pKBYbqPNhHNPYIIesN99q1nFAJtxbrQFT1CQ== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=chan.ngo2203@gmail.com; spf=Pass smtp.mailfrom=chan.ngo2203@gmail.com; spf=None smtp.helo=postmaster@mail-qk0-f175.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of chan.ngo2203@gmail.com) identity=pra; client-ip=209.85.220.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of chan.ngo2203@gmail.com designates 209.85.220.175 as permitted sender) identity=mailfrom; client-ip=209.85.220.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@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-qk0-f175.google.com) identity=helo; client-ip=209.85.220.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="postmaster@mail-qk0-f175.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BtAADlZstWka/cVdFehAxtqjCJCocaAQ2BZiGFbAKBRDgUAQEBAQEBAQEQAQEBAQcLCwkfMUESAYFZghQBAQEDARIVEwYBGxILAQMBCwYFCwMKDSEhAhEBBQEKEgYTEhCHYwEDCggOnTWBMT4xjR2CV4UCChknAwpRg3kBAQEBAQEBAQEBAQEBAQEBAQEBAQEPAQUKBIdwCIJGgjqBeYMtgQ8FhhcMh3uIYQiFV4YUgXOCJoZthWCHBYYGL4EPHgEBgjgNEQiBZkwBg3+EOQEBAQ X-IPAS-Result: A0BtAADlZstWka/cVdFehAxtqjCJCocaAQ2BZiGFbAKBRDgUAQEBAQEBAQEQAQEBAQcLCwkfMUESAYFZghQBAQEDARIVEwYBGxILAQMBCwYFCwMKDSEhAhEBBQEKEgYTEhCHYwEDCggOnTWBMT4xjR2CV4UCChknAwpRg3kBAQEBAQEBAQEBAQEBAQEBAQEBAQEPAQUKBIdwCIJGgjqBeYMtgQ8FhhcMh3uIYQiFV4YUgXOCJoZthWCHBYYGL4EPHgEBgjgNEQiBZkwBg3+EOQEBAQ X-IronPort-AV: E=Sophos;i="5.22,485,1449529200"; d="scan'208";a="204183716" Received: from mail-qk0-f175.google.com ([209.85.220.175]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 20:57:15 +0100 Received: by mail-qk0-f175.google.com with SMTP id o6so60300508qkc.2 for ; Mon, 22 Feb 2016 11:57:15 -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=0yt0cquHDrbGt/WlDU8hL+CyI8tAHG48wrVXG7+Cj3E=; b=HbEvFvd+5qdvSJPeWYcjnKnSmEe2koobRDRQbl/mGgjKDXmlaS1fL7d4JbGnfgIv0l 4tCA+y48W31hsYDAbIt/pL7MgZ0nSUuYHkc3wVsO74hdHZ7iVMjBaryHg1ZBAWpfVweu Nw57C37s1i6ushwzfLpBAk28oK9lYiOP5nz3IXuxxcniC9cdAVeop1iNtuZHMExMw+Cq VewmyuwDHGUsInO8Ktkux8hjjYU/1HJFzm8PYjqxbmUZhEp47cuc0rSSUkbBz5744iVm hlpDsreA+OLSWPti7TBlgBdggIDKMhT/QrudTgaiUvQmYYR9YZJoruQ8wcS1Zu4vSBm4 UcMw== 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=0yt0cquHDrbGt/WlDU8hL+CyI8tAHG48wrVXG7+Cj3E=; b=IyLaNuqrO0NQoVjmrOMybuXH0X9PCOl4RzeTpJn/GM5BdXLoqT9I6nkN2RiB6SEJJN LokF1upSF6Rs7WB6ZqimMHDLBT0X4viKY45VL9XfEp0z+D7TFHGxI4OItgiJjFz9YLkT dvXhmmlzLVoG9lZ2YJal5Zly9PGVESR3U1n4eB57KyvHh4vrU5DV4QiKXOvPfXp777Lj YyFHtbffY4RM2vVW7FzJEAtzKs+MHWoSTH3EPBhdNNQaEtQw5XV9+mcT0DrNsVYWj/Oj bwT4MEcSGFhMEXVzvVDyNkq6XfsBWNt99tfHnCXcM2XwZi7wg4xElJBw78FEuYHRB6IH RmKA== X-Gm-Message-State: AG10YOSmdXJdnnscgsfY6/durpunak3pu9f+i8SvgdmVu12/ag8pSqMYe5kl/aMI+Cw++g== X-Received: by 10.55.53.207 with SMTP id c198mr36664870qka.24.1456171033809; Mon, 22 Feb 2016 11:57:13 -0800 (PST) Received: from chans-mbp.wv.cc.cmu.edu (Chans-MBP.wv.cc.cmu.edu. [128.237.202.31]) by smtp.gmail.com with ESMTPSA id x62sm10819683qhc.42.2016.02.22.11.57.12 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 22 Feb 2016 11:57:12 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) From: Chan Ngo In-Reply-To: Date: Mon, 22 Feb 2016 14:57:11 -0500 Cc: OCaml users Content-Transfer-Encoding: quoted-printable Message-Id: <4BDBBF0B-1783-4F91-9EFA-D3E9FF9EF1EF@gmail.com> References: <20160222094853.GH1544@nunchakus.loria.fr> <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> To: Anton Bachin X-Mailer: Apple Mail (2.3112) Subject: Re: [Caml-list] Constant-time function Hi Johannes and Anton, thanks for the information, but I did not mean the time complexity of the f= unction is constant (Big O notation). I mean the amount of time of executio= n 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 n= ot depend on the characteristic of the input. Best, Chan > 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 firs= t iteration, it is the lengths of the original lists. On the second iterati= on, 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 take= s linear time. >=20 > 2. If h1 and h2 are nontrivial types, structural equality may take a nont= rivial 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 a= nd l2 (in case they are same length, otherwise it return immediately) and i= t is constant time (i.e., we fixed the length of l1 and l2). However, in fa= ct, 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 th= e 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-bigs= tring , >>> 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 49AA= 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