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 AFBC17EF0D for ; Mon, 22 Feb 2016 20:51:10 +0100 (CET) IronPort-PHdr: 9a23:hOQguxGm4sy0Vz4OnlK1Np1GYnF86YWxBRYc798ds5kLTJ75rsuwAkXT6L1XgUPTWs2DsrQf27WQ7vyrADZdqb+681k8M7V0HycfjssXmwFySOWkMmbcaMDQUiohAc5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aJBzzOEJPK/jvHcaK1oLsh7/0psGYOl8VzBOGIppMbzyO5T3LsccXhYYwYo0Q8TDu5kVyRuJN2GlzLkiSlRuvru25/Zpk7jgC86l5r50IeezAcq85Vb1VCig9eyBwvZWz9Er1dhaU/nYXTkkRlxNJBUCFsEC7Dd/NtX7RtuN7kA+VOoWiRrA9X3Kk4KAxEkezoCgCPj89tmrQj5ojorhcpUeIoQB4xcb+aYqVNfw2KqrbYckdQ2BIVcZQUQROB4q9a80ECO9XbrUQlJX0u1Zb9Uj2PgKrHu66j2IRiw== 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-f173.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.173; 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.173 as permitted sender) identity=mailfrom; client-ip=209.85.223.173; 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-f173.google.com) identity=helo; client-ip=209.85.223.173; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="postmaster@mail-io0-f173.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0AxAACFZctWmK3fVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhUTBgEbEgsBAwELBgULDQ0hIQIRAQUBChIGExIQh2MBAwoIDp0sgTE+MY0dgleFAQoZJwMKUYN5AQEBAQEBAQEBAQEBAQEBAQEBAQEBDwEFCgSHcIJOgjqBeYMtgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IPAS-Result: A0AxAACFZctWmK3fVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhUTBgEbEgsBAwELBgULDQ0hIQIRAQUBChIGExIQh2MBAwoIDp0sgTE+MY0dgleFAQoZJwMKUYN5AQEBAQEBAQEBAQEBAQEBAQEBAQEBDwEFCgSHcIJOgjqBeYMtgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IronPort-AV: E=Sophos;i="5.22,485,1449529200"; d="scan'208";a="204183058" Received: from mail-io0-f173.google.com ([209.85.223.173]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 20:51:09 +0100 Received: by mail-io0-f173.google.com with SMTP id l127so188920139iof.3 for ; Mon, 22 Feb 2016 11:51:09 -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=PIhJtKw4cl65n+yK5K6aWAMiU61NKYANEHvkb3PemGQ=; b=aQszwVN3RkzXLS1h8GewpaDlcHnM3w2ZePrDHQTVfqQHCdXW/i7v0DYxmZx1p2a13M KUieP+9q3Y56EuPUl/lin5rmJN3W4dx4PIIUrg4tzL5DW/uJIFzsgVXIxV88uHMMKEyv lSM+yNzxyLL3YH0ApR6kFyJ4pvpv5R/5CWWUsYVWCFD7pB9DwirSfZDtnvIXiPujXI1D NQLv62m2BuHQiQxgGyfb/t/ZZP3AsnAR4aCWiEQryimZPI8oHWEmPDqaDj7TEx54gyDV scjK1zthGVeY9IeVXvGNOK9/KmDmyEk/+YhNM3kNtZtetDaKIePEep3UCIU7NegsOdjg 7bWA== 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=PIhJtKw4cl65n+yK5K6aWAMiU61NKYANEHvkb3PemGQ=; b=LjvPC+2bM8llyVl8uqeR5bSPIBSCsLv2XmVUcn5Zmy+IHYXRQ+JmYAtitYlB95/yLl 36hPJ6XLr4XShVuDoaSo2Ei1E9CmiTryrqQiNQcXnW5YprcOKK9+HNPqqeFDaIuZ6xct AXSWufieMS5LuHPMNS5LbF48zwPpLURHVp0r/tqX66GCgdon4AxSUDtAQQL/6a8gL4Wd 86wbdi6mL8YGBgf1UOwDVieYMHgy7G/Rw3rpLXXsYkFwHTRTYS/u8ga0gRsD1Q8+m7oG RC3KawVZ+D4HA5vhyY63Z/RWww+K/32xGxPLhhK6C8xWCNluxU3u6UVfyt2bYFz1YePX uKOg== X-Gm-Message-State: AG10YOQLcSjrbxtOLAezUYGwW5sp7hntPJQ08hUmZha2Kmtbynw9J0h78cInMQLYbUO4ww== X-Received: by 10.107.16.17 with SMTP id y17mr35694031ioi.119.1456170668672; Mon, 22 Feb 2016 11:51:08 -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 j10sm9825166igx.15.2016.02.22.11.51.07 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 22 Feb 2016 11:51:08 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) From: Anton Bachin In-Reply-To: <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> Date: Mon, 22 Feb 2016 13:51:07 -0600 Cc: OCaml users X-Mao-Original-Outgoing-Id: 477863467.209512-385f34d2c8d0b2202777c397796154ec Content-Transfer-Encoding: quoted-printable Message-Id: References: <20160222094853.GH1544@nunchakus.loria.fr> <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> To: Chan Ngo X-Mailer: Apple Mail (2.2070.6) Subject: Re: [Caml-list] Constant-time function 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 t= he 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 nontri= vial amount of time to compute. > 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 an= d 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 fac= t, 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 the= 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-bigst= ring , >> 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