ARTS - week 2

Algorithm

题目链接

112. 路径总和 - 力扣（LeetCode） (leetcode-cn.com)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

题目解析

宽度优先搜索，从根节点开始，记录从根节点到当前节点的和，如果同时为叶子节点并且等于目标值，则为 true, 否则 false

代码实现

    bool hasPathSum(TreeNode* root, int targetSum) {        queue<pair<TreeNode*, int>> que;         if(root == nullptr){            return false;        }        que.emplace(root, root->val);        while(!que.empty()){            TreeNode* curr_node = que.front().first;            int curr_val = que.front().second;            que.pop();            if(curr_node->left == nullptr && curr_node->right == nullptr && curr_val == targetSum){                return true;            }             if(curr_node->left != nullptr){                que.emplace(curr_node->left, curr_val + curr_node->left->val);            }            if(curr_node->right != nullptr){                que.emplace(curr_node->right, curr_val + curr_node->right->val);            }        }        return false;    }

Review

（正常字体为原文中我觉得比较好的内容，斜粗体为本人观点）

本文斜体部分主要参考 “Hands on Machine Learning with Ski-learn, Keras and Tensorflow”2nd version

https://www.easy-tensorflow.com/tf-tutorials/basics/graph-and-session?view=article&id=50:why-python 该文章介绍了 tensorflow graph 和 session 机制。graph 和 session 属于 tensorflow 很关键的特性，是 lazy computing 和高效训练的关键。搞不懂这两个概念，读起 TensorFlow 代码会头大，一如作者本人。这篇文章没有追求很多细节，但是把核心概念讲的非常清楚，给出的代码、图片示例也很清晰，非常值得作为入门阅读。

graph 以及 session 的目的

通过 graph 和 session 的结合，可以支持 lazy computing 机制（通过 graph 来描述计算和 data 的流动，只在 session run 的时候进行真正的计算），并且能够提供计算的灵活性（即只计算和输出相关的部分，不用计算全部内容，从而提高效率）。

graph

graph 代表数据流动的方式，在 TF 工具中，命名为 tensor,这也是 tensorflow 这个名称的由来。

computation graph 是一系列的 TensorFlow operations, 其中节点表示操作，边来表示数据（Tensor）的流动，一个简单的示例如下

graph 可以将不同的节点作为输出，并且通过 tf 本身优化，只找出和该输出相关的 operations, 从而可以提供灵活性，只计算想要计算的 graph 部分，不用执行全部的操作，一句话，“不用为了买牛奶而买下一头牛”。

用一个比喻来说，tf graph 像是 python 中的函数定义，仅仅是定义了如何对数据进行操作，但是真正执行，是在调用函数的时候，在 tensorflow 也就是 session run 的时候。

trace 机制

从代码到 graph 通过两个过程来完成，首先是 autograph, 将所有操作转换为 tf operations; 接下来是 trace 机制，给一个没有值的变量（symbollic value），通过 autograph 构建代码，来完成 graph 的构建。

此处注意，尽管 print, logging, np.ramdom(), a+=1 等操作在 trace 的过程中会操作，但是仅限于 trace 过程，真正 session run 的时候不被包含；tensorflow 在构建 graph 的时候，只会包含 tensorflow 自己定义的操作。python 自带的一些原生操作不会包含进去，例如 range, sum, sorted 等，可以替换为 tf.range, tf.reduce_sum(), tf.sort(), 一些日志，python 计数也不会放置于 graph 里面。

session

通过运行一个 session, sess.run() 来执行 graph 中的操作,完成真正的计算。

很重要的点：session 在执行的过程中，会根据你定义的 output 以及预先定义的 graph，计算出需要执行的节点，而不是整个计算图都需要跑一遍，因此提供了极大的灵活性，也节省很多计算量。以下图为例，如果 output 仅仅包含 power, 那么 useless 那个分支的操作将不会执行。

此处再次提醒，只有 tf 本身的函数才会在这个阶段执行，一些打印变量的东西

Tips

介绍两个 python 性能分析工具，本周主要介绍两个分析运行时间的工具，下周会介绍内存占用的工具

cProfile 定位最耗时函数

cProfile 是标准库内建工具，测量每个函数运行时间以及调用次数。注意，cProfile 会有开销，比真正运行速度要慢许多，但是考虑能定位 bottleneck, 总体而言花这点时间是值得的。

用法

python -m cProfile -s cumulative <target_program.py>

-s cumulative 开关告诉 cProfile 对每个函数累计花费的时间进行排序，这能让我们看到代码最慢的部分。

如果需要单独分析，也可以将结果输出到一个统计文件，后续通过 python 进行分析，用法如下

python -m cProfile -o <profile.stats> <target_program.py>

python 对其解析并分析的示例,用该方法可以获得和上文命令一样的输出信息

import pstatsp = pstats.Stats("profile.stats")p.sort_stats("cumulative")p.print_stats()

通过 cProfile，可以定位到那个函数耗时最多，但是如果具体到该函数哪一行，除了对每行打印 time.time(), 更加便利的方法就需要 line_profiler 出场了。

line_profiler 对函数进行逐行分析，找到瓶颈

line_profiler 非内建库，需要手动安装

pip install line_profiler

通过 cProfile 定位到某个函数后，只需在该函数前加 @profile 装饰器，就可以标定选中的函数。通过运行命令

kernprof -l -v <target_program.py>

即可运行，会输出选定函数每行的 hits, per hits 时间以及在整个函数中的运行时间占比，非常好用。

（注意，上述版本为 python3, python2 需要加 py 后缀，即 kernprof.py -l -v<target_program.py>）

Share

今天我想分享的观点是关于软件工程中工时分析的。该观点是从学习 python 性能优化工具那里得来的，

我的观点是，我们也可以将 cProfile 方法运用到软件工程中的工时分析当中，即将任务进行拆解，对每个模块进行一个时间预估，并且在开发过程中对真正的耗时进行记录，项目结束后进行复盘，找到最耗时的任务，看看自己的预估有多不靠谱，是哪里出了问题，什么没有考虑到，随着经验积累，应该能够有更好的预估能力，任务排期也会更合理。具体内容详见链接 https://xie.infoq.cn/article/e75fef0a07b8902274d7ee916