Jan
26
又遇到一个灵异的 intellij idea 问题。
背景:在项目 P 的同一个 Module M 下面, PKG P1 需要 import PKG P2 下面的 C1 和 C2 两个 class。
现象:import C1 成功,但是import C2失败;然而通过 mvn clean install 是可以正常完成编译的。

删除 project 下的 .idea 目录重新 import 并没有解决这个问题。
在另一个同学的电脑上尝试,报的错竟然不一样,是在 C2 这个 class 下无法 import 另一个 class C3,但同样可以通过 mvn 命令行完成编译。
通过 Google 搜到 StackOverflow 的这个 thread:
https://stackoverflow.com/a/66167190/802910
解决方案很简单:删掉 idea 的cache 目录,让它重建就好了。
在 windows 下,这个目录位于 %LOCALAPPDATA%\JetBrains\IdeaIC2021.2\caches (注意替换为自己版本号)
在 mac 下,目录应该是 ~/Library/Caches/JetBrains/IdeaIC2021.2
似乎 IDEA 本身也有清空 cache 的功能(File -> Invalidate Caches...),下次遇到再验证一下。
背景:在项目 P 的同一个 Module M 下面, PKG P1 需要 import PKG P2 下面的 C1 和 C2 两个 class。
现象:import C1 成功,但是import C2失败;然而通过 mvn clean install 是可以正常完成编译的。
删除 project 下的 .idea 目录重新 import 并没有解决这个问题。
在另一个同学的电脑上尝试,报的错竟然不一样,是在 C2 这个 class 下无法 import 另一个 class C3,但同样可以通过 mvn 命令行完成编译。
通过 Google 搜到 StackOverflow 的这个 thread:
https://stackoverflow.com/a/66167190/802910
解决方案很简单:删掉 idea 的cache 目录,让它重建就好了。
在 windows 下,这个目录位于 %LOCALAPPDATA%\JetBrains\IdeaIC2021.2\caches (注意替换为自己版本号)
在 mac 下,目录应该是 ~/Library/Caches/JetBrains/IdeaIC2021.2
似乎 IDEA 本身也有清空 cache 的功能(File -> Invalidate Caches...),下次遇到再验证一下。
Aug
11
# 现象
手头有一个比较大的maven project,拆成了十几个module,如果我要在 Intellij IDEA 跑个单测什么的,就会报错,各种依赖找不到,即使 pom.xml 里是明明白白写着:

依然无法识别,连 lombok 和 junit 都不行:

尽管 idea 很好心地给了帮助 "Add JUnit4 to classpath",点击后也只是在 pom.xml 里再添加一次,并没有什么卵用。
这个问题有个很灵异的现象是,每次用 "mvn clean install" 整体编译的时候是正常的,但是在 idea 跑 test case,或启动某个 main,就会报错。
# 排查
打开 Project Structure 可以看到,这个 module 的 dependency 全是空的:

说明 pom.xml 文件应该是有坑。
查看 maven reload 的output,发现是了问题是某个dependency没有指定版本号
参考其他 module 指定正确的版本号:
再重新reload,问题就解决了。
# 回顾
再回头想想前面提到的灵异现象,从结果倒推,大概是因为把项目作为整体编译的时候,同一个package只能有一个版本,即使模块A没有指定版本,只要模块B有指定,就能正常引用。
之前还遇到过另一个现象,整体编译没问题,但是在 iDEA 里跑单测的时候,会发现引用了旧版本,其实也是同样的问题了。
完。
手头有一个比较大的maven project,拆成了十几个module,如果我要在 Intellij IDEA 跑个单测什么的,就会报错,各种依赖找不到,即使 pom.xml 里是明明白白写着:
依然无法识别,连 lombok 和 junit 都不行:
尽管 idea 很好心地给了帮助 "Add JUnit4 to classpath",点击后也只是在 pom.xml 里再添加一次,并没有什么卵用。
这个问题有个很灵异的现象是,每次用 "mvn clean install" 整体编译的时候是正常的,但是在 idea 跑 test case,或启动某个 main,就会报错。
# 排查
打开 Project Structure 可以看到,这个 module 的 dependency 全是空的:
说明 pom.xml 文件应该是有坑。
查看 maven reload 的output,发现是了问题是某个dependency没有指定版本号
引用
[ERROR] org.apache.maven.artifact.InvalidArtifactRTException: For artifact {org.apache.flink:flink-streaming-java_2.11:null:jar}: The version cannot be empty.
参考其他 module 指定正确的版本号:
引用
<version>1.10.1</version>
再重新reload,问题就解决了。
# 回顾
再回头想想前面提到的灵异现象,从结果倒推,大概是因为把项目作为整体编译的时候,同一个package只能有一个版本,即使模块A没有指定版本,只要模块B有指定,就能正常引用。
之前还遇到过另一个现象,整体编译没问题,但是在 iDEA 里跑单测的时候,会发现引用了旧版本,其实也是同样的问题了。
完。
Aug
1
~/.bashrc 中加上以下内容即可:
如果 git 命令(如 git diff)下仍有代码,可以再增加
如果 vim 下依然有乱码,在 .vimrc 中增加
--
参考资料:
- Mac下使用SecureCRT时中文乱码问题解决
https://blog.csdn.net/BabyFish13/article/details/101463105
- 记一次secureCRT中文乱码解决过程
https://yunchangyue.github.io/blog/tools/2018/11/16/securecrt/
引用
export LANG=zh_CN.UTF-8
如果 git 命令(如 git diff)下仍有代码,可以再增加
引用
export LESSCHARSET=UTF-8
如果 vim 下依然有乱码,在 .vimrc 中增加
引用
set encoding=utf-8
set termencoding=utf-8
set termencoding=utf-8
--
参考资料:
- Mac下使用SecureCRT时中文乱码问题解决
https://blog.csdn.net/BabyFish13/article/details/101463105
- 记一次secureCRT中文乱码解决过程
https://yunchangyue.github.io/blog/tools/2018/11/16/securecrt/
May
12
Dec
24
备查。
#允许 felix021 用户免密 sudo 为所欲为
felix021 ALL=(ALL:ALL) NOPASSWD: ALL
#允许 adm 这个 group 免密 sudo 为所欲为
%adm ALL=(ALL:ALL) NOPASSWD: ALL
# Cmnd alias specification
Cmnd_Alias APT_CMD=/usr/bin/apt-get install *, /usr/bin/apt install *
# 允许所有用户用 root 权限执行 APT_CMD 下的所有命令
ALL ALL=(root) NOPASSWD: APT_CMD
felix021 ALL=(ALL:ALL) NOPASSWD: ALL
#允许 adm 这个 group 免密 sudo 为所欲为
%adm ALL=(ALL:ALL) NOPASSWD: ALL
# Cmnd alias specification
Cmnd_Alias APT_CMD=/usr/bin/apt-get install *, /usr/bin/apt install *
# 允许所有用户用 root 权限执行 APT_CMD 下的所有命令
ALL ALL=(root) NOPASSWD: APT_CMD
Oct
25
Aug
20
简单记一下:
或者
$ cat curl-format.txt
time_namelookup: %{time_namelookup}\n
time_connect: %{time_connect}\n
time_appconnect: %{time_appconnect}\n
time_pretransfer: %{time_pretransfer}\n
time_starttransfer: %{time_starttransfer}\n
$ curl -w '@curl-format.txt' -o /dev/null -s -L "https://www.baidu.com"
time_namelookup: 0.004
time_connect: 0.018
time_appconnect: 0.050
time_pretransfer: 0.050
time_starttransfer: 0.065
time_namelookup: %{time_namelookup}\n
time_connect: %{time_connect}\n
time_appconnect: %{time_appconnect}\n
time_pretransfer: %{time_pretransfer}\n
time_starttransfer: %{time_starttransfer}\n
$ curl -w '@curl-format.txt' -o /dev/null -s -L "https://www.baidu.com"
time_namelookup: 0.004
time_connect: 0.018
time_appconnect: 0.050
time_pretransfer: 0.050
time_starttransfer: 0.065
或者
$ go get github.com/davecheney/httpstat
$ httpstat https://www.baidu.com
...
DNS Lookup TCP Connection TLS Handshake Server Processing Content Transfer
[ 0ms | 9ms | 105ms | 10ms | 0ms ]
| | | | |
namelookup:0ms | | | |
connect:10ms | | |
pretransfer:116ms | |
starttransfer:126ms |
total:126ms
$ httpstat https://www.baidu.com
...
DNS Lookup TCP Connection TLS Handshake Server Processing Content Transfer
[ 0ms | 9ms | 105ms | 10ms | 0ms ]
| | | | |
namelookup:0ms | | | |
connect:10ms | | |
pretransfer:116ms | |
starttransfer:126ms |
total:126ms
Aug
8
最近老是想起陈芝麻烂谷子的事情,说明工龄所剩无几了。
- 1 -
又是在那遥远的 2009 年,那个“杯具”已经不是杯具的年头,度厂办个算法比赛,办出了点儿杯具的味道。
比赛的名字叫“百度之星”,那些年在校园里影响力还蛮大的(好像现在还是),大概赛制就是通过初赛、复赛、决赛这么几轮,选出几个社会主义四有青年瓜分奖金。值得一提的是,头两年(05、06)冠军都被楼教主承包了。
为什么说有点杯具的味道呢,因为那年的初赛结束以后,度厂搞了个骚操作,把所有参赛选手提交的代码导出来,打了个包,发在贴吧里。
于是贴吧突然就炸了。

- 2 -
要知道初赛是网络赛,各个学校的 ACM(或OI) 集训队的队员们很可能都是凑在机房一起参与,毕竟毛主席教导我们人多力量大嘛。

所以这就有点意思了:如果同一个题,两份代码长得很像,说明互相抄袭概率就很大。
问题是参赛人数有点多,两两对比这 O(n^2) 的时间复杂度,靠人肉有点儿吃不消;但这么大一个瓜,光看不吃又有点可惜了。
那么这瓜到底该怎么吃呢?
- 3 -
还好,作为一个竞赛战五渣的我,通过初赛的能力没有,搞事情的能力还是有一点的。

为了对比两份代码的相似度,那我首先得找到一个指标。
作为一个善于作弊 思考的社会主义三无青年,我估计作弊者在拿到弊友代码后不会直接提交,至少会做些更换变量名之类操作;但竞赛时间紧迫,大概率来不及修改整体框架。
那么,只要我能算出修改的程度,就能判断相似度了:假设两份代码长度分别是 m、n,修改了 x 个字符, 我们大致可以把 `100% - x / ((m + n) / 2)` 当成相似度(没被修改的字符占比)。
但如何计算这修改的程度呢?毕竟修改前后代码长度很可能不同,不适合通过逐字比较来找到差别。
- 4 -
既然直接处理两段代码有点棘手,那不妨先考虑一下简单的 case 。
比如说要将字符串 "a" 改成 "b",这个简单,只要改一个字符就行。
又比如说要将字符串 "a" 改成 "ab",这个也简单,只要添加一个字符就行。
再比如说要将字符串 "ab" 改成 "b",这个依然简单,只要删除一个字符就行。
如果我能算出将一段字符串通过添加、删除、修改三种操作修改成另一个字符串的最少操作次数,应该就能把这瓜给吃了。

好像是找到了方向,但是要怎么实现呢?
- 5 -
既然直接处理两段代码还是有点棘手,那不妨再考虑一下稍微复杂一点的 case ,比如把字符串 X = "baidu" 变成 Y = "bytedance"。
首先,因为 X[0] 和 Y[0] 相同,我们可以把问题简化成:将 "aidu" 变成 "ytedance",即 X[1..4] => Y[1..8](后面简记为 X[1:] => Y[1:])。
接着,X[1] = 'a', Y[1] = 'y',如上一节所说,这时候我们有三种选择:
* 添加:给 X 添加 'y' ,当成 "byaidu",于是问题简化为将 "aidu" 变成 "tedance",即 X[1:] => Y[2:];(注意,我们在这里把该操作当成一个思维实验就好,不需要真的修改 X ,所以这里 "aidu" 对应 X[1:] 而不是 X[2:])
* 删除:从 X 中删掉 'a' ,当成 "bidu",问题简化为将 "idu" 变成 ytedance",即 X[2:] => Y[1:];
* 修改:把 X 这个 'a' 改成 'y',当成 '"byidu",问题简化为将 "idu" 变成 "tedance",即 X[2:] => Y[2:];
这三种操作中,后续需要的修改次数最少的那个,再加上 1,就是我们把 X[1:] 改成 Y[1:] 所需的最少次数。
依此类推,如果我们将 X[i:] 变成 Y[j:] 需要 f(i, j) 次操作,由上可得到这样一个公式:
也就是说,我们可以用子问题的最优解来推导出问题的最优解,如果用不说人话的方式,就叫做该问题存在最优子结构。
这么一看,代码是不是呼之欲出了?
- 6 -
啰嗦了这么多,不能忘了大佬的教导:

说干就干,把上面推导的公式落地成代码,so easy:
然后跑起来一看:

- 7 -
"index out of range",越界了 —— 显然,这里漏掉了递归的终止条件。
不过这个简单:如果 X 越界了,说明这时 i == len(X),那么 Y 还剩几个字符,我们都加上就行,即还需要 len(Y) - j 次操作;或者 Y 越界了,说明 j == len(Y),我们把 X 剩下的几个字符删掉,即 len(X) - i 次操作。
于是代码变成了:
跑起来效果杠杠的,马上就得到了 7,算得没毛病。
只可惜这代码还没法用 —— 别说跑那些参赛代码,就连长度为 16 的两个字符串都跑不出结果……
- 8 -
稍微分析一下我们就会发现,它竟然是指数时间复杂度的:

不过仔细观察上图(不仔细也没关系,我给红色高亮了),我们可以发现,为了计算 f(i, j),我们需要计算 f(i + 1, j + 1);而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j) 。
这意味着这个问题存在重复子问题,类似于我们用 f(i) = f(i - 1) + f(i - 2) 计算飞波纳妾 fibonacci 数列。
因此我们完全可以将 f(i, j) 存下来、避免重复计算,就像这样:
注:实际上这里也可以直接用一个二维数组 f[i][j] 来保存 f(i, j),对 C/C++ 来说实现会更容易,读写效率也更高。
优化以后,因为每个 f(i, j) 只需要计算 1 次、并且可以在常数时间里完成(因为子问题已经计算好了),我们将时间复杂度降到了 O(m * n) ,从而可以在短时间内计算出结果了。
- 9 -
在这个问题里,还有一个很重要的特性是,我们在计算 f(i, j) 的时候,并不关心从 f(0, 0) 到 f(i, j) 的推导过程,或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的方式,这就叫做无后效性。
注意,无后效性并不是对所有问题都成立的。
比如在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条路径,我们在使用 BFS 或 DFS 搜索时需要将路过的坐标做好标记,避免再次走到,因此从 (1, 1) 到 (x, y) 的路径是会影响从 (x, y) 到 (N, N) 的路径,不满足无后效性。
汇总一下前面提到的这个问题的几个特点:
* 最优子结构
* 重复子问题
* 无后效性
—— 这不就是标准的 动态规划 问题嘛!对应的,第 5 节我们推导出的公式,就是这个动态规划问题的状态转移方程了!

由于满足这几个特性,我们实际上可用迭代的方式,从 f(m, n) 倒推出 f(0, 0),这样可以使用循环而不是递归,进一步提高代码的运行效率。
另外,对于同一个动态规划问题,状态转移方程也可以不止有一种写法,比如我们可以定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数,于是:
基于这一版状态转移方程,我们就可以从 f(0, 0) 开始逐步计算出 f(m, n)。
具体代码就不在这里贴了,感兴趣的同学可以自己写写看,注意边界值的处理就好。
实际上,这个算法叫做编辑距离,英文名 Levenshtein distance,是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法;该算法经典到 php 的标准库里竟然包含了一个 levenshtein 函数(可见php的作者真是太闲了)。
- a -
还没完,在追求性能和效果的路上我们还能走得更远,根据代码本身的特性,我们还有一些优化可以做。
比如说代码的注释是可以先删掉再比较。
比如说代码里的字符串也可以删掉再比较。
比如说代码里的空格,貌似也不影响我们的相似度对比。
通过这样的操作,我们可以大幅缩短了需要对比的代码长度,对于 O(m*n) 的算法而言,这个改善是很可观的。
此外,当时下场切瓜的另一位瓜友将这个思路推到了极致:既然我们认为代码的整体框架不变、改变的只是变量名这些东西,那我们直接把所有字母、数字、空格等字符全删除,只留下标点符号来代表代码的框架,不是更香吗?
这样我们既提升了计算的效率,又进一步提升了计算的效果。
值得一提的是,该瓜友用的不是编辑距离,而是另一个经典的动态规划算法“最长公共子序列(LCS)”。
- b -
啰嗦了这么多,终于可以写总结了:
* 计算两个文本的相似度,可以使用编辑距离或者最长公共子序列算法;这两个都是典型的动态规划算法;
* 动态规划问题需要满足最优子结构、重复子问题、无后效性;
* 要解决动态规划问题,先定义状态,推导状态转义方程,再编码;可以用递归也可以用迭代,前者实现简单,后者运行更快;
* 搞事情要考虑后果,本不应该把参赛账号名也直接公开,结果是那次比赛有些人面子上有点不好看;不过年轻时谁没犯点错呢,除了自己谁又还记得呢?
最后,“编辑距离” 是个 LeetCode 的原题(No. 72,传送门),;“最长公共子序列” 也是个 LeetCode 的原题(No. 1143,传送门),感兴趣的同学也别错过。
都看到这儿了,帮忙点个 “赞” 或分享给你的小伙伴吧,感谢~
---
推荐阅读:
* 程序员面试指北:面试官视角
* 又是面试题?对,合并有序序列。
* 踩坑记:go服务内存暴涨
* TCP:学得越多越不懂
* UTF-8:一些好像没什么用的冷知识
* (译) C程序员该知道的内存知识 (1)
- 1 -
又是在那遥远的 2009 年,那个“杯具”已经不是杯具的年头,度厂办个算法比赛,办出了点儿杯具的味道。
比赛的名字叫“百度之星”,那些年在校园里影响力还蛮大的(好像现在还是),大概赛制就是通过初赛、复赛、决赛这么几轮,选出几个社会主义四有青年
为什么说有点杯具的味道呢,因为那年的初赛结束以后,度厂搞了个骚操作,把所有参赛选手提交的代码导出来,打了个包,发在贴吧里。
于是贴吧突然就炸了。
- 2 -
要知道初赛是网络赛,各个学校的 ACM(或OI) 集训队的队员们很可能都是凑在机房一起参与,毕竟毛主席教导我们人多力量大嘛。
所以这就有点意思了:如果同一个题,两份代码长得很像,说明互相抄袭概率就很大。
问题是参赛人数有点多,两两对比这 O(n^2) 的时间复杂度,靠人肉有点儿吃不消;但这么大一个瓜,光看不吃又有点可惜了。
那么这瓜到底该怎么吃呢?
- 3 -
还好,作为一个竞赛战五渣的我,通过初赛的能力没有,搞事情的能力还是有一点的。
为了对比两份代码的相似度,那我首先得找到一个指标。
作为一个善于
那么,只要我能算出修改的程度,就能判断相似度了:假设两份代码长度分别是 m、n,修改了 x 个字符, 我们大致可以把 `100% - x / ((m + n) / 2)` 当成相似度(没被修改的字符占比)。
但如何计算这修改的程度呢?毕竟修改前后代码长度很可能不同,不适合通过逐字比较来找到差别。
- 4 -
既然直接处理两段代码有点棘手,那不妨先考虑一下简单的 case 。
比如说要将字符串 "a" 改成 "b",这个简单,只要改一个字符就行。
又比如说要将字符串 "a" 改成 "ab",这个也简单,只要添加一个字符就行。
再比如说要将字符串 "ab" 改成 "b",这个依然简单,只要删除一个字符就行。
如果我能算出将一段字符串通过添加、删除、修改三种操作修改成另一个字符串的最少操作次数,应该就能把这瓜给吃了。
好像是找到了方向,但是要怎么实现呢?
- 5 -
既然直接处理两段代码还是有点棘手,那不妨再考虑一下稍微复杂一点的 case ,比如把字符串 X = "baidu" 变成 Y = "bytedance"。
首先,因为 X[0] 和 Y[0] 相同,我们可以把问题简化成:将 "aidu" 变成 "ytedance",即 X[1..4] => Y[1..8](后面简记为 X[1:] => Y[1:])。
接着,X[1] = 'a', Y[1] = 'y',如上一节所说,这时候我们有三种选择:
* 添加:给 X 添加 'y' ,当成 "byaidu",于是问题简化为将 "aidu" 变成 "tedance",即 X[1:] => Y[2:];(注意,我们在这里把该操作当成一个思维实验就好,不需要真的修改 X ,所以这里 "aidu" 对应 X[1:] 而不是 X[2:])
* 删除:从 X 中删掉 'a' ,当成 "bidu",问题简化为将 "idu" 变成 ytedance",即 X[2:] => Y[1:];
* 修改:把 X 这个 'a' 改成 'y',当成 '"byidu",问题简化为将 "idu" 变成 "tedance",即 X[2:] => Y[2:];
这三种操作中,后续需要的修改次数最少的那个,再加上 1,就是我们把 X[1:] 改成 Y[1:] 所需的最少次数。
依此类推,如果我们将 X[i:] 变成 Y[j:] 需要 f(i, j) 次操作,由上可得到这样一个公式:
if X[i] == Y[j]:
f(i, j) = f(i + 1, j + 1)
else:
f(i, j) = 1 + min(
f(i, j + 1), #添加
f(i + 1, j), #删除
f(i + 1, j + 1) #修改
)
f(i, j) = f(i + 1, j + 1)
else:
f(i, j) = 1 + min(
f(i, j + 1), #添加
f(i + 1, j), #删除
f(i + 1, j + 1) #修改
)
也就是说,我们可以用子问题的最优解来推导出问题的最优解,如果用不说人话的方式,就叫做该问题存在最优子结构。
这么一看,代码是不是呼之欲出了?
- 6 -
啰嗦了这么多,不能忘了大佬的教导:
说干就干,把上面推导的公式落地成代码,so easy:
def change(x, y):
def f(i, j):
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
def f(i, j):
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
然后跑起来一看:
$ python change.py
Traceback (most recent call last):
File "change.py", line 13, in <module>
print change("baidu", "bytedance")
... #省略一大段
File "change.py", line 3, in f
if x[i] == y[j]:
IndexError: string index out of range
Traceback (most recent call last):
File "change.py", line 13, in <module>
print change("baidu", "bytedance")
... #省略一大段
File "change.py", line 3, in f
if x[i] == y[j]:
IndexError: string index out of range
- 7 -
"index out of range",越界了 —— 显然,这里漏掉了递归的终止条件。
不过这个简单:如果 X 越界了,说明这时 i == len(X),那么 Y 还剩几个字符,我们都加上就行,即还需要 len(Y) - j 次操作;或者 Y 越界了,说明 j == len(Y),我们把 X 剩下的几个字符删掉,即 len(X) - i 次操作。
于是代码变成了:
def change(x, y):
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
跑起来效果杠杠的,马上就得到了 7,算得没毛病。
只可惜这代码还没法用 —— 别说跑那些参赛代码,就连长度为 16 的两个字符串都跑不出结果……
- 8 -
稍微分析一下我们就会发现,它竟然是指数时间复杂度的:
不过仔细观察上图(不仔细也没关系,我给红色高亮了),我们可以发现,为了计算 f(i, j),我们需要计算 f(i + 1, j + 1);而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j) 。
这意味着这个问题存在重复子问题,类似于我们用 f(i) = f(i - 1) + f(i - 2) 计算
因此我们完全可以将 f(i, j) 存下来、避免重复计算,就像这样:
def change(x, y):
cache = {}
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if (i, j) not in cache:
if x[i] == y[j]:
ans = f(i + 1, j + 1)
else:
ans = 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
cache[(i, j)] = ans
return cache[(i, j)]
return f(0, 0)
cache = {}
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if (i, j) not in cache:
if x[i] == y[j]:
ans = f(i + 1, j + 1)
else:
ans = 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
cache[(i, j)] = ans
return cache[(i, j)]
return f(0, 0)
注:实际上这里也可以直接用一个二维数组 f[i][j] 来保存 f(i, j),对 C/C++ 来说实现会更容易,读写效率也更高。
优化以后,因为每个 f(i, j) 只需要计算 1 次、并且可以在常数时间里完成(因为子问题已经计算好了),我们将时间复杂度降到了 O(m * n) ,从而可以在短时间内计算出结果了。
- 9 -
在这个问题里,还有一个很重要的特性是,我们在计算 f(i, j) 的时候,并不关心从 f(0, 0) 到 f(i, j) 的推导过程,或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的方式,这就叫做无后效性。
注意,无后效性并不是对所有问题都成立的。
比如在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条路径,我们在使用 BFS 或 DFS 搜索时需要将路过的坐标做好标记,避免再次走到,因此从 (1, 1) 到 (x, y) 的路径是会影响从 (x, y) 到 (N, N) 的路径,不满足无后效性。
汇总一下前面提到的这个问题的几个特点:
* 最优子结构
* 重复子问题
* 无后效性
—— 这不就是标准的 动态规划 问题嘛!对应的,第 5 节我们推导出的公式,就是这个动态规划问题的状态转移方程了!
由于满足这几个特性,我们实际上可用迭代的方式,从 f(m, n) 倒推出 f(0, 0),这样可以使用循环而不是递归,进一步提高代码的运行效率。
另外,对于同一个动态规划问题,状态转移方程也可以不止有一种写法,比如我们可以定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数,于是:
if X[i] == Y[j]:
g(i, j) = g(i - 1, j - 1)
else:
g(i, j) = 1 + min(
g(i, j - 1),
g(i - 1, j),
g(i + 1, j + 1)
)
g(i, j) = g(i - 1, j - 1)
else:
g(i, j) = 1 + min(
g(i, j - 1),
g(i - 1, j),
g(i + 1, j + 1)
)
基于这一版状态转移方程,我们就可以从 f(0, 0) 开始逐步计算出 f(m, n)。
具体代码就不在这里贴了,感兴趣的同学可以自己写写看,注意边界值的处理就好。
实际上,这个算法叫做编辑距离,英文名 Levenshtein distance,是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法;该算法经典到 php 的标准库里竟然包含了一个 levenshtein 函数(
- a -
还没完,在追求性能和效果的路上我们还能走得更远,根据代码本身的特性,我们还有一些优化可以做。
比如说代码的注释是可以先删掉再比较。
比如说代码里的字符串也可以删掉再比较。
比如说代码里的空格,貌似也不影响我们的相似度对比。
通过这样的操作,我们可以大幅缩短了需要对比的代码长度,对于 O(m*n) 的算法而言,这个改善是很可观的。
此外,当时下场切瓜的另一位瓜友将这个思路推到了极致:既然我们认为代码的整体框架不变、改变的只是变量名这些东西,那我们直接把所有字母、数字、空格等字符全删除,只留下标点符号来代表代码的框架,不是更香吗?
这样我们既提升了计算的效率,又进一步提升了计算的效果。
值得一提的是,该瓜友用的不是编辑距离,而是另一个经典的动态规划算法“最长公共子序列(LCS)”。
- b -
啰嗦了这么多,终于可以写总结了:
* 计算两个文本的相似度,可以使用编辑距离或者最长公共子序列算法;这两个都是典型的动态规划算法;
* 动态规划问题需要满足最优子结构、重复子问题、无后效性;
* 要解决动态规划问题,先定义状态,推导状态转义方程,再编码;可以用递归也可以用迭代,前者实现简单,后者运行更快;
* 搞事情要考虑后果,本不应该把参赛账号名也直接公开,结果是那次比赛有些人面子上有点不好看;不过年轻时谁没犯点错呢,除了自己谁又还记得呢?
最后,“编辑距离” 是个 LeetCode 的原题(No. 72,传送门),;“最长公共子序列” 也是个 LeetCode 的原题(No. 1143,传送门),感兴趣的同学也别错过。
都看到这儿了,帮忙点个 “赞” 或分享给你的小伙伴吧,感谢~
---
推荐阅读:
* 程序员面试指北:面试官视角
* 又是面试题?对,合并有序序列。
* 踩坑记:go服务内存暴涨
* TCP:学得越多越不懂
* UTF-8:一些好像没什么用的冷知识
* (译) C程序员该知道的内存知识 (1)