9 jun 2009

# Tree Sum

## Alternate solution

In Essay/Tree Sum the tree sum problem and a few solutions are described.
From that page we take the definitions of testdata , tsum_des and tsum_dfs.

Another solution is presented here. It looks like tsum_des, but is more efficient. After adding the value of the children to the parent, a grandchild becomes a child.

```trsmB=: 4 : 0                   NB. x=v y=p
c=. i.# p=.y                   NB. child & parent
'p c'=. p (~: #"1 ,:) c        NB. no child of self
cp=. 1
v=. x
while. #cp do.
nbp=. ~.p
cpp=. p</.c                   NB. children per parent
v=. ((v {~ nbp) + (<v) +/@:{~&> cpp) nbp} v
cp=. c (e.#[) p               NB. children which are parent
'p c'=. (~:/ #"1 ]) (p {~ c i. cp) (;@] ,:~ (#~ #&>)) cpp {~ nbp i. cp
end.
v
)```

Let's check it on the first example in Essay/Tree Sum with p=: _1 p: i.15 and v=: 15 ?.@\$ 20 .
Notice however that  ?.  is changed since that essay was written, so  15 ?.@\$ 20  is no longer equal to  v=: 6 15 19 12 14 19 0 17 0 14  6 18 13 18 11  (but (in J602) to  14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 ).

```   v trsmB p
182 55 121 40 52 50 11 17 0 14 6 18 13 18 11```

OK, the answer is the same.

## Performance

Now what happens if we compare it performancewise with tsum_des on some heavy trees?

```   testdata 15          NB. to set pa, pb, pc and pd

[ tsB=:ts&.> 'v trsmB pa';'v trsmB pb';'v trsmB pc';'v trsmB pd'
+-------------------+-------------------+------------------+-------------------+
|0.032915806 6197376|0.090163334 9184384|1.3478651 13962752|0.60153995 11500032|
+-------------------+-------------------+------------------+-------------------+

[ tsH=:ts&.> 'v tsum_des pa';'v tsum_des pb';'v tsum_des pc';'v tsum_des pd'
+------------------+-------------------+------------------+-------------------+
|0.3601053 36491776|0.39932302 29075456|1.6973844 20277760|0.91604341 19062272|
+------------------+-------------------+------------------+-------------------+

tsH %&.> tsB
+-------------------+-------------------+-------------------+-------------------+
|10.940194 5.8882624|4.4288848 3.1657492|1.2593133 1.4522753|1.5228306 1.6575843|
+-------------------+-------------------+-------------------+-------------------+

tsH */@:%&.> tsB
+---------+---------+---------+-------+
|64.418733|14.020739|1.8288696|2.52422|
+---------+---------+---------+-------+

('v trsmB pa';'v trsmB pb';'v trsmB pc';'v trsmB pd')-:&(".&.>)'v tsum_des pa';'v tsum_des pb';'v tsum_des pc';'v tsum_des pd'
1 1 1 1```

So not only does the output match, trsmB is also (much) more efficient.

How about tsum_dfs which is only not so efficient on skinny trees?

```   [ tsH2=:ts&.> 'v tsum_dfs pa';'v tsum_dfs pb';'v tsum_dfs pd'
+--------------------+-------------------+------------------+
|0.0070383532 3741440|0.008948664 3741440|0.22297881 3217152|
+--------------------+-------------------+------------------+

tsH2 */@:%&.>~ 1 1 0 1 # tsB
+--------+---------+---------+
|7.746446|24.733354|9.6433594|
+--------+---------+---------+

('v trsmB pa';'v trsmB pb';'v trsmB pd')-:&(".&.>)'v tsum_dfs pa';'v tsum_dfs pb';'v tsum_dfs pd'
1 1 1```

And so tsum_dfs remains the best for shallow trees.

# Reversed Tree Sum

## Description

But the real reason is I want a tree sum the other way around, where a node gets the value of all its ancestors.
I will denote these verbs with a starting r, like rtrsmB etc.

Let me explain this with the example in the second box in Essay/Tree Sum.

```                                        ┌─ 6  ( 0 33) ─── 14 (11 44)
┌── 1 (15 21) ─── 3 (12 33) ─┴─ 7  (17 50)
│                            ┌─ 8  ( 0 39)
─ 0 (6 6) ─┤              ┌─ 4 (14 39) ─┼─ 9  (14 53)
│              │             ├─ 10 ( 6 45)
└── 2 (19 25) ─┤             └─ 11 (18 57)
│             ┌─ 12 (13 57)
└─ 5 (19 44) ─┴─ 13 (18 62)```

In the diagram above, each node is labelled with its index, value, and the sum of self + ancestors.

Here is rtrsmB :

```rtrsmB=: 4 : 0                  NB. x=v y=p
c=. i.# p=.y                   NB. child & parent
'p c'=. p (~: #"1 ,:) c        NB. no parent of self
pc=. 1
v=. x
while. #pc do.
v=. ((v {~ c) + v {~ p) c} v
pc=. p #~ t=. p e. c          NB. parents which are child
'p c'=. (t # c) ,:~ p {~ c i. pc
end.
v
)

v=: 6 15 19 12 14 19 0 17 0 14  6 18 13 18 11
p=: _1 p: i.15
v rtrsmB p
6 21 25 33 39 44 33 50 39 53 45 57 57 62 44```

The analogue of tsum_dfs is rtsum_dfs .

```rtsum_dfs=: 4 : 0
e=. y (~: #"1 ,:) i.#y
while. {:\$e do.
b=. e./e
'p q'=. (-.b)#"1 e
e=. b#"1 e
x=. ((q{x)+ p{x) q}x
end.
x
)

v=: 6 15 19 12 14 19 0 17 0 14  6 18 13 18 11
p=: _1 p: i.15
v rtsum_dfs p
6 21 25 33 39 44 33 50 39 53 45 57 57 62 44```

## Performance

Comparing performances gives

```   testdata 15

[ tsH3=:ts&.> 'v rtsum_dfs pa';'v rtsum_dfs pb';'v rtsum_dfs pd'
+-------------------+-------------------+------------------+
|0.018521856 3740800|0.026874537 3740800|0.20366136 3216512|
+-------------------+-------------------+------------------+

[ tsB1=:ts&.> 'v trsmB pa';'v trsmB pb';'v trsmB pd'
+-------------------+-------------------+-------------------+
|0.032174045 6197376|0.089608716 9184384|0.57779459 11500032|
+-------------------+-------------------+-------------------+

tsH3 */@:%&.>~  tsB1
+---------+---------+---------+
|2.8778259|8.1864347|10.143287|
+---------+---------+---------+

('v rtsum_dfs pa';'v rtsum_dfs pb';'v rtsum_dfs pd')-:&(".&.>)'v rtrsmB pa';'v rtrsmB pb';'v rtrsmB pd'
1 1 1

ts'v rtrsmB pc'
0.09002895 7411712

ts'v rtsum_dfs pc'
22.587198 3740800```

So also here rtsum_dfs is faster for non skinny trees and a lot slower for skinny ones.

# Collected definitons

```trsmB=: 4 : 0                                   NB. x=v y=p
c=. i.# p=.y                                   NB. child & parent
'p c'=. p (~: #"1 ,:) c                        NB. no child of self
cp=. 1
v=. x
while. #cp do.
nbp=. ~.p
cpp=. p</.c                                   NB. children per parent
v=. ((v {~ nbp) + (<v) +/@:{~&> cpp) nbp} v
cp=. c (e.#[) p                               NB. children which are parent
'p c'=. (~:/ #"1 ]) (p {~ c i. cp) (;@] ,:~ (#~ #&>)) cpp {~ nbp i. cp
end.
v
)

rtrsmB=: 4 : 0                                  NB. x=v y=p
c=. i.# p=.y                                   NB. child & parent
'p c'=. p (~: #"1 ,:) c                        NB. no parent of self
pc=. 1
v=. x
while. #pc do.
v=. ((v {~ c) + v {~ p) c} v
pc=. p #~ t=. p e. c                          NB. parents which are child
'p c'=. (t # c) ,:~ p {~ c i. pc
end.
v
)

rtsum_dfs=: 4 : 0
e=. y (~: #"1 ,:) i.#y
while. {:\$e do.
b=. e./e
'p q'=. (-.b)#"1 e
e=. b#"1 e
x=. ((q{x)+ p{x) q}x
end.
x
)```

From Essay/Tree Sum#CollectedDefinitions (as per jun 11 09)

```testdata=: 3 : 0
m =: _1+2^y
v =: m ?@\$ 20
pa=: _1 p: i.m
pb=: 0,2#i.<.m%2                           NB. complete binary tree
pc=: 0>.<:i.m                              NB. tall skinny tree
pd=: m (\$,) (c*i.c) ([,.+/) i.<:c=. <.%:m  NB. forest
i.0 0
)

am   =: i.@,~@# e. # #. ] ,. i.@#
rc   =: +. =@i.@#
tc   =: +./ .*.~^:(2>.@^.#)
tsum_mat=: tc@rc@am@] +/ .* [

sons =: (~. i. i.@#) { a: ,~ (</. i.@#)
gen  =: 3 : '(*c) #^:_1 (I.c) <@;/. (;y){y [ c=. #&> y'
ad   =: 4 : '(*c) #^:_1 (I.c)  +//. (;y){x [ c=. #&> y'

tsum_des=: 4 : 0
x=. x + t=. x ad d=. (sons y) -.&.> i.#y
while. 0 +./@:~: t do. x=. x + t=. x ad d=. gen d end.
)

tsum_dfs=: 4 : 0
e=. y (~: #"1 ,:) i.#y
while. {:\$e do.
b=. e.~/e
'p q'=. (-.b)#"1 e
j=. ~.p
x=. ((j{x)+p+//.q{x) j}x
e=. b#"1 e
end.
x
)             ```

RE Boss/J-blog/TreeSum (last edited 2009-06-11 19:28:24 by RE Boss)