计算机

Python metaclass 的原理和应用

元编程(meta programming)是一项很神奇的能力,可以通过代码在运行时动态生成代码。元类(meta classes)是 Python 提供的一种元编程的能力。在 Python 中,类也是一种对象,那么类这种对象就是元类的实例,所以我们可以在运行时通过实例化元类动态生成类。

使用 type “函数”

首先我们来了解一下 type,type 可以作为函数使用,用来获得对象的类型:

>>> class Foo:
...     pass
>>> obj = Foo()
>>> obj.__class__
<class "__main__.Foo">
>>> type(obj)
<class "__main__.Foo">
>>> obj.__class__ is type(obj)
True

实际上 type 并不是一个函数,而是一个类,我们可以使用 type(type) 来确定一下:

>>> type(type)
<class "type">

type 实际上不只是类,而是一个“元类”。我们接下来要可以看到,所有的元类都需要继承自 type。type 是所以类的元类,所以在上面的例子中 x 是 Foo 的实例,Foo 是 type 的实例,type 又是他自己的实例。

file

使用 type 动态创建类

如果传递给 type 的参数是三个的时候,type 的语义就不再是返回给定参数的类,而是实例化生成一个新的类。

type(name: str, bases: tuple, namespace: dict)

第一个参数是新生成的类的名字;第二个参数是新生成的类的基类列表;第三个参数是要个这个类绑定的属性的列表,比如说这个类的一些方法。实际上 class Foo 这种语法只是使用 type 生成类的语法糖而已。

最简单的一个例子,比如我们要创建 Foo[0..9] 这些类,可以这样做:

classes = []
for i in range(10):
    cls = type("Foo%s" % i, tuple(), {})
    classes.append(cls)

# 就像使用普通类一样初始化 Foo0

foo0  = clssses[0]()

如果要实现类的方法,一定要记得同样是要使用 self 变量的。在 Python 中 self 只是一个约定俗称的变量,而不是关键字。

def __init__(self, name):
    self.name = name

def print_name(self):
    print(self.name)

Duck = type("Duck", tuple(), {"__init__": __init__, "print_name": print_name})

duck = Duck("Donald")

duck.print_name()
# Donald

创建自己的元类

首先我们来回顾一下 Python 中类的初始化过程:

foo = Foo()

当这条语句运行的时候,Python 会依次调用 __new____init__ 方法。其中 __new__ 方法在 __init__ 之前调用,并返回已经创建好的新对象,而 __init__ 函数是没有返回结果的。一般情况下,我们都会覆盖 __init__ 方法来对新创建的对象做一些初始化操作。

现在回归到元类上,进入烧脑部分。前面我们说过元类的实例化就是类,所以大致相当于:

Foo = MetaFoo(name, bases, attrs)  # MetaFoo 默认情况下是 type
foo = Foo()

默认情况下,所有类的元类是 type,也就是在这个类是通过 type 来创建的,这和前面说的通过 type 来动态创建类也是一致的。

那么怎样定义一个 MetaFoo 呢?只需要继承自 type 就行了。因为元类的实例化就是类的创建过程,所以在元类中,我们可以修改 __new__ 来在 __init__ 之前对新创建的类做一些操作。

>>> class MetaFoo(type):
...     def __new__(cls, name, bases, namespace):
...         x = super().__new__(cls, name, bases, namespace)  # super实际上就是 type
...         x.bar = 100  # 为这个类增加一个属性
...         return x
...

>>> Foo = MetaFoo("Foo", tuple(), {})  # MetaFoo 在这里就相当于 type 了,可以动态创建类
>>> Foo.bar
100
>>> foo = Foo()
>>> foo.bar
100

在这里我们创建了 MetaFoo 这个元类,他会给新创建的类增加一个叫做 bar 的属性。

在实际的代码中,我们一般还是不会直接动态生成类的,还是调用 class Foo 语法来生成类比较常见一点,这时候可以指定 metaclass 参数就好了。可以通过 Foo(metaclass=MetaFoo) 这种方式来指定元类。

class Foo(metaclass=MetaFoo):
    pass

这种定义和上面的元类用法效果完全是一致的。

一个现实世界的元类例子

在 django.models 或者 peewee 等 ORM 中,我们一般使用类的成员变量来定义字段,这里就用到了元类。

class Field:
    pass

class IntegerField(Field):
    pass

class CharField(Field):
    pass

class MetaModel(type):
    def __new__(meta, name, bases, attrs):
        # 这里最神奇的是:用户定义的类中的 bases 和 attrs 都会作为参数传递进来
        fields = {}
        for key, value in attrs.items():
            if isinstance(value, Field):
                value.name = "%s.%s" % (name, key)
                fields[key] = value
        for base in bases:
            if hasattr(base, "_fields"):
                fields.update(base._fields)
        attrs["_fields"] = fields
        return type.__new__(meta, name, bases, attrs)

class Model(metaclass=MetaModel):
    pass

这样用户使用的时候就可以这样定义:

>>> class A(Model):
...     foo = IntegerField()
...
>>> class B(A):
...     bar = CharField()
...
>>> B._fields
{"foo": Integer("A.foo"), "bar": String("B.bar")}

程序在执行的时候就可以直接访问 X._fields,而不用每次都通过反射遍历一次,从而提高效率以及做一些验证。

不过,其实这个完全可以通过装饰器来实现:

def model(cls):
    fields = {}
    for key, value in vars(cls).items():
        if isinstance(value, Field):
            value.name = "%s.%s" % (cls.__name__, key)
            fields[key] = value
    for base in cls.__bases__:
        if hasattr(base, "_fields"):
            fields.update(base._fields)
    cls._fields = fields
    return cls

@model
class A():
    foo = IntegerField()

class B(A):
    bar = CharField()

但是用装饰器的话,就失去了一些类型继承的语义信息。

总结与思考

Python 中的元编程还是一种很强大的特性,但是也比较复杂,有时候很难以理解。实际上,过分的动态特性也导致了 Python 的解释器和静态分析、自动补全等很难优化,因为有好多信息必须到运行时才能知道。

实际上近些年新开发的语言越来越多地加入了静态类型的特性,比如 swift, rust, go 等。就连 Python 本身也增加了 type hinting 的功能,很遗憾的是,这个功能不是强制性的,所以也很难用来提升性能。

元类这块应该是我在 Python 语言方面了解的最后一大块知识了。接下来除了写业务代码不会再深究 Python 了,研究 Golang 去了~

Au revoir, Python!

参考

  1. https://realpython.com/python-metaclasses/
  2. https://stackoverflow.com/questions/392160/what-are-some-concrete-use-cases-for-metaclasses
  3. https://blog.ionelmc.ro/2015/02/09/understanding-python-metaclasses/
  4. https://stackoverflow.com/questions/2608708/what-is-the-difference-between-type-and-type-new-in-python

给 Python 程序员的 Go 语言教程

楔子

最近读到一亩三分地上一篇讲 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

面试刷题总结(八)- 字符串

解决两个字符串的动态规划问题,一般都是用两个指针 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 设计一个(多线程)爬虫解法

单线程题目 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–。

面试刷题总结(九)- 数学知识

数学类问题一定要记得进位 v = v1 + v2 + carry

最大公约数和最小公倍数

辗转相除法(欧几里得算法). 原理在于 gcd(a, b) == gcd(b, a % b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

排列组合

卡特兰数,为什么除以 n+1

牛顿迭代法

格雷码

二进制

  • 判断一个数是不是 2 的正整数次幂:n > 0 && (n & (n - 1)) == 0
  • 对 2 的非负整数次幂取模:x & (mod - 1)
  • 判断符号是否相同:(x ^ y) >= 0
  • 获取某一位:(a >> b) & 1
  • 遍历某个集合的子集:for (int s = u; s; s = (s - 1) & u)
  • 一的个数:while (n) {n = n & (n-1); count++}

求幂

long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

全排列

几何

有时候几何题也会出现在面试中。不过,毕竟是 coding interview 而不是 math interview,这部分复习的优先级不高。

参考

  • https://oi-wiki.org/math/

面试刷题总结(一) – 递归问题

递归是几乎一些算法的基础。实际上我认为算法题大致可以分为两类:递归和其他。

实际上计算机能解的唯二问题:

  1. 足够简单的问题:比如 x * x, x^0 = 1.
  2. 把复杂问题约简到简单问题:比如 x^n = x^(n/2) * x^(n/2)

分治、树、深度优先搜索等等实际上都是递归。

递归的核心思想:明白每个函数能做的事,并相信它们能够完成,千万不要试图跳进细节。

在面试的时候,如果允许写递归(一般是允许的),那一定要写递归解。

解题思路

对一个给定的问题:

  1. 确定哪些情形是基础情形,不需要再做递归。比如说:高度为 0 的树,或者 null 根节点,空字符串等。
  2. 把问题转化为规模更小的问题。
def fact(a, n):
    if n == 1:
        return a
    return a * fact(a, n-1)  # or n/2 or whatever...

def fact(a, n):
    if n == 1:
        return a
    h = fact(a, n/2)
    return h * h

好多时候,需要编写一个私有的 helper 方法,更改一下函数的签名。对于 Python 或者 JavaScript 的话,直接写一个闭包函数是最好的,也避免了全局变量。

Algorithme by Jeff Erickson

最后推荐一本神书:Algorithms by Jeff Erickson. 这本书全书都是在按照递归的思路讲解。

其它的书和文章的问题在于每个知识点似乎都是孤立的,比如说动态规划就在重点讲解状态转移方程和状态矩阵,而分治就在讲解如何用递归树计算时间复杂度等等。这种讲解方式下,每个知识点之间看不到有什么关联,往往熟悉了这个又忘了那个。实际上这些知识点都是有联系的,所谓的动态规划不过是状态空间搜索的一个巧妙转换,本质上和回溯是一致的,都是递归而已。每个技巧的内核都是一致的,只不过特异化之后有不同的表现,如果你不去抓住内核,通过一个主干把所有知识串联起来,而只看表面现象,那么永远也记不住的。

其他的书就好比盲人摸象,而这本书则是讲解的大象的骨骼结构和肌肉构造。分治和动归这些算法好比是大象的耳朵、尾巴等等部位,可以在外部摸到,而递归则是大象的骨架,虽然摸不到,但是只有画出了骨骼,才能把大象画好。

参考

  1. https://stackoverflow.com/questions/25367781/tips-on-solving-binary-tree-binary-search-tree-problems-using-recursion-java

在 IPython 中自动重新导入包

在使用 IPython 交互性测试编写的函数的时候,可以打开自动重新导入包的功能,这样每次保存后就可以直接测试了。

In [1]: %load_ext autoreload

In [2]: %autoreload 2

其中三个数字的含义是:

  • %autoreload 0 – 关闭自动重新导入
  • %autoreload 1 – 只在 import 语句重新导入
  • %autoreload 2 – 调用的时候自动重新导入

如果想要在 IPython 中自动启用

$ ipython profile create
$ vim ~/.ipython/profile_default/ipython_config.py
c.InteractiveShellApp.extensions = ["autoreload"]
c.InteractiveShellApp.exec_lines = ["%autoreload 2"]

面试刷题总结(七) – 树和图

图的表示方法

标准的表示方法应该是邻接表。在邻接表中我们使用链表来表示相邻节点。

任意优先搜索(Whatever First Search)

这是 Jeff Erickson 在书中提到的搜索算法框架,一个框架就综合了所有遍历算法。

树的遍历实际上和图的遍历完全一样,只是不需要标记有没有访问过当前节点。

WhateverFirstSearch(s):
  把 s 放入 bag
  while bag 非空:
    从 bag 取出 v
    if v 未标记:
      标记 v
      for 每个边 vw:
        把 w 放入 bag 中

如果 bag 的算法选用 stack,那么就可以实现深度优先遍历,如果选用 queue 就可以实现广度优先遍历。

如果选用 priority queue,那么就可以实现最优优先遍历。

  1. 如果我们使用每个边作为排序依据,那么就可以得到最小生成树,也就是传说中的 Prim 算法。
  2. 如果我们使用 dist(v) + w(v->w) 作为排序依据,那么就得到了传说中的 Dijkstra 算法。其中 dist(v) 为从源点 s -> v 的距离。
  3. 未完待续

对于没有连通的图,我们还可以使用 WFSALL 来遍历所有节点

WFSALL(G):
  for 所有节点 v:
    取消标记 v
  for 所有节点 v:
    if v 未标记:
      WhateverFirstSearch(v)

深度优先搜索

深度优先搜索实际上就是上面的 任意优先搜索 算法的特例化

DFS(v):
  标记 v
  PreVisit(v)
  for 每个边 vw:
    if w 未标记:
      parent(w) <- v
      DFS(w)
  PostVisit(v)

其中的 PreVisit 和 PostVisit 就是我们可以插入的目标函数,通过改变这两个函数就可以实现不同的算法。

拓扑排序

拓扑排序就可以简单地使用深度优先搜索实现,只不过在最后需要把顺序倒过来。

TopologicalSort(G):
  pass

二叉树外部节点总是等于内部节点加 1

解决树问题的思路

树的最大问题在于要从底层叶节点开始思考,而不是自上而下看图。递归是从基础 case 开始向上递归的。一定要画出访问的顺序图。

访问顺序图

  1. 对于任何树的问题,还是优先考虑递归,因为树本身就是一个递归性质的数据结构。
  2. 树还是天然 Devide and Conquer 的,也就是说可以分层左右两个树分别处理,然后合并得到答案。

解树的问题就只有两种方法:

  1. 分治:后序遍历,并通过左右子树和根节点一起解决问题。
        1
      /   \
    2      3
  /  \   +---+
4      5   B
+------+
    A
  1. 遍历:在遍历过程中解决问题,比如记录最大值等。

对于树的题目,到底是迭代解还是递归解呢?

*最好写递归解,比较简单。写迭代性解首先考虑栈。函数调用过程本来就会用到栈使用栈可以模拟递归调用。使用栈还可以把需要反转的操作自动反转。比如在 zigzag 层序遍历的时候。

递归的出口是选 NULL 还是叶子节点?

最好选择 null,具体来说:

  1. 有一个 corner case 是直接就传一个 null 的节点进来,所以要选 null
  2. 叶子节点比较复杂,只要判断 null 的 return 之后结果 ok, 就 null

改变函数签名与参数传递

参考回溯文档中的讲解

常见问题总结

遍历

参考 这里

二叉查找树

一定是用中序遍历来解的

其他常见的树

2-3-4 树

234 树的意思是每个节点的子节点可能有 2、3、4 个,所有的叶节点都在同一深度。

插入

对于 2-节点和 3-节点,显然是比较简单的,我们只要直接插入就行了。对于 4-节点来说,我们不能插入。不过解决方法也很简单,我们把 4-节点分裂,然后把中间节点提到上一级,然后就有两个 2-节点了,这时候就可以插入了。

在自上而下插入的过程中,我们还会把遇到的每一个 4-节点都分裂,这样保证了我们

红黑树

红黑树是为了解决二叉查找树不平衡的问题发明的。

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点永远是黑色的。
  3. 所有的叶子节点都是空节点(即 null),并且是黑色的。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点。)
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

Null 也算节点,从头到尾都是黑色节点,红色节点只能是内部节点。每条路径都包含相同的黑色节点。

红黑树保证的是没有一个节点长度是其他路径的 2 倍,而不是每一个路径之间的差在常数倍,比如说下面这个树。

为了保证平衡,也就是第 5 个条件,插入的新节点必须是红的,如果恰好插入到了一个黑色节点下面,那就结束了,如果插入到了一个红色节点下面,需要调整。

跳表

跳表显然不是一颗普通意义上的树,但是因为他的时间复杂度和红黑树类似,并且实现起来简单,不容易出 bug,所以很多时候,都把跳表作为红黑树的一个替代来使用,比如在 Redis 中。

B 树

B 树用于基于硬盘的数据库的索引。为什么不直接用二叉树呢?B 树本质上来说就是 2-3-4-n 树,因为硬盘读取相对于内存访问来说实在太慢了,所以减少树的层级有利于提升速度。

更多的树

有些题看起来是树,实际上是利用递归关系的,或者只是利用到了一个性质,但本质上是其他问题

参考资料

  1. https://stomachache007.wordpress.com/2017/03/12/%E4%B9%9D%E7%AB%A0%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-3-binary-tree-divide-conquer/
  2. https://blog.csdn.net/yang_yulei/column/info/easydatastruct
  3. https://web.archive.org/web/20200112020131/https://merunas.io/tree-data-structures/
  4. 《数据结构与算法分析:C 语言描述》
  5. https://stackoverflow.com/questions/8765558/why-dont-we-use-2-3-or-2-3-4-5-trees

Go 语言 Map 实战

相比 Rust 中尚未实现 IndexMut 的 Hash 类型来说,Go 中的 Map 实现度可以说是非常高了。

基本用法

Map 的类型是 map[KeyType]ValueType 的。也就是由 Key 类型和 Value 类型同时决定的。声明一个 Map:

var m map[string]int

不过一般很少有人这样写,还是生命并赋值比较常见,还是使用我们的 make 函数:

m = make(map[string]int)
commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}

基本上除了 slice,map 和 function 以外,都可以做 map 的键。

赋值

m["route"] = 66

获取值

i := m["route"]  // 如果 route 不存在,那么获取的就是对应的零值
j := m["non-exist"]

删除值

delete(m, "route")  // 如果不存在的话,也不会抛出异常。这里和 Python 不一样

判断是否存在

i, ok := m["route"]

遍历

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}

并发性

map 不是线程安全的。

使用 ssh 反向隧道登录没有 IP 的服务器

假设我们家里的服务器叫做 homeserver,没有公网 IP。然后我们有一台服务器叫做 relayserver,拥有公网 IP。

在家里执行

homeserver~$ ssh -fN -R 10022:localhost:22 relayserver_user@1.1.1.1

在服务器上就可以登陆啦

relayserver~$ ssh -p 10022 homeserver_user@localhost

然而这样链接还是很不稳定的,我们还是需要一个稳定的链接,这时候就可以使用 autossh 了,它会保持链接的稳定,自动重新连接。

autossh -M 20000 -f -N your_public_server -R 1234:localhost:22 -C

参考

  1. http://xmodulo.com/access-linux-server-behind-nat-reverse-ssh-tunnel.html
  2. https://superuser.com/questions/37738/how-to-reliably-keep-an-ssh-tunnel-open