Chpater3 今天来学习画一棵树（IV）浅谈效能和演算法，以迭代取代递回吧！

昨天发完文後，觉得对於演算法还是心有不甘，便上网搜寻了一下，虽然没直接给到答案，间接的给了我一些大胆的想法。

具体参考的是这篇：
https://ithelp.ithome.com.tw/articles/10231115
而当下的我了一个很草率的结论：迭代的效能比递回好

说回迭代(for)

在树的开篇有提到使用递回的原因是一般的回圈做不出树状结构，但是效能上却有瓶颈，接着我就意识到，先前的作法根本是「为了递回而递回」，我们只是需要透过树状结构来指定父子关系，那为什麽每次更新（渲染绘图）的时候都还要跑递回呢？

因此我的思路是，把需要递回的放在建构式里面，其他则透过跑回圈的方式，於是，简化了一开始的流程，分别只对树根Tree进行定位，对於树枝Stick只提供长度跟角度，接着在这个过程中把树状图给扁平化，把众树枝们放到treeNodes里面。

let treeNodes = [];
let Tree = function(x, y, r, theta, times){
    treeNodes = [this];
    this.startX = x;
    this.startY = y;
    this.endX = x + r * Math.cos(theta / 180 * Math.PI);
    this.endY = y + r * Math.sin(theta / 180 * Math.PI);
    this.r = r;
    this.theta = theta;
    this.grow = 0;
    let shrink = 0.65 + random(0.1);
    let diff = random(0.3) - 0.15; // +-0.15
    this.son = [new Stick(this, (shrink - diff), 30 * (a+b+1), times - 1),
                new Stick(this, (shrink + diff), 30 * (a-b-1), times - 1)];
}
let Stick = function(father, shrink_diff, angleOffset, times){

    this.father = father;
    this.r = this.father.r * (shrink_diff);
    this.theta = this.father.theta + angleOffset;
    this.grow = 0;
    treeNodes.push(this);
    if(times > 0){
        let shrink = 0.65 + random(0.1);
        let diff = random(0.3) - 0.15; // +-0.15
        this.son = [new Stick(this, (shrink - diff), 30 * (a+b+1), times - 1),
                    new Stick(this, (shrink + diff), 30 * (a-b-1), times - 1)];
    }
}

於是，在物件实例化的过程中，我们就拿到了treeNodes

里面有三处标记，说明一下：

1. treeNodes[0]是一开始放进去的Tree物件
2. Tree有两节子树枝，其中一枝和它後面2^9的子子孙孙都会排序其後
3. 右下角显示该树枝没有子代，表示到treeNodes[10]实际上已经递回10次

然後就可以把每一侦都要跑的，原本递回写法Transform和Draw通通改成for回圈，这边和之前主要的差异在於，之前要用this，现在用node = treeNodes[N]，和判断树枝在左侧或右侧。

Tree.prototype.Transform = function(){
    let a = myMouse.pointX;
    let b = myMouse.pointY;
    for(let N = 1; N < treeNodes.length; N++){
        let node = treeNodes[N];
        let index = node.father.son.indexOf(node);
        let parameter = ((index == 0)?(a+b+1):(a-b-1));
        // if(index == 0) console.log(0);
        // else console.log(1);
        node.theta = node.father.theta + 30 * parameter;
        // 已知father, r, theta 三个参数，透过father取得座标後进行计算
        let x = node.father.endX;
        let y = node.father.endY;
        let r = node.r;
        let theta = node.theta;
        node.startX = x;
        node.startY = y;
        node.endX = x + r * Math.cos(theta / 180 * Math.PI);
        node.endY = y + r * Math.sin(theta / 180 * Math.PI);
    }
};
Tree.prototype.Draw = function(){
    for(let N = 1; N < treeNodes.length; N++){
        let node = treeNodes[N];
        let x = (node.startX - WIDTH/2) * node.grow + WIDTH/2,
            y = (node.startY - HEIGHT)* node.grow + HEIGHT,
            r = node.r * node.grow,
            theta = node.theta;
            
        context.beginPath();
        context.moveTo(x, y);
        context.lineTo(x + r * Math.cos(theta / 180 * Math.PI),
                       y + r * Math.sin(theta / 180 * Math.PI));
        context.lineWidth = 1 + r/50;
        context.strokeStyle = 'rgba(179, 198, 213, 1)';
        context.stroke();
        
        node.grow = Math.min(node.grow + 0.01 / (0.8 + 2 * node.grow), 1);
    }
};

值得一提的是父子之间一定有前後顺序，不一定相邻，但是父树枝一定在阵列比较前面的地方，因此不必担心父树枝的座标未经演算，就被子树枝拿去作使用，这也是扁平化的时候就要先设计好的。

效能有变好吗

稍作体感上有感受到很微妙的差异，CPU则同样在50%~80%之间

（五年老笔电i7-6700）

後来再回去拜读了一下开头贴的文章，发现它谈论的只是如何让递回的Stack不要爆炸（记忆体超过最大限制），所以严格来说虽然有优化，因为不会占用记忆体空间，不过运算树的座标本身还是需要演算的时间，要求1秒60侦，也就是每16豪秒计算一次，算是要求相当高，对CPU的负荷仍不会少。

同样以prototype的写法来执行一次完整的动画：

• 　原本需要5.88~7.90毫秒不等（极少数有超过8毫秒）
• 今天则需要4.47~6.84毫秒不等（极少数有7~10毫秒）

不过原本的是在github.io上做测试，今天的在本地端做测试，可能会有些许误差

结论

我对资料结构还不够熟悉，等系列文结束之後再来慢慢研究迭代跟递回吧！
不过针对演算的时间，我们理论上应该还是可以透过减少浮点数的运算，来让程序效率更佳，到时候该做的还是逃不掉！

後记

结果又没时间美化树枝了XDD，本着程序越复杂之後越难改的心情，先跑回来重写递回，果然还是没那麽容易呢！而且今天白天跑去爬柴山了，回来整个动弹不得Ww，差点没睡死在床上，原本也想仔细解释上面程序码在写什麽，不过时间不太够了，如果有需要的话，留言跟我说，再补充。