p =: p: inv 1+i.2e4
n =: 2e4 [EMAIL PROTECTED] 25
ts'n tsum3 p'
0.017312542 1670912
ts'n tsum4 p'
0.0089138557 789888
n (tsum3-:tsum4) p
1
m=: _1+2^20
n=: m [EMAIL PROTECTED] 20
p0=: p: inv >: i.m
p1=: 0,2#i.<.-:m NB. complete binary tree
n (tsum3-:tsum4) p0
1
n (tsum3-:tsum4) p1
1
ts'n tsum3 p0'
1.2542457 94034368
ts'n tsum4 p0'
1.0701561 1.3422765e8
ts'n tsum3 p1'
4.3480865 1.6362938e8
ts'n tsum4 p1'
1.4879192 1.4261466e8
tsum4 is still a test version which I will post asap.
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [EMAIL PROTECTED] [mailto:programming-
> [EMAIL PROTECTED] Namens Roger Hui
> Verzonden: donderdag 13 maart 2008 7:44
> Aan: Programming forum
> Onderwerp: Re: [Jprogramming] tree sum and difference
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
