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=DNS_FROM_RFC_ABUSE, NO_REAL_NAME autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id B778DBBAF for ; Mon, 10 Aug 2009 14:19:39 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApsEABOtf0qGdRUV/2dsb2JhbACPSL44hBgF X-IronPort-AV: E=Sophos;i="4.43,353,1246831200"; d="scan'208";a="32267299" Received: from pegasus.math.carleton.ca ([134.117.21.21]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 10 Aug 2009 14:19:38 +0200 Received: from pegasus.carleton.ca (pegasus.carleton.ca [127.0.0.1]) by pegasus.math.carleton.ca (Postfix) with ESMTP id D01857FCAD6 for ; Mon, 10 Aug 2009 08:19:35 -0400 (EDT) Received: from 70.26.45.246 (SquirrelMail authenticated user kcheung) by pegasus.carleton.ca with HTTP; Mon, 10 Aug 2009 08:19:35 -0400 (EDT) Message-ID: <60096.70.26.45.246.1249906775.squirrel@pegasus.carleton.ca> In-Reply-To: <20090810.105950.42868244.garrigue@math.nagoya-u.ac.jp> References: <20090809183246.GB25629@happyleptic.org> <20090810.105950.42868244.garrigue@math.nagoya-u.ac.jp> Date: Mon, 10 Aug 2009 08:19:35 -0400 (EDT) Subject: Re: [Caml-list] ocamlgraph predecessors From: kcheung@math.carleton.ca To: caml-list@yquem.inria.fr User-Agent: SquirrelMail/1.4.8-4.0.1.el4 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-Spam: no; 0.00; node:01 functionnal:01 doubly:01 doubly:01 beginner's:01 ocaml:01 bug:01 carleton:98 cheung:98 beginners:01 caml-list:01 caml-list:01 bin:01 variant:02 arbitrary:02 Perhaps something like that in ConcreteBidirectional be implemented for general Digraph so predecessors can be accessed in O(1)? If I am not mistaken, that will double the storage and running time of most of the operations. This implementation could be added as an additional variant without modifying existing code. Kevin Cheung. > From: rixed@happyleptic.org >> > What you're asking is similar to the problem of finding the >> predecessor >> > of an arbitrary node in a singly-linked-list. You have no option but >> to >> > scan the whole list to find its predecessor. If you had a >> > doubly-linked-list, predecessor lookups would work easily, but that's >> a >> > different data structure, with much more overhead. >> >> Much more overhead, really ? >> So this is for performance reasons that all functionnal languages >> promote singly-linked lists, while for instance in Linux every list >> is implemented with a doubly linked list for purely ideological reasons >> ? >> >> :-) > > Yes indeed, much more overhead. But the source is not the fact you > have to maintain backlinks, but their impact on the GC. > With a GC, any modification on existing values has a cost, since you > have to keep track of them independently of the value itself. > Since linux has no GC, using doubly linked lists has only a very > limited cost, mostly related to the extra space needed. > By the way, BSD uses lots of singly-linked lists, probably because it > comes from a time when there was not so much memory. > > Jacques Garrigue > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >