Re: how to suppress carefully a recursive tree

On 23 jan, 16:35, fj <francois.j...@xxxxxxx> wrote:
On 23 jan, 14:32, David BL <davi...@xxxxxxxxxxxx> wrote:



On Jan 23, 4:10 pm, fj <francois.j...@xxxxxxx> wrote:

On 23 jan, 01:12, David BL <davi...@xxxxxxxxxxxx> wrote:

On Jan 23, 1:10 am, fj <francois.j...@xxxxxxx> wrote:

On 22 jan, 15:52, Jan Hidders <hidd...@xxxxxxxxx> wrote:

On 22 jan, 12:04, fj <francois.j...@xxxxxxx> wrote:

I know how to suppress a normal tree but I meet the following kind of
situation :

I'm guessing that when you say "suppress" you mean "represent in a
database". Correct?

No : I want to destroy, remove, kill ... a part of the data (a
complete tree or just a branch), but without destroying data shared by
other trees or branches.

Would the mark and sweep algorithm suit you purposes?

No

the mark and sweep algorithm needs to know all the tree roots in order
to mark all the used objects.

In my example I indicates that the node b3 belongs to the root r2
just for information to explain the storage count. But the deletion
routine I want to write just receives "r1" as argument, nothing else.
It does not know that r2 exists too ... It is just able to detect the
existence of other objects via the storage count of b3 which is a
little bit too high for being just referenced by r1 !

For a directed edge from node n1 towards node n2, let n2 be referred
to as the "destination" node.

n1 ---->---- n2
source destination

Maybe the following approach would work:

It is assumed that node r1 is the root of the "tree" to be deleted.

Step 1: Perform a trace (in the manner of a mark phase) treating r1
as the one and only root and decrementing the storage counter on the
destination node for each edge that is traversed. ie find the set X
of nodes that are reachable from r1. Nodes that have already been
visited are flagged to ensure each reachable node is visited exactly
once. For each node during the recurse, retrieve the set of outgoing
edges yielding a set of destination nodes. Decrement each destination
node's storage counter (this must be done for all the destination
nodes - ie including the nodes that have already been visited). Then
recurse into the destination nodes that haven't been visited before.

Step 2: Find the subset R of X corresponding to nodes whose storage
counter hasn't fallen to zero.

Step 3: Run a mark and sweep using roots R and sweeping over X. For
each edge traversed in the mark phase, increment the storage counter
on the destination node.

In your example I think step 1 will find X = {r1,b1,b2,b3,b4} and only
b3 will end up with a nonzero storage counter, so step 2 yields R =
{b3}. Then in step 3, a trace from roots {b3} will bump the storage
counter of b4 back up to 1 and only {r1,b1,b2} will be deleted.

Am I making sense?

Yes.

I was arrived to a very similar solution as I explained in my second
message. Nevertheless, several steps are expensive, especially if I
suppose forbidden to add new pieces of information in the nodes
themselves : only the creation a new local tables of linked lists is
authorized. For instance :

- in the step 1, flagging a visited node to avoid recursion might be
expensive. At the moment, I create a linked list of nodes in
traversing the sub-tree. So when I visit a node then I start by
looking for it in the linked list. This simple research is expensive
(cost in O(n2) if n is the number of nodes in the subtree). If the
node is not found, then I add a new term in my linked list which
contains the node index and its storage count minus 1 (at the end,
this count will be the external count). If I find it then I just
decrement the external count in the found term.

- the step 2 is OK (cost in O(n))

- the step 3 may be expensive too (all depends on the number of nodes
with an external count greater that 0).

In my solution, the step 3 was replaced by traversing again the tree
from r1 and going down a node only if its external count is equal to
zero. During this step, the true storage count of nodes is decremented
and nodes with a count equal to zero are destroyed. But this solution
has again a drawback : looking for the current visited node in the
linked list in order to get its external count. A possible improvement
was to create a new field in each node used to store the external
count there rather than in a parallel linked list.

Another solution might be to create an array which size is the total
number of nodes. This array will replace the linked list. The
advantage is clear : looking for the external count in this array is
immediate, the node index corresponding to the array index. The
drawback is the size of the array, the total number of nodes being
potentially huge ( > 1 million) whereas the number of nodes in a
deleted branch is generally several orders of magnitude lower (but
often greater than 1000).

Oups ! I think that the main drawback is the fact that this solution
does not work correctly !
So the step 3 of David is much better !

After looking for GC on internet, I found the Python GC uses a
technique similar to the David's solution


An intermediate solution consists in using an extensible hash
table ...

In any case, I would like a solution in O(n) else such algorithm is
not tractable.

.

Relevant Pages

  • Re: how to suppress carefully a recursive tree
    ... just for information to explain the storage count. ... as the one and only root and decrementing the storage counter on the ... destination node for each edge that is traversed. ... I would avoid linked lists. ...
    (comp.databases.theory)
  • Re: how to suppress carefully a recursive tree
    ... just for information to explain the storage count. ... as the one and only root and decrementing the storage counter on the ... destination node for each edge that is traversed. ... I would avoid linked lists. ...
    (comp.databases.theory)
  • Re: how to suppress carefully a recursive tree
    ... just for information to explain the storage count. ... Perform a trace (in the manner of a mark phase) treating r1 ... destination node for each edge that is traversed. ... only the creation a new local tables of linked lists is ...
    (comp.databases.theory)
  • Re: how to suppress carefully a recursive tree
    ... to mark all the used objects. ... just for information to explain the storage count. ... destination node for each edge that is traversed. ... a trace from roots will bump the storage ...
    (comp.databases.theory)
  • Re: Along a similar vein (Was Re: hash of hashes with lists)
    ... > I could use a variant of an online merchant form, ... session information to be carried from request to request, ... but you do not want to use storage. ... if your question is really about linked lists, the read the FAQ, ...
    (comp.lang.perl.misc)