[Jprogramming] tree sum and difference

[Roger Hui]

There are other ways to avoid transposing the matrix
which are even more efficient:

   10 ts 'M +/"1@:*"1 cm'
0.0437692 55296
   10 ts 'M +/ .*|:cm'
0.193762 1.67953e7
   10 ts 'cm +/ .* M'
0.0253117 17600

But for efficiency sufficient to handle tens of thousands
or millions of nodes, you have to avoid explicitly generating
the matrix.  Dealing with an (n,n) connection matrix is a 
non-starter when n is like 1e6, especially when it is sparse 
(as it would be for a tree).




----- Original Message -----
From: Arie Groeneveld <bradypus at xs4all.nl>
Date: Wednesday, March 12, 2008 6:33
Subject: Re: [Jprogramming] tree sum and difference
To: Programming forum <programming at jsoftware.com>

> M=:?.100+i.3000
> P=:p:inv 1+i.3000
> 
> Not a big deal, but:
> 
> separating structure (connection matrix) from calculating sums:
> 
> cm=:connmat P
> 
>    10 ts 'M +/"1@:*"1 cm'
> 0.0573582 55296
> 
>    10 ts 'M +/ .*|:cm'
> 0.1671801 16795264
> 
> trees1=:+/"1@:*"1 connmat
> 
>    n(trees1-:treesum)parents
> 1
>    M(trees1-:treesum)P
> 1
> 
> 
> Raul Miller schreef:
> > So, let's say that I have a tree structure where 0
> > is the parent of all other nodes
> >    parents=: p:inv 1+i.10
> > and that I have some numbers associated with
> > the nodes of this tree
> >    n=: ?.100+i.10
> >
> > I can produce a tree-wise sum, for example:
> >    connmat=:3 :'(e."0 1/ [:|:{&y^:a:)i.#y'
> >    treesum=: +/ .* |:@connmat
> >    parents,n,:n treesum parents
> >   0   0   1   
> 2   2 3  3  4  4  4
> >  46  25 101  69 102 9 58 45 40 64
> > 559 513 488 136 251 9 58 45 40 64
> >
> > I can also find the tree-wise difference, for example:
> >    treediff=: %. connmat
> >    559 513 488 136 251 9 58 45 40 64 treediff parents
> > 46 25 101 69 102 9 58 45 40 64
> >
> > However, it seems that there ought to be faster
> > approaches for large trees (with hundreds or
> > thousands of nodes).
> >
> > So, since some people like puzzles, can anyone
> > come up with faster implementations for treesum
> > and treediff, for large trees?