ARTS(24)

1 Algorithm

串匹配算法

1.1 KMP 算法

1.1.1 流程图

KMP 算法是串匹配是一种高效的方法,通过构造一个 next 表来大幅度移动匹配指针,从而降低暴力算法中的重复匹配。

在上图中,ij 分别指向文本串和模式串,在当前的位置发生字符失配。由于我们已经根据模式串提前计算出 next 表项目,挡墙 next[j] 为 2,所以一下轮对比的位置如下图:

同样发生了失配现象,所以继续下一轮匹配

在这个位置上同样发生了字符失配,这个时候 next[j] 值为 -1, 这是 KMP算法中比较 tricky 的部分,在模式串索引为 -1 设置了一个哨兵(sential),它是一个通配字符(*),那么接下来匹配状态

因为是通配符,所以匹配过程继续下去,下一轮状态为

由于匹配成功,所以继续往下走

j 到达模式串的最后一个字符,完成匹配。在文本串中第一次匹配的位置为 i - j

1.1.2 KMP 主算法

func kmp(haystack string, needle string) int {
    next  := buildNext(needle)
    i, j := 0, 0
    for i < len(haystack) && j < len(needle) {
        if  j == -1 || haystack[i] == needle[j] {
            i ++ 
            j ++
        } else {
            j = next[j]
        }
    }
    if j == len(needle) {
        return i - j 
    }
    return -1
}

主算法 for 循环中的 if 判断条件 j == -1 就是通配符匹配,也是匹配的一种,所以 ij 指针继续往下进行。

1.1.3 next 表构建

那么 next 表究竟代表了什么含义呢?这也是 KMP 算法之所以能够高效匹配的原因。因为在失配字符之前的子串都是匹配成功的,也就是说我们已经知道了文本串这的内容。在下一轮匹配的时候,直接跳过那些肯定不能不成功的部分,只去比较对其之后的字符。
那么肯定匹配的字符是那些呢?假设 t = next[j],那么对于字符串的前缀 needle[:t] 和 已经匹配的字符串后缀的 needle[j-t: j] 是相同的。

为了避免漏掉应该匹配的位置,需要保证 t 是最大的。对于 next[0] 也就是在第一个字符地方发生失配,我们设置一个 next[0] = -1 表明是个通配符。
如果已知 next[j-1],那么如何得到 next[j]的值呢,很简单如果 next[j-1]j-1 位置的时候下一轮要比较的位置,如果 needle[j] == needle[next[j-1]] 那么 next[j] = next[j-1] + 1,否则继续往前找更小的子串来匹配,比较 needle[j] == needle[next[next[j-1]]],知道 next[0] == -1 ,因为设置了通配符,这次相等比较肯定会成功。

func buildNext(needle string) []int {
    next := make([]int, len(needle))
    t, next[0]  = -1, -1
    for j:=0; j < len(needle)-1; {
        if t == -1 || needle[j] == needle[t] {
            next[j+1] = t + 1
            j++
        }else{
            t = next[t]
        }
    }
    return next
}

1.2

2 Review

Asking the right question is more important than getting the right answer
提出一个好问题比得到一个好答案更加重要
学校训练我们为既定的问题得到正确的答案,但是现实生活中的经验告诉我们,提出一个正确的问题似乎是更加困难的。
更进一步讲,你要开始提出一个问题,我想说明的是你提出的问题就表明了你是哪一类人。
什么是好的问题呢?

  • 好的问题是应该可理解的并且有价值的,它会指引你走向一条探索之路。你可以简单提出类似如何治疗癌症的问题,但是这个问题对于非医疗领域的人来讲不是一个好的问题,因为这个不能提供任何帮助。
  • 秘密的问题是最好的,如果你的脑海中有自己一个人知道问题,这仿佛你自己藏了一个金矿。每个人都知道的问题就很大概率没有任何价值。这个观点在 Peter Thiel 那本 《从零到一》这本书中已经说过。

你可能会说,通过努力学习,学习所有的问题,就能够更好的提出问题。但是我不同意这个观点。
事实上,知道得更多可能会伤害你,我更喜欢那种每天都有新的问题学生A,而不是每门课都是 A+ 并且每件事都是正确的学生。一个很难接受的现实是那些最好的研究者或者发明是那些很平均的学生。
可以做下面的一个实验,选择任何一个研究领域,花两周阅读你能够阅读的全部资料。接下来,写下 5 个问题,我几乎可以保证你写下的问题都可以在你已经阅读的资料中找到,这些问题就是所谓的 已知答案 的问题。
所以为了找到好的问题,你需要与这些材料保持一定距离。如果你同意我定义的 好问题 是那些秘密亦或者 高度原创,这个观点是毫无争议的。
我们思维的方式是取向那些我们已经定义好的模式。花两年学习马克思主义,那就感觉每一个问题都好像变得马克思主义化。从这个思维框架中提出新的问题是非常困难的。
这就是很多研究这公的工作方式,他们从他们领域中的最近的会议和期刊中阅读最好的论文。更重要的是,他们确信他们阅读的是其他人阅读的,确保他们的思维方式也是最优秀的人的思维方式。他们也确信他们能够重复最流行的问题和答案。他们阅读论文,找到这些文章的漏洞或者提高的可能性。但是这些确信只是导致了那些优秀的前行者带来的无数类似的论文或者微小的变种。
这个现象从后来的角度来看很容易发现。在计算机科学中,世纪之交的时候有一股 XML 狂热。每一年在每一次顶级数据库会议上,大量的有关 XML 文章出现,我之前写过这个问题。那为什么在同一个时刻无数人对一个即将消失的东西这么狂热?
我认为因为人们更加乐于交出问题,然后证明那些老旧的答案,而不顾这个问题是否正确。
我的观点是这样的,那些领先的人不是天然的聪明、智慧或者创造性。那些回答别人的问题也不是笨蛋或者缺乏想象力。主要区别在于专注力,你可以专注于提出的问题,也可以专注于提供好的答案。
如果我们有更多的提出好问题的人,世界将会变得更好。
我们该如何提出好的问题呢?

  • 专注于你周边违背你世界观的事情。Fleming 是如何发现亲霉素?他注意到那些入侵到他是实验室的霉斑杀掉了细菌,在那一刻他提出了一个好问题。
  • 保持耐心。据说 Einstein 曾经说过 “我并不是非常聪明,只不过我和难题待在一起时间比较长”。你和问题相处的时间越长,你就越有可能发现有趣的问题。错失有趣的问题最好的方法就是错失难题然后尽快的离开。
  • 保持身体活跃,出去走走。我曾经认为所有伟大的智能产出都是有最好的套路。但是现在我认为我完全错了,现在每个周末的早上我都会出去走走。
  • 别那么专注社交。社交的压力往往压制自发的创造性。正确的做法是,在全天都处于独处状态。Bernstin 建议间断性的社交活动,而不是持续性的社交活动,避免个体的创造性。
  • 提出很多问题。如果你想要成为能够提供答案的人,训练你自己回答大量问题。同样如果你想要擅长提出问题,提出很多问题。
  • 永远对你的思考和工作提出问题。

3 Tips

3.1 vim 删除全部

gg -> dG

3.2 APScheduler

在使用 cron 定时任务的时候,注意 timezone 参数设置。
参考

3.3 如果判断一个数字是否为2的幂

n & (n-1) == 0

4 Share

在使用任何第三方工具的时候,一定要充分阅读相关文档,针对不同的目的,可以阅读工具的不同类型文档

Comments
Write a Comment