From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id CD97CBBC1 for ; Wed, 20 Feb 2008 17:02:33 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAABLdu0fRVciph2dsb2JhbACQUQEBAQcFBAsIGJgOh04 X-IronPort-AV: E=Sophos;i="4.25,381,1199660400"; d="scan'208";a="22836252" Received: from wf-out-1314.google.com ([209.85.200.169]) by mail4-smtp-sop.national.inria.fr with ESMTP; 20 Feb 2008 17:02:32 +0100 Received: by wf-out-1314.google.com with SMTP id 25so894923wfa.15 for ; Wed, 20 Feb 2008 08:02:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=Wc18N+R/hwdEbCpv6BxaAHuWxqxHCpJLyfNerFLN+SM=; b=OmiwMbrisV2vCqsVziqEFGmTLSsl4EalYSU4NpnWnN2l4Ie0kijFRyxQUipls60iqs1CTJR7wevSeGx5+1MVPihZX1v1pydNi3oFkuaL03DEkpmaWTQXxhNV2HUb1O7ZSG9AIdHAXQi6FbpyQl/VvbqVXLY3hZaHCbCqXLvlpqI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=Q37UGHGkDW5IU0EsePpMmo5rMFis8nFf8YrcMQAss9J+5CMFaGFEnfMFmyP4Y+AjMGQwzVGjn48+2znsMaEeP3I3RRPVtn47VSn7zWgiNJ7KsyP/REt1LJgNOq9Dkjq9h4fm1ozWka7I49vDwjzv+MXgRNOMb0U7mTYWdqsIod0= Received: by 10.142.217.17 with SMTP id p17mr6623625wfg.139.1203523351700; Wed, 20 Feb 2008 08:02:31 -0800 (PST) Received: by 10.142.134.13 with HTTP; Wed, 20 Feb 2008 08:02:31 -0800 (PST) Message-ID: <4a051d930802200802w6c0e9a0ayde1000f1b4584753@mail.gmail.com> Date: Wed, 20 Feb 2008 11:02:31 -0500 From: "Christopher L Conway" Sender: christopherleeconway@gmail.com To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Re: large hash tables In-Reply-To: <33d2b3f70802192118p4d887212mcf76e34447c54e52@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <55e81f00-5ef7-4946-9272-05595299e114@41g2000hsc.googlegroups.com> <33d2b3f70802192118p4d887212mcf76e34447c54e52@mail.gmail.com> X-Google-Sender-Auth: 13bbc760b2af11f8 X-Spam: no; 0.00; hash:01 okasaki's:01 deques:01 usma:01 okasaki:01 pubs:01 caml-list:01 tail:01 data:02 append:02 jfp:02 functional:02 eecs:03 element:03 element:03 John, Everybody else has answered your main concerns in great detail. I just have a silly nitpick... > let newList = List.rev_append [newElement] oldList in This is what is known as a "functional anti-pattern" [1]. As you probably know, adding an element at the head of a list is O(1), whereas adding an element at the tail is O(n). If possible, you should just keep these lists in reverse order (let newList = newElement :: oldList) and call List.rev "on demand" when you pull the data out of the table (or keep separate forward/reversed lists, populating the forward list on demand, ala Okasaki's deques [2]). Regards, Chris [1] http://trevion.blogspot.com/2006/12/little-knowledge-gets-you-long-way.html [2] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp95