Re: [Caml-list] ocamlgraph predecessors

[kcheung@math.carleton.ca]

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
>