By putting sub-functions in-line and then streamlining
the operations, the time and esp. the space have been
further reduced.
tsum3=: 4 : 0
d=. ((</[EMAIL PROTECTED]) y) -.&.> i=. ~.y
while. 1 do.
c=. #&>d
j=. (*c)#i
i=. c#i
e=. ;d
t=. i +//. e{x
if. 0 *./@:= t do. x return. end.
x=. (t+j{x) j}x
d=. i <@;/. (j i. e){d,a:
i=. j
end.
)
p =: p: inv 1+i.2e4
n =: 2e4 [EMAIL PROTECTED] 25
ts 'n tsum3 p'
0.0148536 1.67091e6
tsum3 readily handles non-trivial trees with a million nodes.
e.g.
m=: _1+2^20
n=: m [EMAIL PROTECTED] 20
p0=: p: inv >: i.m
p1=: 0,2#i.<.-:m NB. complete binary tree
ts 'n tsum3 p0'
1.1258 9.40344e7
ts 'n tsum3 p1'
4.1365 1.63629e8
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Wednesday, March 12, 2008 17:17
Subject: Re: [Jprogramming] tree sum and difference
To: Programming forum <[email protected]>
> 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
