Month: 11月 2019

给 Python 程序员的 Go 语言教程

Posted on by 逸飞

楔子

最近读到一亩三分地上一篇讲 Facebook 架构和国内对比的文章，感觉自己真是井底之蛙。头脑中一些架构方面的概念和 Status of the Art 的理念还相去甚远，迫切想要进一步了解一些先进知识。比如说，以前觉得 git flow 这个概念还挺不错的，实践了半年，发现 develop 分支完全是多余的；以前觉得每个项目分一个仓库方便管理，现在觉得 monorepo 似乎更好一点。另外就是对“互联网时代的 C 语言” Golang 有点想了解一下。

一年前休假的时候看了几眼 Golang，感觉还不错，但是想实际写点什么的时候发现 GOPATH 这个设计真是奇葩至极。而现在我的思想已经完全倒向 Monorepo 了，那么 GOPATH 也就看起来很可爱了，Golang 看起来也就很可爱了，也就决定再翻翻 Go 语言的书吧，以后说不定会写点儿什么呢。

忘了在哪里看过一句话：人的知识像一个网络，新学到的知识只有和已有的知识关联起来才能真正记得住、记得牢，否则的话像是一个孤岛的新知识很快就会被忘记了，于是就有了本文。

需要注意的是，本文并不是一个简单的语法对比，倘若只是语法的话，直接把代码一列其实就差不多了。除去语法之外，本文还在设计理念上做了一些对比。以下为目录。（没有链接的表示还没有写，敬请期待）

目录

  1. 语法基础
    1. 类型与变量
    2. 数据结构与控制语句
    3. 函数定义
    4. 面向对象
    5. 错误处理
    6. 包管理
  2. 并发与网络
    1. 并发机制
    2. Http 请求
  3. 常用标准库
    1. 时间解析
    2. 文件 IO
    3. 正则表达式
    4. 数学函数
    5. 定时机制

写这些文章的另一个目的就是对 Python 中相关的知识做个梳理，以便以后再学习新的语言（比如 rust, clojure）能够更有条理。

Ref

  1. Python slice notation. https://stackoverflow.com/questions/509211/understanding-slice-notation/50929x
  2. How to get type of go. https://stackoverflow.com/questions/20170275/how-to-find-a-type-of-an-object-in-go
  3. Golang online repo. https://repl.it/languages/go
  4. A tour of go. https://tour.golang.org/moretypes/6
  5. golang vs python. http://govspy.peterbe.com/#lists
  6. https://www.353.solutions/py2go/index.html

面试刷题总结（八）- 字符串

Posted on by 逸飞

解决两个字符串的动态规划问题，一般都是用两个指针 i,j 分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

解字符串问题常用的算法是采用滑动窗口的方法。

避免字符串 O(n) 比较的一个方法是使用 hash。

字符串问题本质上都是自动机问题，实际上还是图论问题。

后缀数组技巧

kmp

  1. next 数组的定义为：当前位置的子字符串，前缀和后缀匹配的最大长度为多少。
  2. KMP 计算 next 数组和查找字符串的过程几乎是一样的，所以关键就在于构造 next 数组。
  3. 构造 next 数组的关键就一句话：次大匹配就是（失败的）最大匹配处的子串的最大匹配，也即 j = next[j-1]
def kmp(t, p):
    """return all matching positions of p in t"""
    next = [0]
    j = 0  # j 表示当前自创中前缀和后缀匹配的最大长度
    # 注意这里是从 1 开始
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if p[i] == p[j]: # 相等时，最大匹配自然要 +1
            j += 1
        next.append(j)
    ans = []
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if t[i] == p[j]:
            j += 1
        if j == len(p):
            ans.append(i - (j - 1))
            # 这里是匹配成功了，但是要接着找下一个，所以按失败处理
            j = next[j - 1]
    return ans

def test():
    p1 = "aa"
    t1 = "aaaaaaaa"

    assert(kmp(t1, p1) == [0, 1, 2, 3, 4, 5, 6])

    p2 = "abc"
    t2 = "abdabeabfabc"

    assert(kmp(t2, p2) == [9])

    p3 = "aab"
    t3 = "aaabaacbaab"

    assert(kmp(t3, p3) == [1, 8])

    print("all test pass")

if __name__ == "__main__":
    test()

自动机

Trie 是一个自动机，KMP 是一个自动机，AC 自动机是 Trie 上运行 KMP 得到的自动机。Trie 和 KMP 都可以用于单模匹配，AC 自动机可以用于多模匹配。AC 自动机是确定性有限状态自动机 (DFA)。

正则表达式构建出来的却是一个非确定性有限状态自动机（NFA），非确定指的是跳转的时候可能有多个分支。要实现非指数时间解，也就是不用回溯，其实就是把回溯的深度优先遍历改成了广度优先遍历从而实现了剪枝。

哈夫曼树

https://juejin.im/post/5d1c7df2e51d45775c73dd49

参考资料

  1. https://oi-wiki.org/string/hash/
  2. https://www.zhihu.com/question/21923021/answer/37475572
  3. https://swtch.com/~rsc/regexp/regexp1.html
  4. https://stackoverflow.com/questions/31429865/trie-for-unicode-character-set
  5. https://oi-wiki.org/string/sa/
  6. https://oi.men.ci/suffix-array-notes/
  7. https://blog.csdn.net/u013421629/article/details/83178970
  8. https://oi-wiki.org/string/ac-automaton/
  9. http://nark.cc/p/?p=1453
  10. https://lingeros-tot.github.io/2019/03/05/Warming-Up-%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%A8%A1%E5%9E%8B/
  11. http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

LeetCode 1236/1242 设计一个(多线程)爬虫解法

Posted on by 逸飞

单线程题目 LeetCode-1236

具体题目就不说了，直接去 LeetCode 上看就好了。1236 要求使用单线程即可，考察的主要是图的遍历。只要注意到对于新发现的节点需要考虑是否已经访问过就好了。在实际生产中，肯定也是要用广度优先，深度优先基本就会陷进一个网站出不来了。

from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        domain = urlsplit(startUrl).netloc
        q = [startUrl]
        visited = set([startUrl])
        while q:
            newUrls = []
            for url in q:
                urls = htmlParser.getUrls(url)
                for newUrl in urls:
                    u = urlsplit(newUrl)
                    if u.netloc != domain:
                        continue
                    if newUrl in visited:
                        continue
                    visited.add(newUrl)
                    newUrls.append(newUrl)
            q = newUrls
        return list(visited)

多线程题目 LeetCode-1242

1242 题要求使用多线程来实现。在现实生活中，爬虫作为一个 IO 密集型的任务，使用多线程是一项必须的优化。

在上述的单线程版本中，我们使用了 visited 这个数组来存放已经访问过的节点，如果我们采用多线程的话，并且在每个线程中并发判断某个 URL 是否被访问过，那么势必需要给这个变量加一个锁。而我们知道，在多线程程序中，加锁往往造成性能损失最大，最容易引起潜在的 bug。那么有没有一种办法可以不用显式加锁呢？

其实也很简单，我们只要把需要把并发访问的部分放到一个线程里就好了。这个想法是最近阅读 The Go Programming Language 得到的启发。全部代码如下：

import threading
import queue
from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        domain = urlsplit(startUrl).netloc
        requestQueue = queue.Queue()
        resultQueue = queue.Queue()
        requestQueue.put(startUrl)
        for _ in range(5):
            t = threading.Thread(target=self._crawl, 
                args=(domain, htmlParser, requestQueue, resultQueue))
            t.daemon = True
            t.start()
        running = 1
        visited = set([startUrl])
        while running > 0:
            urls = resultQueue.get()
            for url in urls:
                if url in visited:
                    continue
                visited.add(url)
                requestQueue.put(url)
                running += 1
            running -= 1
        return list(visited)

    def _crawl(self, domain, htmlParser, requestQueue, resultQueue):
        while True:
            url = requestQueue.get()
            urls = htmlParser.getUrls(url)
            newUrls = []
            for url in urls:
                u = urlsplit(url)
                if u.netloc == domain:
                    newUrls.append(url)
            resultQueue.put(newUrls)

在上面的代码中，我们开启了 5 个线程并发请求，每个 worker 线程都做同样的事情：

  1. 从 requestQueue 中读取一个待访问的 url；
  2. 执行一个很耗时的网络请求：htmlParser.getUrls；
  3. 然后把获取到的新的 url 处理后放到 resultQueue 中。

而在主线程中：

  1. 从 resultQueue 中读取一个访问的结果
  2. 判断每个 URL 是否已经被访问过
  3. 并分发到 requestQueue 中。

我们可以看到在上述的过程中并没有显式使用锁（当然 queue 本身是带锁的）。原因就在于，我们把对于需要并发访问的结构限制在了一个线程中。

当然如果可以用锁的话，也可以在每个 worker 线程中计数。而这种情况下，为了使用 running > 0 这个条件，一定要首先在发现新的 url 的时候 running++，在处理完整个页面之后再 running–。