Another factor of 3 or so by making a similar improvement
to sd. Thus:
sons=: (~. i. [EMAIL PROTECTED]) { a: ,~ (</. [EMAIL PROTECTED])
gen =: 3 : '(*c) #^:_1 (c#i.#y) <@~.@;/. (;y){y [ c=. #&> y'
sd =: 4 : '(*c) #^:_1 (c#i.#y) +//. (;y){x [ c=. #&> y'
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.
)
p=: p: inv 1+i.2e4
n=: 2e4 [EMAIL PROTECTED] 25
ts 'n tsum p'
0.172833 1.07744e7
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Wednesday, March 12, 2008 17:04
Subject: Re: [Jprogramming] tree sum and difference
To: Programming forum <[email protected]>
> 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
