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 69ED17EE51 for ; Mon, 15 Apr 2013 13:08:41 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=pra; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of syshen@nudt.edu.cn) identity=mailfrom; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="syshen@nudt.edu.cn"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@nudt.edu.cn) identity=helo; client-ip=61.187.54.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="syshen@nudt.edu.cn"; x-sender="postmaster@nudt.edu.cn"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlgHACPfa1E9uzYLdGdsb2JhbABQhmy9KCiBHw4BDBUIPIIfAQEFI1YQBQQCDgoCAiYCAiE2BhMRh3EDDo4SmwSIDg1MiRGBI4shgiAzB4IugRMDiQOMH4Fji3WINIIb X-IPAS-Result: AlgHACPfa1E9uzYLdGdsb2JhbABQhmy9KCiBHw4BDBUIPIIfAQEFI1YQBQQCDgoCAiYCAiE2BhMRh3EDDo4SmwSIDg1MiRGBI4shgiAzB4IugRMDiQOMH4Fji3WINIIb X-IronPort-AV: E=Sophos;i="4.87,474,1363129200"; d="scan'208";a="13307178" Received: from mail.nudt.edu.cn (HELO nudt.edu.cn) ([61.187.54.11]) by mail2-smtp-roc.national.inria.fr with ESMTP; 15 Apr 2013 13:08:39 +0200 Received: by ajax-webmail-coremail.nudt.edu.cn (Coremail) ; Mon, 15 Apr 2013 19:05:19 +0800 (GMT+08:00) Date: Mon, 15 Apr 2013 19:05:19 +0800 (GMT+08:00) From: =?UTF-8?B?5rKI6IOc5a6H?= To: "David House" Cc: "Malcolm Matalka" , caml-list Message-ID: <2b3ad45a.48f7.13e0d5ed8c7.Coremail.syshen@nudt.edu.cn> In-Reply-To: References: <1cbcde35.47c9.13e08b6f72a.Coremail.syshen@nudt.edu.cn> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Originating-IP: [113.246.242.103] X-Priority: 3 X-Mailer: Coremail Webmail Server Version 4.0.5a build 20121109(20529.5019.5013) Copyright (c) 2002-2013 www.mailtech.cn nudt-out X-SendMailWithSms: false X-CM-TRANSID:AQAAf0A5f0Tx3mtR2SsgAA--.4801W X-CM-SenderInfo: xv1vxvnq6q3vvwohv3gofq/1tbiAQAIE1C8Ui+8MAAcsb X-Coremail-Antispam: 1Ur529EdanIXcx71UUUUU7IcSsGvfJ3iIAIbVAYjsxI4VW5Jw CS07vEb4IE77IF4wCS07vE1I0E4x80FVAKz4kxMIAIbVAFxVCaYxvI4VCIwcAKzIAtYxBI daVFxhVjvjDU= Subject: Re: Re: [Caml-list] [OCAML]:: the cost of List.length Dear all: I have found that the slow down of my program is not caused by the List.len= gth directly, instead, the list length operation cause some different chang= e in my control flow, that is the direct cause of my slow down. but still thank you for your help. Shen > -----=E5=8E=9F=E5=A7=8B=E9=82=AE=E4=BB=B6----- > =E5=8F=91=E4=BB=B6=E4=BA=BA: "David House" > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2013-04-15 14:29:21 (=E6=98=9F=E6= =9C=9F=E4=B8=80) > =E6=94=B6=E4=BB=B6=E4=BA=BA: "Malcolm Matalka" > =E6=8A=84=E9=80=81: "=E6=B2=88=E8=83=9C=E5=AE=87" , c= aml-list > =E4=B8=BB=E9=A2=98: Re: [Caml-list] [OCAML]:: the cost of List.length >=20 > 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. >=20 > There is probably a better data structure than lists for your > purposes. What operations do you need, and which ones need to be fast? >=20 > 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 lis= t? > >> or is a const? > >> > >> Shen