非递归遍历二叉树到底有什么用

发表于 2021-05-03 Disqus：

准备过互联网公司的服务端岗位面试的人，对于二叉树的三种遍历方式想必是如数家珍。假设以类BinaryTree定义一棵二叉树

class BinaryTree:
    def __init__(self, left, right, value):
        self.left = left
        self.right = right
        self.value = value

实现一个前序遍历的算法便是信手拈来的事情

def preorder_traversal(tree, func):
    """前序遍历二叉树的每个节点。"""
    if tree is None:
        return
    func(tree.value)
    preorder_traversal(tree.left, func)
    preorder_traversal(tree.right, func)

随着行业曲率的增大，要求写出不使用递归的版本也没什么过分的

def iterative_preorder_traversal(tree, func):
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        func(node)
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

一直以来，我觉得这种用一个显式的栈来代替递归过程中隐式的栈的做法就是镜花水月。但最近却找到了它的一个用武之地——用于实现iterator。

`iterator`是个啥？

这年头，iterator已经不是什么新鲜事物了，许多语言中都有支持，维基百科上有一份清单列出了比较知名的语言的iterator特性。按照Python官方的术语表中的定义，iterator表示一个数据流，反复调用其__next__方法可以一个接一个地返回流中的下一项数据。将内置函数iter作用于list、str、tuple类型的对象，可以获得相应的迭代器

$ cat get_iter.py
# -*- coding: utf8 -*-
if __name__ == '__main__':
    values = [
        [1, 2, 3],
        'Hello, world!',
        (True, None),
    ]
    for v in values:
        print('type of iter({}) is {}'.format(v, type(iter(v))))
$ python get_iter.py
type of iter([1, 2, 3]) is <class 'list_iterator'>
type of iter(Hello, world!) is <class 'str_iterator'>
type of iter((True, None)) is <class 'tuple_iterator'>

写一个前序遍历的`iterator`

一个iterator对象必须要实现__iter__和__next__方法：

__iter__只需要返回iterator对象自身即可；
顾名思义，__next__负责返回下一个元素。

仔细观察一下前文中的iterative_preorder_traversal函数可以看出：

nodes = [tree]属于初始化逻辑；
len(nodes) > 0用于判断是应当抛出StopIteration，还是应当继续返回下一个值（nodes.pop()）；
最后四行就是负责填充nodes，好让它可以在下一次调用__next__的时候有值可以返回的。

到这里，iterator的具体实现代码已经呼之欲出了

class BinaryTreePreorderIterator:
    def __init__(self, root):
        nodes = []
        if root is not None:
            nodes.append(root)
        self.nodes = nodes

    def __iter__(self):
        return self

    def __next__(self):
        if len(self.nodes) == 0:
            raise StopIteration
        node = self.nodes.pop()
        if node.right is not None:
            self.nodes.append(node.right)
        if node.left is not None:
            self.nodes.append(node.left)
        return node.value

构造一棵这样的满二叉树

用BinaryTreePreorderIterator可以正确地打印出每一个节点的值

if __name__ == '__main__':
    tree = BinaryTree(
        BinaryTree(
            BinaryTree(None, None, 1), 
            BinaryTree(None, None, 3), 
            2,
        ),
        BinaryTree(
            BinaryTree(None, None, 5), 
            BinaryTree(None, None, 7), 
            6,
        ),
        4,
    )
    for n in BinaryTreePreorderIterator(tree):
        print('{}\t'.format(n), end='')
# 打印内容为：4	2	1	3	6	5	7

`iterator`的优势

显然，iterator比起preorder_traversal更为灵活——很容易在for-in循环内添加各种各样的控制逻辑：用continue跳过一些值，或者用break提前结束遍历过程。这些在函数preorder_traversal中做起来会比较别扭。

聪明的你应该已经发现了，大可不必将preorder_traversal拆解到一个构造方法和一个__next__方法中。用generator写起来明明更加直观

def preorder_generator(tree):
    """返回一个能够以前序遍历的次序遍历二叉树节点的generator。"""
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        yield node.value
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

但是，很多语言并不支持generator。与之相比，iterator要亲民得多，更容易移植。例如，即使是Common Lisp这种一穷二白的语言，也可以实现和Python的iterator以及for类似的效果

(in-package #:cl-user)

(defpackage #:com.liutos.binary-tree
  (:use #:cl))

(in-package #:com.liutos.binary-tree)

(defclass preorder-iterator ()
  ((nodes
    :initform nil)
   (tree
    :initarg :tree))
  (:documentation "前序遍历二叉树的迭代器"))

(defmethod initialize-instance :after ((instance preorder-iterator) &key)
  (with-slots (nodes tree)
      instance
    (when tree
      (push tree nodes))))

(defgeneric next (iterator)
  (:documentation "返回迭代器的下一个值。"))

(define-condition stop-iteration (error)
  ()
  (:documentation "Python中StopIteration异常的等价物。"))

(defmethod next ((iterator preorder-iterator))
  (with-slots (nodes) iterator
    (when (null nodes)
      (error 'stop-iteration))

    (let ((node (pop nodes)))
      ;; 一个节点的结构为：(值 左子树 右子树)
      (when (third node)
        (push (third node) nodes))
      (when (second node)
        (push (second node) nodes))
      (first node))))

(defmacro for-in (var iterator &body forms)
  "将iterator中的值逐个绑定到变量var上，并执行forms中的表达式。"
  (let ((iter (gensym)))
    `(let ((,iter ,iterator))
       (handler-case
           (loop
              (let ((,var (next ,iter)))
                ,@forms))
         (stop-iteration (c)
           (declare (ignorable c)))))))

(defparameter *tree*
  '(4 (2 (1 nil nil) (3 nil nil)) (6 (5 nil nil) (7 nil nil))))

(defun test-preorder-iterator ()
  "测试前序遍历迭代器。"
  (for-in n (make-instance 'preorder-iterator
                           :tree *tree*)
    (format t "~D~C" n #\Tab)))

后记

中序遍历和后序遍历也可以写成迭代器，证明略。

当你SET的时候，Redis到底在SET些什么

发表于 2021-04-17 Disqus：

准备过互联网公司的服务端岗位面试的人，对Redis中的5种数据类型想必是如数家珍。而网上很多面试题里也会出现这道题目

随着行业曲率的增大，光是知道有这些数据类型已经不够了，还得知道同一个类型也有不同的底层数据结构。例如同样是string类型，不同内容或不同长度会采用不同的编码方式：

127.0.0.1:6379> SET key1 "1"
OK
127.0.0.1:6379> SET key2 "value"
OK
127.0.0.1:6379> SET key3 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
OK
127.0.0.1:6379> TYPE key1
string
127.0.0.1:6379> TYPE key2
string
127.0.0.1:6379> TYPE key3
string
127.0.0.1:6379> OBJECT ENCODING key1
"int"
127.0.0.1:6379> OBJECT ENCODING key2
"embstr"
127.0.0.1:6379> OBJECT ENCODING key3
"raw"

而hash类型也有两种底层实现

127.0.0.1:6379>  HSET myhash field1 "Hello"
(integer) 1
127.0.0.1:6379>  HSET myhash2 field1 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
(integer) 1
127.0.0.1:6379> OBJECT ENCODING myhash
"ziplist"
127.0.0.1:6379> OBJECT ENCODING myhash2
"hashtable"

不知道你是否曾经好奇过，上文中的key1、key2、key3、myhash，以及myhash2这些键，与它们各自的值（前三个为string，后两个为hash）之间的关系又是存储在什么数据结构中的呢？

答案在意料之外，情理之中：键与值的关系，也是存储在一张哈希表中的，并且正是上文中的hashtable。

求证的办法当然是阅读Redis的源代码。

Redis命令的派发逻辑

阅读Redis的源码是比较轻松愉快的，一是因为其源码由简单易懂的C语言编写，二是因为源码仓库的README.md中对内部实现做了一番高屋建瓴的介绍。在README.md的server.c一节中，道出了有关命令派发的两个关键点

call() is used in order to call a given command in the context of a given client.

The global variable redisCommandTable defines all the Redis commands, specifying the name of the command, the function implementing the command, the number of arguments required, and other properties of each command.

位于文件src/server.c中的变量redisCommandTable定义了所有可以在Redis中使用的命令——为什么一个C语言项目里要用camelCase这种格格不入的命名风格呢——它的元素的类型为struct redisCommand，其中：

name存放命令的名字；
proc存放实现命令的C函数的指针；

比如高频使用的GET命令在redisCommandTable中就是这样定义的

1
2
3

{"get",getCommand,2,
 "read-only fast @string",
 0,NULL,1,1,1,0,0,0},

身为一名老解释器爱好者，对这种套路的代码当然是不会陌生的。我也曾在写过的、跑不起来的玩具解释器上用过类似的手法

Redis收到一道需要执行的命令后，根据命令的名字用lookupCommand找到一个命令（是个struct redisCommand类型的结构体），然后call函数做的事情就是调用它的proc成员所指向的函数而已

1	c->cmd->proc(c);

那么接下来，就要看看SET命令对应的C函数究竟做了些什么了。

`SET`命令的实现

redisCommonTable中下标为2的元素正是SET命令的定义

/* Note that we can't flag set as fast, since it may perform an
 * implicit DEL of a large key. */
{"set",setCommand,-3,
 "write use-memory @string",
 0,NULL,1,1,1,0,0,0},

其中函数setCommand定义在文件t_string.c中，它根据参数中是否有传入NX、XX、EX等选项计算出一个flags后，便调用setGenericCommand——顾名思义，这是一个通用的SET命令，它同时被SET、SETNX、SETEX，以及PSETEX四个Redis命令的实现函数所共用。

setGenericCommand调用了genericSetKey，后者定义在文件db.c中。尽管该函数上方的注释写着

All the new keys in the database should be created via this interface.

但~~人生不如意事十之八九~~事实并非如此。例如在命令RPUSH的实现函数rpushCommand中，调用了pushGenericCommand，后者直接调用了dbAdd往Redis中存入键和列表对象的关系。

言归正传。根据键存在与否，genericSetKey会调用dbAdd或dbOverwrite。而在dbAdd中，最终调用了dictAdd将键与值存入数据库中。

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

现在我们知道了，使用SET命令时传入的key和value，是存储在一个dict类型的数据结构中。

`HSET`命令的实现

依葫芦画瓢，Redis的HSET命令由位于文件t_hash.c中的函数hsetCommand实现，它会尝试转换要操作的hash值的编码方式。

1	hashTypeTryConversion(o,c->argv,2,c->argc-1);

如果hashTypeTryConversion发现要写入哈希表的任何一个键或者值的长度超过了server.hash_max_ziplist_value所规定的值，就会将hash类型的编码从ziplist转换为hashtable。server.hash_max_ziplist_value的值在文件config.c中通过宏设置，默认值为64——这正是上文中myhash2所对应的值的编码为hashtable的原因。

将思绪拉回到函数hsetCommand中。做完编码的转换后，它调用函数hashTypeSet，在编码为hashtable的世界线中，同样调用了dictAdd实现往哈希表中写入键值对。

殊途同归

结论

因此，在Redis中用以维持每一个键与其对应的值——这些值也许是string，也许是list，也许是hash——的关系的数据结构，与Redis中的一系列操作哈希表的命令——也许是HSET、也许HGET，也许是HDEL——所用的数据结构，不能说是毫不相关，起码是一模一样。

多重返回值的阵营九宫格

发表于 2021-03-14 Disqus：

通常在糊业务代码的时候，不管是函数、方法，还是宏，都只会有一个返回值。比如在C语言用于检查一个字符是否为阿拉伯数字的isdigit函数就只会返回是（1）或否（0）

#include <ctype.h>
#include <stdio.h>

int
main(int argc, char *argv[])
{
    char c = 'a';
    printf("isdigit('%c') is %d\n", c, isdigit(c));
    return 0;
}

但有时候如果一个函数、方法，或宏可以返回多个值的话会更加方便。例如，在Python中dict类型有一个实例方法get，它可以取得dict实例中与给定的键对应的值。但如果有一个键在字典中的值为None，那么光凭get的返回值无法准确判断这个键是否存在——除非你给它一个非None的默认值

# -*- coding: utf8 -*-
def test(d, key):
    print("d.get('{0}') is {1}\t'{0}' in d is {2}".format(key, d.get(key), key in d))

if __name__ == '__main__':
    d = {
        'foo': 'bar',
        'baz': None,
    }
    test(d, 'foo')
    test(d, 'baz')

发展了这么多年的编程语言，又怎么会连一次调用、多值返回这么简单的事情都做不到呢。事实上，有各种各样、各显神通的返回多个值的方法，我给其中的一些做了个分类

Lisp的`multiple-value-bind`

Common Lisp（简称为CL）的多重返回值当之无愧是其中最正统、最好用的实现方式。以它的内置函数truncate为例，它的第一个返回值为第一个参数除以第二个参数的商，第二个返回值为对应的余数

1
2
3

CL-USER> (truncate 10 3)
3
1

如果不加修饰地调用truncate，就像其它只返回一个值的函数一样，也只会拿到一个返回值

1
2
3

CL-USER> (let ((q (truncate 10 3)))
           (format t "q = ~D~%" q))
q = 3

除非用multiple-value-bind来捕获一个函数产生的所有返回值

CL-USER> (multiple-value-bind (q r)
             (truncate 10 3)
           (format t "q = ~D~8Tr = ~D~%" q r))
q = 3   r = 1

CL的方案的优点在于它十分灵活。即使将一个函数从返回单个值改为返回多个值，也不会导致原本调用该函数的位置要全部修改一遍——对修改封闭，对扩展开放（误）。

Go的多重返回值

踩在C语言肩膀上的Go也能够从函数中返回多个值。在io/ioutil包的官方文档中有大量的例子，比如用ReadAll方法从字符串衍生的流中读取全部内容，就会返回两个值

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes, err := ioutil.ReadAll(reader)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("bytes is %s", bytes)
}

Go以这种方式取代了C语言中用返回值表达成功与否、再通过指针传出读到的数据的风格。由于这个模式在有用的Go程序中到处出现，因此Gopher们用的都是定制的键盘（误）

不同于前文的multiple-value-bind，如果一个函数或方法返回多个值，那么调用者必须捕获每一个值，否则编译无法通过

➜  try cat try_read_all_ignore_err.go
package main

import (
	"fmt"
	"io/ioutil"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes := ioutil.ReadAll(reader)
	fmt.Printf("bytes is %s", bytes)
}
➜  try go build try_read_all_ignore_err.go
# command-line-arguments
./try_read_all_ignore_err.go:12:8: assignment mismatch: 1 variable but ioutil.ReadAll returns 2 values

这一要求也是合理的，毕竟多重返回值机制主要用于向调用者传递出错原因——既然可能出错，那么就必须要检查一番。

Python和Rust的解构

就像CL的truncate函数一样，Python中的函数divmod也可以同时返回两个数相除的商和余数，并且咋看之下也是返回多个值的形式

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, r = divmod(10, 3)
    print('q = {}\tr = {}'.format(q, r))

但本质上，这是因为Python支持解构，同时divmod返回的是一个由商和余数组成的元组。这样的做法与CL的真·奥义·多重返回值的差异在于，如果只想要divmod的第一个值，那么等号左侧也要写成对应的结构

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, _ = divmod(10, 3)
    print('q = {}'.format(q))

在支持解构的语言中都可以模仿出多重返回值，例如Rust

fn divmod(a: u32, b: u32) -> (u32, u32) {
    (a / b, a % b)
}

fn main() {
    let (q, r) = divmod(10, 3);
    println!("q = {}\tr = {}", q, r);
}

Prolog的归一

到了Prolog这里，画风就有点不一样了。首先Prolog既没有函数，也没有方法，更没有宏。在Prolog中，像length/2和member/2这样的东西叫做functor，它们之于Prolog中的列表，就犹如CL的length和member之于列表、Python的len函数和in操作符之于列表，JavaScript的length属性和indexOf方法之于数组……

其次，Prolog并不“返回”一个functor的“调用结果”，它只是判断输入的查询是否成立，以及给出使查询成立的变量值。在第一个查询中，length/2的第二个参数为变量L，因此Prolog给出了使这个查询成立的L的值4；第二个查询中没有变量，Prolog只是简单地给出查询是否成立；第三个查询中，Prolog给出了四个能够使查询成立的变量X的值。

由于Prolog会给出查询中每一个变量的值，可以用这个特性来模拟多重返回值。例如，可以让Prolog一次性给出两个数字的和、差、积，和商

麻烦之处在于就算只想要得到两数之和，也必须用占位符填在后三个参数上：jjcc(10, 3, S, _, _, _)。

作弊的指针与全局变量

尽管在开篇的时候提到了C语言中的函数无法返回多个值，但如果像上文的Prolog那般允许修改参数的话，C语言也是可以做到的，谁让它有指针这个强力特性呢。例如，stat(2)函数就会将关于一个文件的信息填充到参数中所指向的结构体的内存中

#include <stdio.h>
#include <sys/stat.h>

int
main(int argc, char *argv[])
{
    char *path = "./try_stat.c";
    struct stat buf;
    stat(path, &buf);
    printf("inode's number of %s is %llu\n", path, buf.st_ino);
    return 0;
}

查看man 2 stat可以知道struct stat类型中有非常多的内容，这显然也是一种多重返回值。同样的手法，在Go中也可以运用，例如用于把从数据库中读取出来的行的数据写入目标数据结构的Scan方法。

最后，如果只要能让调用者感知就行，那么全局变量未尝不是一种通用的多重返回值机制。例如在C语言中的strtol函数，就会在无法转换出任何数字的时候返回0并设置errno，因此检查errno是必须的步骤

#include <stdio.h>
#include <stdlib.h>
#include <sys/errno.h>

void try_conversion(const char *str)
{
    long num = strtol(str, NULL, 10);
    if (errno == EINVAL || errno == ERANGE)
    {
        char message[64];
        snprintf(message, sizeof(message), "strtol(\"%s\")", str);
        perror(message);
        return;
    }
    printf("strtol(\"%s\") is %ld\n", str, num);
}

int
main(int argc, char *argv[])
{
    try_conversion("233");
    try_conversion("0");
    try_conversion("lisp");
    return 0;
}

鉴于errno是一个全局变量，strtol的使用者完全有可能忘记要检查。相比之下，Go的strconv包的函数都将转换过程中的错误以第二个参数的形式返回给调用者，用起来更安全。

后记

按照《代码写得不好，不要总觉得是自己抽象得不好》这篇文章的说法，代码写成什么样子完全是由产品经理决定的。但产品经理又怎么会在意你用的技术是怎么实现多重返回值的呢。综上所述，这个特性没用（误）。

全文完。

终端看片指日可待

发表于 2021-02-27 Disqus：

序言

在旧文《如何写一个命令行的秒表》中，借助命令tput，我实现了“原地更新”所输出的时分秒的效果

其中用到的是ASCII转义序列\x1b[8D和\x1b[0K。除此之外，ASCII转义序列还有许多其它功能。例如，可以用来定制输出内容的前景色

将转义序列中的参数38改为48，可以定制输出内容的背景色

将打印内容改为两个空格，看起来就像是在一块黑色的画布上涂了一个红色的方块

既然如此，只要尺寸合适，就可以在终端打印出一张图片，只需要将每一个像素的颜色作为背景色，在坐标对应的行列上输出两个空格即可。如果能抹掉输出的内容并在同样的位置上打印一张不同的图片，甚至可以实现动画的效果。

百闻不如一见，下面我用Python演示一番。

把GIF装进终端

要想用前文的思路在终端中显示一张GIF图片，必须先得到GIF图片每一帧的每个像素的颜色才行。在Python中使用名为Pillow的库可以轻松地解析GIF文件，先安装这个库

➜  /tmp rmdir show_gif
➜  /tmp mkdir show_gif
➜  /tmp cd show_gif
➜  show_gif python3 -m venv ./venv
➜  show_gif . ./venv/bin/activate
(venv) ➜  show_gif pip install Pillow
Collecting Pillow
  Using cached Pillow-8.1.0-cp39-cp39-macosx_10_10_x86_64.whl (2.2 MB)
Installing collected packages: Pillow
Successfully installed Pillow-8.1.0
WARNING: You are using pip version 20.2.3; however, version 21.0.1 is available.
You should consider upgrading via the '/private/tmp/show_gif/venv/bin/python3 -m pip install --upgrade pip' command.

接着便可以让它读入并解析一张GIF图片

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        pass

然后将每一帧都转换为RGB模式再遍历其每一个像素

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                pass

调用Image类的实例方法load得到的是一个PixelAccess类的实例，它可以像二维数组一般用坐标获取每一个像素的颜色值，颜色值则是一个长度为3的tuple类型的值，其中依次是像素的三原色的分量。

从ANSI escape code词条的24-bit小节中得知，使用参数为48;2;的转义序列，再接上以分号分隔的三原色分量即可设置24位的背景色

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')

在每次二重循环遍历了所有像素后，还必须清除输出的内容，并将光标重置到左上角才能再次打印，这可以用ASCII转义序列来实现。查阅VT100 User Guide可以知道，用ED命令可以擦除显示的字符，对应的转义序列为\x1b[2J；用CUP命令可以移动光标的位置到左上角，对应的转义序列为\x1b[0;0H。在每次开始打印一帧图像前输出这两个转义序列即可

import sys

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')

最后，只需要在每次打印完一帧后，按GIF文件的要求睡眠一段时间即可。每一帧的展示时长可以从info属性的键duration中得到，单位是毫秒

import sys
import time

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                print('\x1b[48;2;{};{};{}m  \x1b[0m'.format(*colors), end='')
            print('')
        time.sleep(rgb_frame.info['duration'] / 1000)

现在可以看看效果了。我准备了一张测试用的GIF图片，宽度和高度均为47像素，共34帧

让它在终端中显示出来吧

一点微小的改进

你可能留意到了，前文的演示效果中有明显的闪烁，这是因为打印ASCII转义序列的速度不够快导致的。既然如此，可以将一整行的转义序列先生成出来，再一次性输出到终端。改动不复杂

import sys
import time

from PIL import Image, ImageSequence

if __name__ == '__main__':
    path = sys.argv[1]
    im = Image.open(path)
    for frame in ImageSequence.Iterator(im):
        rgb_frame = frame.convert('RGB')
        pixels = rgb_frame.load()
        print('\x1b[2J\x1b[0;0H', end='')
        for y in range(0, rgb_frame.height):
            last_colors = None
            line = ''
            for x in range(0, rgb_frame.width):
                colors = pixels[x, y]
                if colors != last_colors:
                    line += '\x1b[0m\x1b[48;2;{};{};{}m  '.format(*colors)
                else:
                    line += '  '
                last_colors = colors
            print('{}\x1b[0m'.format(line))
        time.sleep(rgb_frame.info['duration'] / 1000)

但效果却很显著

全文完

此数绵绵无绝期——欧拉计划第66题

发表于 2021-02-11 更新于 2021-02-12 Disqus：

仅以此文膜拜八年前的自己

序言

欧拉计划（Project Euler）就像LeetCode，是一个编程答题的网站。不同于LeetCode的是，欧拉计划只要求用户提交最终答案即可（一般是一个数字），而不需要完整代码。因此，可以尽情地使用自己喜欢的编程语言——不少题目甚至光靠笔和纸便能解决。

欧拉计划的第66题非常有意思，它的题目很简单，就是要求找出在不大于1000的整数中，以哪一个数字为丢番图方程的系数，可以得到所有最小解中的最大值。

可以很容易地看出方程有一个直观的暴力算法：让y从1开始递增，对于每一个y，计算公式Dy^2+1的值。如果该值为平方数，那么它的平方根就是最小的x解。再依照这个算法求解所有D不大于1000的方程，便可以求出题目的答案。很容易用Python写出这个算法

# -*- coding: utf8 -*-
import math

def is_square(num: int) -> bool:
    return math.isqrt(num) ** 2 == num

def find_x(D: int) -> int:
    """
    求出给定D时，满足题目所给的丢番图方程的最小的x。
    """
    assert not is_square(D)
    y = 1
    while True:
        candidate = D * y * y + 1
        if is_square(candidate):
            return math.isqrt(candidate)
        y += 1

def solve_66(limit):
    """
    找出不大于limi的D中，使find_x的返回值最大的那一个数字。
    """
    max_D = None
    max_x = None
    D = 2
    while D <= limit:
        if is_square(D):
            D += 1
            continue
        x = find_x(D)
        if max_x is None or x > max_x:
            max_D = D
            max_x = x
        D += 1
    return max_D, max_x

if __name__ == '__main__':
    D, x = solve_66(7)
    print('D is {} and x is {}'.format(D, x))

但如果将上限limit提升为1000，这个算法在有生之年是算不出结果的。

要想解决这一题，需要借助数学的力量。

佩尔方程

八年前第一次做这一题的时候，经过一番搜索，我从这篇文章中知道了题目中的方程叫做佩尔方程。它有标准的解法，但需要用到连分数。那么什么是连分数呢？

连分数不是一种新的数系，只是小数的另一种写法。例如可以把分数45除以16写成下面的形式

就像定义递归的数据结构一样，可以给连分数一个递归的定义。连分数要么是一个整数，要么是一个整数加上另一个连分数的倒数。除了上面的形式，连分数也可以写成更节省篇幅的样子。比如把45除以16写成[2;1,4,3]，即把原本的式子中所有的整数部分按顺序写在一对方括号之间。这种记法，看起来就像是编程语言中的数组一般。

如果用数组[2;1,4,3]的不同前缀来构造分式，那么结果依次为2/1、3/1、14/5。它们是这个连分数的渐进连分数，而佩尔方程的一组解，就来自于渐进连分数的分子和分母。

以系数为7的佩尔方程为例，先计算出根号7的连分数，然后依次尝试它的渐进连分数。前三个分别为2/1、3/1、5/2，都不是方程的解。第四个渐进连分数8/3才是方程的解。如果继续提高连分数的精度，还会找到第二个解127/48。继续找，还有更多，而8则是其中最小的x。

所以，想要快速算出佩尔方程的解，最重要的是找到计算一个数的平方根的连分数的算法。

计算平方根的连分数的错误方法

要计算一个数字的连分数，最重要的便是要算出所有的整数部分（a0、a2、a2等）。它们都可以依据定义直接计算

推广到一半情况，如果用变量n存储开平方的数字，用numbers存储所有已知的整数，那么用Python可以写出下面的算法来计算出下一个整数

# 计算连分数数列的下一个数字
import math

def compute_next_integer_part(n, numbers):
    v = math.sqrt(n)
    for a in numbers:
        v = 1 / (v - a)
    return int(v)

if __name__ == '__main__':
    n = 14
    numbers = [3, 1, 2, 1]
    v = compute_next_integer_part(n, numbers)
    print('下一个数字为{}'.format(v))

遗憾的是，这个算法算出来的数字会因为计算上的精度误差而导致失之毫厘谬以千里。

计算平方根的连分数的正确方法

要想计算出正确的结果，就需要尽可能地消除在计算1 / (v - a)的时候引入的误差，因此必须把浮点数从分母中除去。

在这个网站中，作者以计算根号14的连分数为例，列出了一个表格

可以看到x1、x2，以及x3都是形如(sqrt(n)+a)/b这样的格式，这样的式子更利于控制误差。那么是否每一个待计算的x都符合这种格式呢？答案是肯定的，可以用数学归纳法予以证明（为了方便写公式，用LaTeX写好后截了图）

在这个证明过程中，还得到了分子中的a以及分母中的b的递推公式，现在可以写出正确的计算连分数整数部分的代码了。

用Common Lisp实现上述算法

为了在实现这个算法的同时还要写出优雅的代码，我会用上Common Lisp的面向对象特性。首先是定义一个类来表示一个可以不断提高精度的连分数

(defpackage #:com.liutos.cf
  (:use #:cl))

(in-package #:com.liutos.cf)

(defclass <cf> ()
  ((a
    :documentation "数学归纳法中、分子中与平方根相加的数"
    :initform 0)
   (b
    :documentation "数学归纳法中的分母"
    :initform 1)
   (numbers
    :documentation "连分数中的整数部分依次组成的数组。"
    :initform nil)
   (origin
    :documentation "被开平方的数字"
    :initarg :origin))
  (:documentation "表示整数ORIGIN的平方根的连分数。"))

接着再定义这个类需要实现的“接口”

(defgeneric advance (cf)
  (:documentation "让连分数CF提高到下一个精度。"))

(defgeneric into-rational (cf)
  (:documentation "将连分数CF转换为有理数类型的值。"))

最后来实现上述两个接口

(defmethod advance ((cf <cf>))
  "根据递推公式计算出下一批a、b，以及连分数的整数部分。"
  (let* ((a (slot-value cf 'a))
         (b (slot-value cf 'b))
         (n (slot-value cf 'origin))
         (m (truncate (+ (sqrt n) a) b)))
    (let ((a (- (* b m) a))
          (b (/ (- n (expt (- a (* b m)) 2)) b)))
      (setf (slot-value cf 'a) a
            (slot-value cf 'b) b
            (slot-value cf 'numbers) (append (slot-value cf 'numbers) (list m))))
    (values)))

(defmethod into-rational ((cf <cf>))
  (let* ((numbers (reverse (slot-value cf 'numbers)))
         (v (first numbers)))
    (dolist (n (rest numbers))
      (setf v
            (+ n (/ 1 v))))
    v))

在实现into-rational方法上，Common Lisp的有理数数值类型给我带来了极大的便利，它使我不必担心计算(/ 1 v)的时候会引入误差，代码写起来简单直白。

解题

乘胜追击，用Common Lisp解答第66题

(defun find-min-x (D)
  (let ((cf (make-instance '<cf> :origin D)))
    (loop
       (advance cf)
       (let* ((ratio (into-rational cf))
              (x (numerator ratio))
              (y (denominator ratio)))
         (when (= (- (* x x) (* D y y)) 1)
           (return-from find-min-x x))))))

(defun square-p (n)
  (let ((rt (sqrt n)))
    (= rt (truncate rt))))

(defun pro66 (&optional (bnd 1000))
  (let ((target-d)
	(max-x 0))
    (loop :for i :from 2 :to bnd
       :when (not (square-p i))
       :do (let ((x (find-min-x i)))
	     (if (> x max-x)
		 (setf target-d i
		       max-x x))))
    (values target-d max-x)))

答案的D是多少就不说了，不过作为答案的x是16421658242965910275055840472270471049。有兴趣的读者可以试一下暴力解法要花多久才能算到这个数字。