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 <[EMAIL PROTECTED]> Date: Wednesday, March 12, 2008 6:33 Subject: Re: [Jprogramming] tree sum and difference To: Programming forum <[email protected]> > 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? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
