Open youngwind opened 7 years ago
@shadeofgod 已更新完毕。
看jsperf的图愣了一下,应该是单位时间内的运算次数成10倍,100倍下降,运算时间是增长的吧。 有点容易引起困惑。
@shadeofgod 此处确实写得不对,多谢指出,已更正。
preact的出现是为了解决了什么问题呢?单纯只是一个精简版的React吗?
看起来是的,你看官网都这么说。 @MrErHu
Fast 3kB alternative to React with the same ES6 API
@youngwind 那两者内部实现的方式差异大吗?
@MrErHu Preact除了只是实现一个精简版的React之外,内部还做了很多的hack,提升了较大的性能,虽然没有React的体系那么庞大,比如没有event system, 但是总体的经常使用的核心API是一致的,加之体积比较小,在一定的程度上更加利于移动端的使用场景,具体内部的实现差异不是很大,preact在内部的diff算法和react部部分不同,生命周期函数内部唤起的机制也有所不同,针对text node做了很多的优化。 我自己分析过preact的源码,通过注释的形式分析的, 需要的话你可以看看 preact_analyse
@wangning0 解释的真不错,谢谢了~去了解一下
动态规划,对于两个串,"abcdef" -> "abccde" 求出最小距离是2之后,react还需要如何判断移动哪些字符呢?
*空 a b c d e f 空 0 1 2 3 4 5 6 a 1 0 1 2 3 4 5 b 2 1 0 1 2 3 4 c 3 2 1 0 1 2 3 c 4 3 2 1 1 2 3 d 5 4 3 2 1 2 3 *e 6 5 4 3 2 1 2
肉眼判断肯定是把abcdef中间插入c,末尾移除f,就可以转成abccde 程序怎么写?
动态规划和分治法(使用递归)的最大区别应该是子问题是否重叠,动态规划应用于子问题重叠(意味着可以使用缓存),而分治法子问题互不相交。
动态规划的两个特性:最优子结构和重叠子问题; 你的递归方法进行简单的修改也可以变为动态规划,它其实是自顶向下的求解问题,在递归到达递归边界时出栈并进行问题的计算,但是你没有对子问题进行缓存查询的逻辑,只是单纯的递归了; 你的动态规划方法,它其实是自底向上求解问题,对子问题进行了缓存和查询的逻辑;
@demonbibi 说的没错,画一个递归的图,就可以看出比如i-1,j-1的情况算了三次, 时间复杂度:动态规划优于递归
继上一篇 #104 ,本来是在研究虚拟 DOM 算法的,看到了 livoras 的这篇文章,觉得写得很好!珠玉在前,我便不再赘述了。该文章中提到:列表更新本质上是一个最小编辑距离问题,不过并未就此详细展开。今天,我们来具体看看这个问题。
问题
给定两个字符串 a 和 b,只允许以下三种操作:
求:把 a 转换成 b 的最小操作次数,也就是所谓的最小编辑距离。 举例: "xy" => "xz",只需要把 y 替换成 z,因此,最小编辑距离为 1。 "xyz" => "xy",只需要删除 z ,因此,最小编辑距离为 1。
求解这个问题,一般有两种思路:递归和动态规划。
递归
所谓递归,便是把大问题”分治“成类似的小问题。 假设,a 的长度是 m,b 的长度是 n,要求 a[1]a[2]...a[m] => b[1]b[2]...b[n] 的最小编辑距离,记为 d[m][n]。
代码实现
动态规划
动态规划看起来跟递归很像,不过推理逻辑正好是反过来的。递归的逻辑是:“要求得 d[m][n],先要求得 d[m-1][n-1]……”,动态规划的逻辑是:“先求得 d[m-1][n-1],再求 d[m][n]……”这是它们的主要区别。 举个例子,在已知 d[0][0],d[0][1],d[1][0] 的前提下,要求 d[1][1]:
接着用同样的方式,可以求得 d[1][2]、d[1][3]、……、d[1][n],然后继续求得 d[2][1]、d[2][2]、……、d[2][n],一直到 d[m][n]。代码实现如下:
对比与实证
这两种算法哪一个更快呢? 我不知道如何从理论上去计算其时间复杂度和空间复杂度,因为对于复杂度的计算,我只能应付那种简单的,比如 n 重循环,我知道其时间复杂度是 n 次方。但是,对于这种稍微复杂一些的程序,我便不知所措了。 怎么办呢? → 我决定从实证的角度去得到答案,也就是说,通过实际测量程序的运行时间,来衡量其时间复杂度。 我使用 jsPerf,建了一个 Test Case,从链接进去点击“Run Tests”,稍等片刻,便能看到程序运行的速度(指标 ops/sec 为 1s 内程序重复执行次数,数值越高代表程序运行越快),具体执行结果如下图所示。
从图中我们可以看到:递归的时间复杂度是指数级的,动态规划的时间复杂度是线性级的。
为什么动态规划快那么多呢? → 从代码上我们能猜测一二:动态规划需要存储一个矩阵d[m][n],随着规模的增大,矩阵变得越来越大,对内存的占用也是越来越多的。这本质上是在用空间换时间。当然,也是有办法可以优化其占用空间的,具体的可以看参考资料中明无梦的文章。另外,目前我还不知道该如何实际测量程序的空间复杂度,如果有知道的朋友,还望不吝赐教。
参考资料