From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 8AB6ABB94 for ; Tue, 4 Oct 2005 18:14:34 +0200 (CEST) Received: from cenn.mc.mpls.visi.com (cenn.mc.mpls.visi.com [208.42.156.9]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j94GEXiP009660 for ; Tue, 4 Oct 2005 18:14:34 +0200 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by cenn.mc.mpls.visi.com (Postfix) with ESMTP id 8BBC18265; Tue, 4 Oct 2005 11:14:32 -0500 (CDT) Date: Tue, 4 Oct 2005 11:15:33 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: skaller Cc: Martin Chabr , Thomas Fischbacher , caml-list@yquem.inria.fr Subject: Re: [Caml-list] Avoiding shared data In-Reply-To: <1128394430.23813.20.camel@rosella> Message-ID: References: <20051003200337.14092.qmail@web26809.mail.ukl.yahoo.com> <1128394430.23813.20.camel@rosella> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at nez-perce with ID 4342AA69.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 avoiding:01 mutable:01 caching:01 mutable:01 nodes:01 2005,:98 weights:98 wrote:01 node:01 graph:01 edges:01 cyclic:01 precisely:01 algorithm:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Tue, 4 Oct 2005, skaller wrote: > Mutable shared data is very useful: caching is > an obvious example where this is precisely what you want. Also, occassionally mutable data allows you to do something in O(1) instead of O(log N). If this extra cost is in your inner loop, it can slow the whole algorithm down by a factor of 10-30 fold easy. Graph algorithms are especially bad for this. Want to get a name for yourself? Come up with a way to represent cyclic graphs in a purely functional way such that given any arbtirary node, I can find out what other nodes it has edges to (and what their weights are) in O(1). Brian