Becomin' Charles

算法 | LNMP | Flutter | Mac

Becomin' Charles

局限于英文水平和对软件工程“学术界”了解的浅薄,我对 Inverstion of Control —— 中文或许可以翻译成“反向控制” —— 的理解,总是停滞在一种似是而非的程度。我尝试通过搜索来学习,发现我能搜到的中文文章,都不能给我很大的帮助,有的在大谈特谈 Spring 框架如何如何;有的又说,想搞清楚 IoC,你先要理解 DIP …… ;也有的,干脆就说,所谓的 IoC 根本就是 DI。一时间,各种术语满天飞,越发让我觉得糊涂了。

不得已,我又开始搜寻英文资料,发现基本也是各种意见都有,但是无一例外都会指向一个地方,就是 Martin Fowler(马丁・福勒)的文章(很感谢国外这些博客的作者,都有良好的习惯,让人比较容易找到一个概念的发展脉络)。通过学习和对比各种国内的文章,我似乎对这个概念更加清晰了一些,不敢说全懂了,但是总算比以前明了了一点。特此记录。

阅读全文 »

简述一下题目的意思:给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。

这个题目的全文太长了,我就不全部挪过来了,就是提示一下这个意思就行了。具体可以去 LC 上查看。

这个题目感觉和 26 题极其相似,我第一个想到的就是“双指针”,第一个指针标记筛后的数组的末位,第二个指针指向筛前数组的开头。然后,两个指针的初始化都在 0,我们这么考虑问题,从筛选前的数字的第一个元素开始,如果这个元素没命中 target 就拷贝到筛选后数组的最后一位,如果命中了,就跳过看第二个元素。

因为筛选用的那个指针移动速度大于等于筛选后的那个指针,所以这个算法会没有重复和遗漏地结束。写出来是:

1
2
3
4
5
6
7
8
9
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, 0
while j < len(nums):
if nums[j] != val:
nums[i] = nums[j]
i += 1
j += 1
return i

也是非常短的。写完我看了下答案,原来还有优化的空间,就是我这个算法,拷贝的次数比较多,因为如果整个数组都没有命中的数字,那么每个数字都要被原地赋值一次,确实如此。

如果我们不纠结元素的顺序,可以使用交换法,还是双指针,一个初始化在筛后数字的开头,一个指向筛前数组的末位,就是倒着筛,筛到就交换。这样就极大减少了赋值的次数,提高了效率。很有意思。

知识点:无新的知识点。

这是一个非常经典的库函数吧,在一个长字符串(haystack)中,搜索一个字符串(needle),如果包含了就返回起始的位置,如果没有包含,就返回 -1。

看了这个题目,我想到的唯一办法就是暴力算,先做一头对齐,然后逐个比较,找到了返回下标,没找到就移动一格重复这个过程,直到无法移动为止:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
i, j = len(haystack), len(needle)
if j == 0:
return 0
x, y = 0, 0
while x <= i - j:
for y in range(j):
if haystack[x + y] != needle[y]:
break
if needle[y] == haystack[x + y]:
return x
else:
x += 1
return -1

其实没啥难的,就是很多边界条件,很难写,我提交错了 5 回才写对。(泪奔……

然后我看了题解,暴力算是比较普遍的解法,我的也不算太偏。看到了一个让我皱眉头的算法,叫 KMP,大学时候我学过,完全没有学会过。这次我就认真学学。

自然而然写的那个算法,里面其实存在重复,因为目标字符串,每次搜索失败,我们只移动一个位置,其实,搜索过程中,可能已经比较了好几个字符了,都白比较了。所以,类似 KMP 这样的算法,本质上,就是希望已经比较过的部分,希望能利用起来,减少重复的运算,从而提高了效率。

自然而然写的算法,复杂度大概是 O(M(N-M)),但是 KMP 算法,通过预处理,时间换空间,可以做到 O(N) 的时间复杂度。

它的原理,简单来说,就是已经扫描过的被搜索串,应该是完整的目标搜索串的子串,这个子串的后缀同时也是这个子串的前缀的话,那么我们就可以节省移动的距离。这么说是非常绕的,我是看了很久很久才看懂的。

字符串匹配的KMP算法》阮一峰

KMP算法详解》 labuladong

《[如何更好的理解 KMP 算法](http://如何更好地理解和掌握 KMP 算法? - 海纳的回答 - 知乎 https://www.zhihu.com/question/21923021/answer/281346746)》知乎

上面两篇是我认真看了的网络文章,此外我还翻阅了《算法导论》,多种材料混合下,还是看懂了一点的。我估计过个不久就还是会忘记的,所以,我打算,按照自己已经理解的部分来实现一下 KMP 算法,如果能写对,我估计印象可以久一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
i, j = 0, 0
pie = self.pie(needle)

while i < len(haystack) and j < len(needle):
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
else:
j = pie[j]
if j == len(needle):
return i - j
return -1

def pie(self, needle: str) -> List[int]:
pie = [0] * len(needle)
pie[0] = -1
i, j = 0, -1
while i < len(needle) :
if j == -1 or needle[i] == needle[j]:
i += 1
j += 1
if i < len(needle):
pie[i] = j
else:
j = pie[j]
return pie

看了很久,我最后还是没写出来,这是从知乎上一个回答里面拷贝过来的。我自己还是没有掰明白的,我决定还是放一放先。先不要纠结了,后面回过头来再说吧。

在一个给定的排序数组里,找到一个目标数字的位置,如果没有,就给出插入的位置。

这个题目,一看就是二分查找法的应用,但是我写了两次没写对,二分查找法主要是处理边界的问题,还是有很多细节的,我先写了一个 O(N) 的搜索法:

1
2
3
4
5
6
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if target <= nums[i]:
return 0 if i == 0 else i
return len(nums)

很短,很容易写,一下就写对了。然后,我看了题解,还是借机会练习一下二分查找法比较好一点。

所谓的插入位置是什么意思呢?

一般来说,我们把一个数字放入数组的第 0 个位置,则原来在 0 这个下标的数字,会往右移,下标变为 1。所以,这道题,我们真正要找的那个下标是,该下标位置的数字,大于或者等于 target 目标值。

这个在 Python 类库里,其实就是 bisect_left 这个方法。

1
2
3
4
5
6
7
8
9
10
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) >> 1
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left

这是一个二分法的实现。这里比较 tricky 的部分,就是处理边界移动和最终返回值的地方。注意看这句 nums[mid] < target ,满足这个条件的时候,我们把左边界往右移了一格,移动后,nums[left] ≥ target ,所以,left 就是我们要找的解。

真是活久见了,当我使用 yum update 命令的时候,发现竟然报错了:

1
2
3
4
5
6
7
8
yum update
error: rpmdb: BDB0113 Thread/process 4196/140144005818432 failed: BDB1507 Thread died in Berkeley DB library
error: db5 error(-30973) from dbenv->failchk: BDB0087 DB_RUNRECOVERY: Fatal error, run database recovery
error: cannot open Packages index using db5 - (-30973)
error: cannot open Packages database in /var/lib/rpm
CRITICAL:yum.main:

Error: rpmdb open failed

都怪我之前写了各种自动守护脚本,导致服务器上跑的各种服务长久都没什么抖动,于是乎,我很久也不用登录了,不过今天还是跑飞了,上去看看,服务死了,而且 systemd 没有拉起来,太奇怪了。

手动执行了 systemctl restart 后,我想起来久没上来,应该更新一下子,就报错了。从来没见过这个错误,这次可能真的一年多没更新了吧。

搜到了解决方案:

1
2
3
4
5
6
7
8
9
# 第一步,备份文件,建议做备份
mkdir /root/backups.rpm.mm_dd_yyyy/
cp -avr /var/lib/rpm/ /root/backups.rpm.mm_dd_yyyy/

# 第二步,删除错误的文件,开始重建
rm -f /var/lib/rpm/__db*
db_verify /var/lib/rpm/Packages
rpm --rebuilddb
yum clean all

一次尝试成功,可以愉快的 yum update 了。

当然以上解决方案来自 SO

这个原题目可以去 LC 看。我看到这个题目的想法就是硬做,无非是数相同的数字有几个的问题,然后用两个数字描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
say, i, new = "1", 1, ""
while i < n:
num = say[0]
count = 0
for j in range(len(say)):
if num == say[j]:
count += 1
else:
new += str(count) + num
count = 1
num = say[j]
new += str(count) + num
say, new = new, ""
i += 1
return say

这是我写的代码,就是迭代的去逐个计算。

我看了一下题解,有提到查表法的,这个当然是正确的解法,这个题目,有非常小的问题空间 1 <= n <= 30 一共才30个,当然,生成 30 个答案,还是要靠算法去计算,用查表法,只是增加了喜剧效果和真的很省时间,可以 Beats 100%。

另外,值得一提的是,有不少人提到了递归法,这个题目显然具备了递归的结构,比如,计算第 n 个串,本质上就是对第 n - 1 个串的描述。所以,可以用递归法,不过这个题目的特殊之处在于,用递归写,也并没有简单多少,反倒增加了栈的成本。没什么意思,其实栈里只是存储了 n - 1 个串的表达而已,用一个变量就可以存了。像我上面写的代码一样。

这个题目就像标题一样直接,第一步,找到最后一个单词,第二步,计算长度。

我就写了这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def lengthOfLastWord(self, s: str) -> int:
idx = len(s) - 1
flag = False
count = 0
while idx >= 0:
if s[idx] == " ":
if not flag:
idx -= 1
continue
else:
break

flag = True
count += 1
idx -= 1
return count

写完看了题解,发现我写得还是比较啰嗦的,多用了很多的变量。题解里有一些解法,上来先处理尾空格,然后再开一个循环开始计数,原理是一样的,但是写起来简洁了很多,我个人觉得很好。

另外有人提到,为啥不用 trim,是呀,题目也没说不可以用 trim,如果对类库很熟的话,完全可以用 trim,不能因为是算法题,就陷入思维定势吧…… 也是蠢得可爱……

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def lengthOfLastWord(self, s: str) -> int:
s = s.strip()
idx, count = len(s) - 1, 0
while idx >= 0:
if s[idx] != " ":
count += 1
else:
return count
idx -= 1
return 0

用 Python 的 strip() 函数,精简了一下,去掉尾空格后,数数,遇到空格停止。

这个问题也是极其的简洁,就是把一个整数,按位拆分到一个 list 里面,然后,在低位加一,然后让你处理好进位问题。学了几次的列表反转,终于可以在这里派上用场了,难得我想起来用一次:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits, carry = digits[::-1], 1
for i in range(len(digits)):
digits[i] += carry
carry, digits[i] = digits[i] // 10, digits[i] % 10
if carry == 0:
break
if carry == 1:
digits.append(1)
return digits[::-1]

数字的加法,是把 1 加到列表的最右边,但是列表的迭代从最左边比较容易,所以我反转一下,当然这有代价。

然后,我假设现在进位已经有 1 了,原题目正好就是这个意思。然后,迭代处理进位就行了。如果进位最后还剩下 1 ,那么 append 个 1(翻转后的好处),返回的时候,再翻转回去即可。

这样一段代码,不瞒你说,写了三次才写对。你还能写得比我更差么?

最近,我确实比较闲一点,所以我把十几年前的 WordPress 插件,翻出来重新写,这个过程,虽然没什么价值,但是真的很有乐趣的一件事情,就好像有些人打游戏一样的,你把一个游戏打完了,以前完成得不够好的地方,你就再打一遍,用你以为最完美的形式。写代码,也是一样的。

这是一个面向对象设计的范畴。就像很多网站一样,WordPress 也分为前台和后台,前台是大家看到的博客页面,后台,则是各种控制面板和写作界面。然后,作为 Programmer,你一定会遇到的情况就是,有些代码只属于前台,有些代码只属于后台,而无法避免的就是,有些代码前后台都会用到。这种划分,其实是业务属性层面的划分。

还有一个情况就是,有些代码属于界面布局表现,有些属于后台逻辑计算,有些属于用户交互行为,这是逻辑层面的划分。

我们对这些代码进行分类,无非就是为了更好地去管理复杂性,我们追求的一个方向是高内聚,低耦合,让紧密联系的逻辑尽可能靠近,以加强理解和管理,进而便于去复用。不过,从上面我们也能发现,业务属性的划分和逻辑层面的划分,其实是两个不同的维度,近乎是正交的。

于是,就出现了多种的选择,供 Programmer 去进行决策。我就讲个真实的例子。我在开发一款插件,插件功能是在博客的页面上提供一些官方原本没有的功能,比如,有两个小功能,一个是给每篇文章做一个自动摘要,使得博客首页的文章,总是在一定长度后被截断,不要显示全文,这样即便我忘记进行手动摘要,也可以只显示部分内容,便于读者快速浏览整个博客的内容。另一个功能是,在单篇文章的页面,我们也叫帖子页,展示一个相关文章的列表,展示位置在文章结束的地方,提供一个“相关阅读”的栏目,让读者读完一篇文章的时候,快速发现感兴趣的东西,减少站点跳出。

无论是摘要还是相关文章列表,都是改变前台表现的功能。为了控制这两个功能,我就需要提供不少的用户选项。比如,对于摘要功能来说,怎么控制摘要的长度?文章摘要完毕后,要插入一个链接,引导用户跳转到全文进行查看,这个链接展示的样式,也需要控制,也可能,有用户不喜欢这个功能,需要关闭这个功能,那就需要一个开关。

相关文章的列表的控制项就更多了,列表的长度,是否展示文章的阅读次数或者评论数?列表的标题?或者是否关闭功能。

那么为了控制这些选项,显然,还需要后台选项的调整界面。这就是后台业务逻辑了。

我本来的设计是,有一个 Option Manager,提供所有选项的缺省值管理,选项值的读取,写入,持久化。这样,前台功能的时候,可以通过 Option Manager 访问,后台管理界面也可以。

后来我发现,在这个系统里,实现一个后台管理界面的话,会比较复杂,涉及到很多点,比如后台页面的入口位置,后台表单的呈现,提交后的验证等逻辑。后台交互的组织,非常精巧,所以我就实现了一个抽象类,专门管理后台界面的几个方面,为了控制上面两个功能的选项,我显然要把所有的选项划分成两组去分别管理,后来很自然想到了把所有的缺省值和管理界面放在一起,因为选项的结构和和界面的交互设计,也很有关系,放在一起互相启发和功能调整起来都比较快。

然后我今天重构前台的时候,就发现了很大的困难。因为,为了节省内存,我在判定用户只访问前台的时候,不加载后台的代码,我把选项缺省值,内聚到选项面板的代码里去了,这样,如果用户不访问后台的话,就不加载后台部分代码(为了节省 IO 和 内存),结果前台也读不到选项的缺省值了。

可是如果把选项缺省值抽离到 Option Manager 管理,则管理面板和被管理的选项之间的内聚性就牺牲了,于是我就给自己造就了一个两难的选择。

当然,如果这是我的工作的话,我可能随意选择一个方案就处理了,不会去追求完美,但是我这就是像打游戏一样的心态,肯定是希望对极致能有所追求,于是,这就成为一个有趣的设计问题,完全可以尝试进行一番更为精巧的设计。

感觉我就是很喜欢做这种事情,这才是我的热情所在的地方。要是能找到专门干这种事情就能挣钱谋生的工作岗位,那就完美了。

wordpress

玩 WordPress 年头已经长到记不起最初的记忆了,但是,今天我才发现我对其是何其陌生。

现在的 WordPress 早就不是一个博客软件这么简单了,当年就意识到,WordPress 这样的软件,应该归类到 CMS 系统里面,今天,我才体会到什么叫强大的 CMS 系统。以前目光还是太短浅了,也忽略了事物的发展规律。如果 WordPress 一直把自己定位成一个博客,估计尸骨都凉透了。

最近我把我以前开发的插件拿出来,更新了一些代码,让代码适应现代 PHP 的语法规范,以及适应一下新的 WordPress API,其实,这么做,现在看来已经毫无意义了,只是我实在是太久没写代码了,这么做可能可以让我保持一点感觉,毕竟我是一个 PHP 程序员出身,不能对代码和产品设计毫无感觉。

现如今我的眼光和想法和当年开发插件之初,已经发生了很大的变化。现在回顾当年开发的插件,我发现,代码仍然可以称得上精巧细致,以我现今的眼光看仍然是规范的,没有太多嫌弃年轻时候自己的感觉,只是,我现在更注重规范,一致等等。

但是现今去看当年的功能设计和概念设计,就发现简直不堪入目。比如,把很多明显程序员才了解的概念,公然放在界面上,完全不考虑用户的理解能力,似乎只是骄傲地为程序员做了一些功能。可是这个世界上最广大的用户,根本不是程序员啊?如果我只想服务程序员,又何必去发布插件到官方目录呢?毫无意义嘛,根本不会有人去使用的,就算用了,也根本无从用明白啊。

我用我插件的名字和关键词,搜索插件目录,看看同类品里,做得最好的插件,提供了怎样的功能,以及如何设计交互界面,这才给我打开了一个全新的世界。我发现有些插件的安装量,超过了 500万,这太惊人了,完全超乎了我的想象。虽然我觉得插件的世界是个长尾的世界,但是也没想过有插件能超过 500万安装量。

Gutenberg 古腾堡区块布局

这时候我意识到,我太小看了 WordPress。几个百万级插件的功能,都是围绕了最新的文章编辑器 Gutenberg 的,这个基于 Block 的编辑器,我一直根本就没领悟到精髓啊。其实,Grid 系统,正是最近这些年来页面布局的基础方法,比如 Bootstrap 之类流行世界的框架,都是使用 Grid 系统来布局页面的。这个 Block 编辑器,不就是一个可视化的 Grid 编辑器么?把页面抽象成一行一行的区块,每一行其实也可以切割成两列或者三列,由此形成的 Block 可以用区块编辑器填充各种能想象出来的功能,比如图片,图集,视频,地图,等等。你想做商品展示,或者做成电商店铺,也毫无难点,都有无数高度可视化的插件,让你不懂一点技术的情况下,做出自己想象中的网站,这真是太厉害了!

官方只提供了区块编辑这个框架,丰富的功能,由插件来提供,你可以为整个用户群体发明各种神奇的 block 功能,然后他们就能做出各种匪夷所思的网页来,完全不需要后端程序员,不需要前端程序员,只要自己准备高品质的内容即可。这想法太伟大了,这生态也太牛了。虽然 PC Web 已经没落了,但是,这套体系仍然是兼容移动 Web 的啊!而且还能很好地兼容 PC 和 移动 Web,完全超乎我的想象。

可笑我这么多年,从来没看懂过这些,只是可笑的学了一点编码和前端技术,比起真正的用户价值和商业价值来说,我学到的太少了,比起这个系统能带给客户的商业价值来说,我掌握到的太少了。有种买椟还珠的荒诞感油然而生。可笑一把年纪才明白了这么多浅显的道理,一声叹息啊,与大家共勉。