A solution based on the depth first search idea.
In each iteration, tree sums for the leaves
are added to the parents and then the leaves
are removed. The iteration terminates when
no edges remain.
tsum_dfs=: 4 : 0
e=. (~:/ #"1 ]) y,:i.#y
while. */$e do.
b=. -. ({:e) e. {.e NB. leaves
'p q'=. b#"1 e
j=. ~.p
x=. ((j{x)+p+//.q{x) j}x
e=. (-.b)#"1 e
end.
x
)
This solution is faster than the others for
trees that are shallow relative to the number
of nodes (say, logarithmic depth), and less
so for tall trees. e.g.
dataset=: 3 : 0
m =: _1+2^y
v =: m [EMAIL PROTECTED] 20
pa=: _1 p: i.m
pb=: 0,2#i.<.m%2 NB. complete binary tree
pc=: 0>.<:i.m NB. very skinny tall tree
i.0 0
)
dataset 14
$v
16383
v (tsum3 -: tsum_dfs) pa
1
v (tsum3 -: tsum_dfs) pb
1
v (tsum3 -: tsum_dfs) pc
1
ts 'v tsum3 pa'
0.0120516 1.53261e6
ts 'v tsum_dfs pa'
0.00205934 953280
ts 'v tsum3 pb'
0.0484006 2.55827e6
ts 'v tsum_dfs pb'
0.00333292 953280
ts 'v tsum3 pc'
0.394279 3.86906e6
ts 'v tsum_dfs pc'
2.69195 953280
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Friday, March 14, 2008 7:15
Subject: Re: [Jprogramming] tree sum and difference
To: Programming forum <[email protected]>
> In scalar-oriented languages an efficient way to solve this
> problem can be described in 3 words: depth first search.
> That is:
>
> treesum(x) is
> - value(x) if x is a leaf
> - value(x) + +/ treesum"0 (sons of x) if not
>
> The time and space should be within a small factor
> of the time and space to do +/\values , which none of the
> solutions mentioned so far comes near.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
