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 878A27EE51 for ; Mon, 15 Apr 2013 08:29:25 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of dhouse@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of dhouse@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="dhouse@janestreet.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@tot-dmz-mxout1.janestreet.com) identity=helo; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dhouse@janestreet.com"; x-sender="postmaster@tot-dmz-mxout1.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnsBABmda1EmacjlnGdsb2JhbABQhiVHvVB/Hg4BAQEBAQYNCQkUKIIfAQEFIx0BATcBDwkCCwMKAgImAgIhARIBBQEcBhOIAgMPA41hjySKb3GDSgEFhCkNiVcGgSOLIYIgMweCLoETlSWBY4t1gzoWKYQv X-IPAS-Result: AnsBABmda1EmacjlnGdsb2JhbABQhiVHvVB/Hg4BAQEBAQYNCQkUKIIfAQEFIx0BATcBDwkCCwMKAgImAgIhARIBBQEcBhOIAgMPA41hjySKb3GDSgEFhCkNiVcGgSOLIYIgMweCLoETlSWBY4t1gzoWKYQv X-IronPort-AV: E=Sophos;i="4.87,473,1363129200"; d="scan'208";a="13250751" Received: from mx5.janestreet.com (HELO tot-dmz-mxout1.janestreet.com) ([38.105.200.229]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 15 Apr 2013 08:29:24 +0200 Received: from tot-oib-smtp1.delacy.com ([172.27.22.15] helo=tot-smtp) by tot-dmz-mxout1.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1URcuo-0004Zu-0o for caml-list@inria.fr; Mon, 15 Apr 2013 02:29:22 -0400 Received: from tot-dmz-mxgoog1.delacy.com ([172.27.224.14] helo=mxgoog2.janestreet.com) by tot-smtp with esmtps (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1URcuo-00035D-00 for caml-list@inria.fr; Mon, 15 Apr 2013 02:29:22 -0400 Received: from mail-wg0-f70.google.com ([74.125.82.70]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1URcun-0008M5-SY for caml-list@inria.fr; Mon, 15 Apr 2013 02:29:21 -0400 Received: by mail-wg0-f70.google.com with SMTP id e11so3497604wgh.9 for ; Sun, 14 Apr 2013 23:29:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=x-received:mime-version:x-received:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=oST85FZjmCHV4lpXXwGYWOpc4yA+pHY9QmUzKS1XzWo=; b=n31ibKQ90iqjUzqqxzHXN39CFEeBH0WrJRHB3p9Kvz9PqWu0Vs290ln+ViMvlXoxQe s/bLhoPOLSdrnBjDwNQ5fvC8YeribYva6QhJ6ON07/YCdJcSEd1THASK9pAiSmdHm5XE bG73WKI8EiQ22y5FZcmEL4frMFdwVwuyhhhKM= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-received:mime-version:x-received:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding:x-gm-message-state; bh=oST85FZjmCHV4lpXXwGYWOpc4yA+pHY9QmUzKS1XzWo=; b=BtKLDb7NdX4Xt0vy4Fq2VQlTr1B27F4YKLxMEW06nfBbGmM464Xx9ZuyQzwpUn9t2n hfPKJSnv/BlBIcEVl7i4qwWvmiR0FBCstJSLoHxD+QijcEBsYbLJaTqc3Q/xn56DKO9h SfDfbzsdjnqxR2hXsYXM33UZ+o50LD8nUR1AdUpCRmjRVNr06l8HTz7Mekk2PYHspV2M sfQwbk7glKREA8Fl/0RqnJXVuvfh3e0YyJZExtlTGL0LLSsbw71Mkdc5k7y2Q6f2o9/e jgjMmfQtF0kqb2Y5XuBhMIVX0Tg6px1M8hPuTNoMe34BdQUZT+LVudJYuJxLt8Bum0N8 NWBg== X-Received: by 10.14.201.67 with SMTP id a43mr41033723eeo.33.1366007361336; Sun, 14 Apr 2013 23:29:21 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.14.201.67 with SMTP id a43mr41033711eeo.33.1366007361250; Sun, 14 Apr 2013 23:29:21 -0700 (PDT) Received: by 10.223.178.5 with HTTP; Sun, 14 Apr 2013 23:29:21 -0700 (PDT) In-Reply-To: References: <1cbcde35.47c9.13e08b6f72a.Coremail.syshen@nudt.edu.cn> Date: Mon, 15 Apr 2013 07:29:21 +0100 Message-ID: From: David House To: Malcolm Matalka Cc: =?UTF-8?B?5rKI6IOc5a6H?= , caml-list Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Gm-Message-State: ALoCoQkAUcVn5iqXShDkM4xtY+V03lRtaHumnBSy1q7Bw3Xs/Ufm1m+OtmCmNj0bCay4QdFyyP++YOnq6jpk6vLCZdPWPKnHE8dhxEF/zU1DmlefptDnZ8IfFHtOVHCP9jSTBqC4a57w1D6BvyshCuae4PlqSHIpcQ== Subject: Re: [Caml-list] [OCAML]:: the cost of List.length Lists are naive linked lists, i.e. either the empty list or a pair of an element and a list. Finding the length means walking to the end of the list. There is probably a better data structure than lists for your purposes. What operations do you need, and which ones need to be fast? On 14 April 2013 14:32, Malcolm Matalka wrote: > O(n) > > Den 14 apr 2013 15:27 skrev "=E6=B2=88=E8=83=9C=E5=AE=87" : > >> Dear all: >> >> I have a program that run very fast. >> >> Recently, I add a call to List.length to this old program's inner loop, >> which make it significantly slower. >> >> So what is the cost of List.length, is it liner to the size of the list? >> or is a const? >> >> Shen