On the large example, a factor of about 500 improvement
obtains by speeding up a key component:
gen=: 3 : 0
c=. #&> y
(*c) #^:_1 (c#i.#y) <@~.@;/. (;y){y
)
ts 'n tsum p'
0.622585 1.27693e7
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Wednesday, March 12, 2008 15:21
Subject: Re: [Jprogramming] tree sum and difference
To: Programming forum <[email protected]>
> sons=: (~. i. [EMAIL PROTECTED]) { a: ,~ (</. [EMAIL PROTECTED])
> gen =: ([: <@~.@; >@[ { ])"0 1~
> rc =: [EMAIL PROTECTED] ~.@,&.> ]
> rtc =: gen^:_ @ rc @ sons
>
> sd =: (>@] +/@:{ [)"_ 0
>
> tsum=: 4 : 0
> z=. x + t=. x sd d=. (sons y) -.&.> i.#y
> while. +./0~:t do.
> z=. z + t=. z sd d=. gen d
> end.
> )
>
> "sons" computes the list of sons from the parents.
> "rc" computes the reflexive closure. "gen" computes
> the next generation of descendants from the current
> generation. "rtc" computes the reflexive-transitive
> closure.
>
> "tsum" adopts and adapts the transitive closure logic.
> It computes successive generations of descendants
> (pronoun d) and adds their sums to the total.
>
> p=: p: inv 1+i.100
> n=: 100 [EMAIL PROTECTED] 25
> (n treesum p) -: n tsum p
> 1
> ts 'n treesum p'
> 0.000604717 34048
> ts 'n tsum p'
> 0.00328381 56320
>
> p=: p: inv 1+i.2e4
> n=: 2e4 [EMAIL PROTECTED] 25
> ts 'n tsum p'
> 301.378 1.27693e7
>
> For small sets of nodes, the connection matrix approach
> is more efficent. For large sets the situation changes.
> In the last example, *:#n is 4e8 so the connection matrix
> approach would require at least that much space.
>
>
>
> ----- Original Message -----
> From: Raul Miller <[EMAIL PROTECTED]>
> Date: Tuesday, March 11, 2008 12:57
> Subject: [Jprogramming] tree sum and difference
> To: Programming forum <[email protected]>
>
> > 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
