Information Collection and Use

This application does not:

• Collect or use any personal information
• Store any personal data
• Share any information with third parties

Because we do not process any personal information, you can use this application without concern for data tracking, profiling, or distribution.

Changes to This Privacy Policy

This Privacy Policy may be updated from time to time. You are encouraged to review this page periodically to stay informed of any changes. Any updates to this policy will be posted on this page to keep you aware of how your information is protected.

If you have any questions about this Privacy Policy, feel free to contact us.

Email: dreace@foxmail.com

We will do our best to respond and provide assistance as soon as possible.

Thank you for using the app.

软硬件

• 手机：iPhone 12（iOS 16.1）
• 路由器：极路由 4（OpenWrt）2.4GHz + 5GHz 分开的信号

尝试路径

智能设备基本都使用 2.4G WiFi，因此只需要调整 2.4G 的设置就行，不用去动 5G 的配置。

最开始 2.4G 的配置是：

• 名字（SSID）没有非 ASCII 字符
• N 模式
• 自动选择信道
• 20MHz
• 加密 WPA2/WPA3，算法自动

尝试：

1. 模式改为 Legacy，没有用。随后恢复
2. 勾选「允许使用旧的 802.11b 速率」，没有用。随后恢复
3. 加密改为 WPA2，没有用。随后恢复
4. 加密改为 WPA，可以连接
5. 加密改为 WPA/WPA2，可以连接

结论是修改只需要修改加密方式为 WPA/WPA2 或 WPA 即可正常连接小米的智能设备。

前言

使用 C/C++ 编写的程序可以编译为共享库（Shared Library，Linux 中后缀为 .so）供其他程序在运行时加载并使用，Python 的标准库 ctypes 实现了加载、函数寻址、函数调用等方法可以方便地使用共享库¹。

生成共享库

假设有如下 C++ 代码实现了 64 位整型的加法和乘法、截取子字符串，以及一个名叫 Point 的结构体有 x 和 y 两个 32 位整型成员、两个 Point* 类型相加的函数。演示代码所以 Substr 函数实现偷懒了。

#include <cstdint>#include <string>extern "C" {    typedef struct Point {        int32_t x;        int32_t y;    } Point;    Point PointAdd(Point* a, Point* b) {        Point result;        result.x = a -> x + b -> x;        result.y = a -> y + b -> y;        return result;    }    int64_t Add(int64_t a, int64_t b) {        return a + b;    }    int64_t Mul(int64_t a, int64_t b) {        return a * b;    }    const char* Substr(char* str, int64_t start, int64_t length) {        return std::string(str).substr(start, length).c_str();    }}

假设源码文件名为 functions.cpp，使用 g++ 编译上述代码生成共享库：

g++ -fPIC -shared -lstdc++ -o libfunctions.so functions.cpp

参数含义：

• -fPIC：生成地址无关代码，生成共享库时通常配合使用该参数，如果设置了该参数，宏__pic__ 和 __PIC__ 会被定义且值为 2
• -shared：生成共享库，通常需要同时设置 -fPIC
• -lstdc++：链接 C++ 标准库
• -o：指定输出文件，这里为 libfunctions.so

extern "C" 告诉编译器在编译时 {} 中的函数名字需要与 C 兼容，详见 What is the effect of extern "C" in C++? - Stack Overflow。

Python 中使用共享库

Python 中导入 ctypes 指定共享库（.so 文件）加载后声明函数的参数列表和返回值类型（基础类型可声明返回值类型）即可调用共享库中的函数。

简单函数

以调用 Add 函数为例：

import ctypesfunctions = ctypes.CDLL("./libfunctions.so")functions.Add.argtypes = [ctypes.c_int64, ctypes.c_int64]print(functions.Add(1, 2))

其中 argtypes 声明了 Add 函数的参数列表：两个 int64 参数，执行 Python 文件就可以得到结果 3。

调用 Mul 函数也是类似的：

functions.Mul.argtypes = [ctypes.c_int64, ctypes.c_int64]print(functions.Mul(233, 2))

可以得到结果 466。

非基础类型参数

Substr 的第一个参数是字符指针（char*）因此第一个参数应该使用 c_char_p，同时返回值也是字符指针而不是基础类型因此需要声明返回值类型：

functions.Substr.argtypes = [ctypes.c_char_p, ctypes.c_int64, ctypes.c_int64]functions.Substr.restype = ctypes.c_char_pprint(functions.Substr(ctypes.c_char_p("Hello World".encode()), 2, 5).decode())

构造 c_char_p 时可以使用 bytes 或者 int（指针），这里直接将字符串编码传入，执行得到结果 llo W。

使用结构体

在 Python 中定义结构体后可以将结构体作为参数传递给共享库中的函数：

class Point(ctypes.Structure):    _fields_ = [("x", ctypes.c_int32), ("y", ctypes.c_int32)]

定义 Point 结构体，有两个名为 x 和 y，类型是 int32 的参数，然后声明 PointAdd 函数：

PointAdd = functions.PointAddPointAdd.argtypes = [ctypes.POINTER(Point), ctypes.POINTER(Point)]PointAdd.restype = Point

构造两个 Point 结构体调用 PointAdd 函数：

p_a = Point(1, 2)p_b = Point(3, 4)p_result = PointAdd(p_a, p_b)print(p_result.x, p_result.y)

执行得到结果 4 6。

使用 CMake

假设目录结构如下 ：

.├── CMakeLists.txt├── include│   └── point.h└── src    └── functions.cpp

include 存放项目头文件，src 存放源文件，point.h 中是 Point 结构体定义：

#include <cstdint>extern "C" {    typedef struct Point {        int32_t x;        int32_t y;    } Point;}

functions.cpp 除移动到 point.h 中内的容外不变，最小化 CMakeLists.txt 文件：

cmake_minimum_required(VERSION 2.8.9)project (Functions)set(CMAKE_CXX_STANDARD 11)include_directories(./include)aux_source_directory(./src DIR_SRCS)add_library(Functions SHARED ${DIR_SRCS})

编译后修改 Python 中的 functions = ctypes.CDLL("./libfunctions.so") 路径为新的 .so 路径即可使用。

背景

周五下班回家后开电脑发现屏幕一直没有反应，拔插 DP 线也没有效果，并且发现主板的 boot 灯一直亮着，说明在启动中但是没有成功。开关几次电源还是没有效果后开始慌了。

尝试解决

拔插显卡

显卡是刚买的 RX 6900 XT，在默默祈祷中拆下面板把显卡取下来再插回去，但是通电后依然没有效果，显示器依旧提示没有信号输入。

更换显卡

查阅资料后没有获得有效信息，但想起来之前用的亮机卡（750 Ti）还在，就换上了试试。

换上 750 Ti 显示器有信号了，提示内存超频失败（内存是芝奇皇家戟 8Gx4，自动超频到 3600），这下问题找到了，进入 BIOS 禁用 XMP，然后重启，成功进入系统。

此后多次尝试重启系统均成功，然后将显卡换回 RX 6900 XT 也成功启动。

总结

原因未知，但是旧显卡留着还是有用的。

2020年9月28日更新：已拿到意向书。

第 1 面

1. 自我介绍
2. 项目相关
   1. 解决的最困难的问题
3. 算法：数组中出现次数最多的数字
4. 算法：字典树
5. Python 中元组和列表
6. Python 中判断对象是否为某个类的实例
7. Python 中 with
8. 全局解释器锁
9. Python 值传递和引用传递
10. 如何实现一个队列
11. 平衡二叉树和普通二叉树的区别
12. B+ 树
13. 进程间通信方式
14. TCP 和 UDP 区别
15. HTTP 状态码

第 2 面

1. 自我介绍
2. 项目相关
3. 算法：给定权限字符串"[1, 2, 3]" 表示白名单，"[1, 2, 3]" 表示黑名单，给定一个 ID，判断是否拥有权限
4. C++ 中 char* 和 string
5. Python 中生成器
6. Python 中装饰器
   1. 手写一个装饰器
7. Python 中列表和元组
   1. 什么情况可以使用元组，但是不能使用列表
8. Python 中值传递和引用传递
9. 反问

第 3 面（CTO 面）

从二面结束到三面差不多过了一个月，三面是去北京线下面试。

1. 智力题：有四瓶药，其中三瓶 A 药每粒重 3g，一瓶 B 药每粒重 4g，一个电子秤称一次找出哪个是 B 药
2. 开放性问题：估计一栋二十层楼房的重量
3. 真·手撕代码：链表反转
4. 反问

整个CTO 面试流程很快，体验也很好。结束之后 HR 又来问了一些常规的问题，然后带着去看了一下公司的技术办公区。

一个例子

反面教材

for (int i = n; i >= 0; i--) {int d = pos - stop[i].f;while (tank - d < 0){if (que.empty()) {puts("-1");return 0;}tank += que.top();que.pop();ans++;}tank -= d;pos = stop[i].f;que.push(stop[i].s);}

完全看不清这段代码在干什么，作用域尤其不清楚，如果看到上千行这样的代码会直接崩溃。

正面例子

那么格式化后，是这样的：

for (int i = n; i >= 0; --i) {    int d = pos - stop[i].f;    while (tank - d < 0) {        if (que.empty()) {            puts("-1");            return 0;        }        tank += que.top();        que.pop();        ++ans;    }    tank -= d;    pos = stop[i].f;    que.push(stop[i].s);}

代码含义一下子就明了了 。

编码原则

• 增加代码可读性
• 避免混淆
• 保持代码风格一致

关于注释

尽量使用单行注释 // ... 而不是多行注释 /* ... */，因为在大多数时候可以使用 IDE 快捷键 Ctrl + / 可以添加或取消单行注释，并且 // 后要添加空格，不同行的注释需要对齐，为函数和控制语句添加注释时，可以将注释放在上一行，例如：

for (int i = n; i >= 0; --i) {    int d = pos - stop[i].f;    // 一个操作    while (tank - d < 0) {        // que 为空        if (que.empty()) {            puts("-1"); // 输出            return 0;   // 返回        }        tank += que.top();  // 取栈顶元素        que.pop();          // 弹出栈顶        ++ans;              // 更新答案    }    tank -= d;    pos = stop[i].f;    que.push(stop[i].s);}

关于空行

头文件、宏定义与主要实现部分使用空行分开，如：

#include <iostream>#include <vector>bool cmp(int a, int b){    //Do something here}

同一个函数不同功能代码间使用空行分开。

关于空格

在赋值运算符、逻辑运算符、位运算符、算术运算符前后添加空格，例如 name = "Alice" 不能写成 name="Alice"。

在引用操作符 .、->、[] 前后不能添加空格。

添加空格的目的是让独立的 token 分开，加快阅读代码的速度。

关于缩进

按照代码逻辑水平缩进，缩进时使用 Tab 或四个 Space 或两个 Space 作为一个缩进单位，全局保持一致即可。 左大括号 { 使用 Java 风格，即放在上一行末，在前一个字符和 { 之间添加一个空格，也可选择左大括号放在新行，全局保持一致即可。

平行逻辑代码列对齐，子逻辑与上层逻辑有一个单位的缩进，例如：

for (int i = 0; i < n; ++i) {    scanf("%s", field[i]);}for (int i = 0; i < n; ++j) {    for (int j = 0; j < m; ++j) {        if (field[i][j] == 'W') {            dfs(i, j);            ++count;        }    }}

关于控制语句

无论控制语句有几行都要用使用 {、} 括起来，例如：

for (int i = 0; i < n; ++i) {    ++x;}if (!s.empty()) {    res = 1;}

不能写成：

for (int i = 0; i < n; ++i)    ++x;if (!s.empty())    res = 1;

一行只写一个语句

while (x != s) {    ++x;}

不能写成：

while (x != s) { ++x; }

或：

while (x != s) ++x;

命名

不要使用拼音，尤其是拼音缩写，会给其他阅读代码的人带来困扰。

在命名时尽量使变量名表达出它的含义，不要过度使用缩写。在 for 循环控制中可以使用 i、j、k 等简短的变量，以减少键入的时间。

变量使用下划线分割，如 list_name 、 lake_field，当然也可以选择小驼峰命名风格 listName 、 lakeField，或者其他自己喜欢的风格。

常量、宏定义使用全大写，如 const int MAX = 100; #define MAXN 100005。

函数名使用小驼峰命名，如 string getStudentNumber(...)、int maxOfTree(...)。

强烈建议类名使用大驼峰命名，如 class Solution{...};。

不建议的操作

编码时不建议使用第一眼看不出含义的特性，即使该特性是合法的。

不要这样写：

a = b = 5;c += d++;

而是写成这样：

a = 5;b = 5;++d;c += d;

不要这样写：

if (m -= d) {    // Do something here}

而是写成这样：

m -= d;if (m != 0) {    // Do something here}

第 1 面

1. 自我介绍
2. 项目模块划分
3. MySQL
   1. 主从
   2. 隔离级别
   3. 日志
   4. MVCC
   5. 如何评估 SQL 语句的性能
   6. 为什么选用 InnoDB
4. B+ 树对比其他树结构的优点
5. Redis 为什么高效
6. Redis 持久化
7. 算法：剑指 Offer 40. 最小的k个数
   1. 说思路和时间复杂度
8. 一件自己比较自豪的事
9. 反问

第 2 面

1. GET 和 POST 区别
2. DDoS 攻击，如何防御
3. 客户端如何保存登录状态
4. 跨域登录状态保持，从 taobao.com 切换到 tmall.com
5. 缓存（cache）和缓冲（buffer）的区别
6. 磁盘寻道算法
   1. 针对存在高优先级任务如何改进
7. 软中断和硬中断
8. 用户态和内核态，什么情况会切换到内核态
9. AVL 树和红黑树的对比
10. 如何优化快排
11. 为车牌号排序设计一个算法
12. 在二叉搜索树中找比指定值大的最小节点
13. 一片区域（矩阵）有若干水池（0）和陆地（1），求每个陆地节点到水池的最短距离
14. 反问

8月1日完成奇安信笔试，8月8日一口气完成三轮面试，到8月14日收到意向书邮件，秋招之路的第一份 Offer，感谢奇安信。

三轮面试包括 2 次技术面和 1 次 HR 面。

第 1 面

本来是 Python 面试，说着说着就到 Golang 了。

1. 自我介绍
2. Python 类可以定义哪几种方法
   1. 静态方法和类方法应用场景
3. Python 有哪些数据结构
4. Python 如何实现私有成员、方法
5. Python 协程
6. 介绍项目
   1. 做爬虫的时候用了哪些库
   2. 后端怎么部署的
7. Docker 数据卷
8. Dockerfile 中用过哪些指令
9. TCP/IP 模型有哪些层
   1. 哪些层提供的是可靠的服务
10. 有哪些常用的数据结构
11. 有哪些排序算法
    1. 哪些是稳定的
12. Golang 怎么实现面向对象
13. Golang 成员访问控制
14. Golang 有哪些数据结构
15. 算法：1~n 自然数组排序，不能直接 arr[i] = i + 1，要求时间 $O(n)$
16. 算法：剑指 Offer 42. 连续子数组的最大和

第 2 面

1. 为什么还在家
2. 工作地点有什么想法
3. 为什么不考虑读研
4. 最近在干什么
5. 项目架构设计怎么来的
6. 看 GitHub 上的项目问了一些相关问题
   1. 怎么编排 Docker 容器的
   2. 有没有用过 ORM 框架
   3. 自己拼接 SQL 怎么做防注入
   4. 怎么做的 API 限流
7. 反问

第 3 面（HR 面）

1. 自我介绍
2. 在项目或比赛中承担什么角色
3. 怎么理解的网络安全
4. 职业规划
5. 找工作有没有倾向
6. 反问

一共经历了 1 次电话面（简历面），3 次技术面，1 次「GM/EVP/面委会」面和 1 次 HR 面，希望可以拿到 Offer，提早结束提心吊胆的秋招。

第 0 面（电话面）/8月4日

1. 自我介绍
2. 项目
   1. 数据库存密码方案
3. TCP 三次握手
4. 服务器超时没有收到第三次握手会发什么报文

第 1 面/8月5日

没有录音，有些问题想不起来了。

1. 实现 atoi 函数
2. 实现 C++ 单例模式
3. 实现快排
4. C++ 静态成员
5. C++ 静态变量（成员）存放位置
6. TLS 握手过程
   1. 证书包含哪些信息
   2. 客户端如何确认服务器身份
   3. 有哪些签名算法
   4. 双向认证
7. Redis 的事务
8. 中间人攻击
9. DDoS 攻击

第 2 面/8月8日

对方介绍说是小组 leader，如果拿到 Offer 的话会在他手下干活，最后还说了一下具体的业务。录音出问题，只能回忆起部分问题。

1. 实现 TopN 查找
2. InnoDB 主键索引和辅助索引结构
3. C++ 中 map 与 unordered_map 区别，和适用场景
4. 家在哪里，能不能接受去深圳

实际上不止这些问题，如果能想起来再补上。

第 3 面/8月9日

1. 项目相关
2. 是否对编程感兴趣
3. 做项目的时候怎么选择技术栈
4. 在团队中什么地位，周围人怎么评价自己
5. 职业规划
6. 十亿个 QQ 号判断一个是否在其中，性能达到 10 万 QPS
7. 设计一个保障服务高可用的模型
8. 有没有其他 Offer
9. 有没有业务偏好

第 4 面（总监面）/8月13日

能感受到对面非常忙，八分钟就结束了。

1. 快速自我介绍
2. 怎么定义「高可用」
3. 反问
4. 职业规划

第 5 面（HR 面）/8月14日

1. 自我介绍
2. 职业规划
   1. 什么样的工作算满意
3. 开发方向偏好
4. 短板，有没有去补足
5. 有没有其他 Offer
6. 和前面面试官聊得怎么样
7. 没有实习吗
8. 最有成就感的事
9. 在深圳工作有问题吗，家里人支不支持

最后问了一下 HR 什么时候出结果，回答说等其他人面试完，一到两周尽快给反馈。

定位问题

查阅资料得知可能是 cheerio 引起的问题¹，在 node_modules 下查找发现 hexo-katex 引入了 cheerio 并设置了要编码实体，

定位到的代码（node_modules/hexo-katex/index.js:16）：

var $ = cheerio.load(data.content, { decodeEntities: true })

解决

既然问题找到了，解决办法也很简单，将 true 改为 false：

var $ = cheerio.load(data.content, { decodeEntities: false })

但是，直接修改 node_modules 下的文件可能会丢失更改，或者需要在其他环境使用修改不能同步。由于我的博客是使用 CI/CD 自动编译并部署的，直接修改文件会比较麻烦。

这时就需要 patch-package 了，patch-package 可以将更改固定，在每次安装依赖时自动应用更改。

安装

首先要安装 patch-package：

yarn add patch-package postinstall-postinstall

如果使用 npm 则是：

npm i patch-package

然后在 package.json 的 scripts 字段下新增：

"postinstall": "patch-package",

表明在依赖安装后会执行 patch-package。

固定修改

首先保存已修改的文件，然后执行：

yarn patch-package <修改了的包名>

或者使用 npx：

npx patch-package <修改了的包名>

此时将看到类似：

yarn run v1.22.4$ patch-packagepatch-package 6.2.2Applying patches...hexo-katex@0.0.13 ✔Done in 1.13s.

的输出，表明修改已经固定。

在 patches 目录下会有对应的 .patch 文件，本文对应的文件如下：

diff --git a/node_modules/hexo-katex/index.js b/node_modules/hexo-katex/index.jsindex cf8daf8..98fb8c6 100644--- a/node_modules/hexo-katex/index.js+++ b/node_modules/hexo-katex/index.js@@ -13,7 +13,7 @@ hexo.extend.filter.register('after_post_render', function(data) {    if (!cheerio) cheerio = require('cheerio') -  var $ = cheerio.load(data.content, { decodeEntities: true })+  var $ = cheerio.load(data.content, { decodeEntities: false })    if ($('.math').length > 0) {     linkTag = util.htmlTag('link', {

应用更改

只要将上述生成的文件提交到版本控制系统，在其他环境安装依赖时直接使用 yarn install 或 npm install 即可同步修改。

（迁移文章，本文写于2019年8月3日）本人维护的一个项目 中北信息 小程序需要模拟登录来获取信息，这就需要在后台识别验证码。需要识别的验证码比较简单且为纯数字，有简单到可以忽略不计的变形，像下面这个样子。

可以看到稍微有一点噪点，应该是压缩解压过程造成的（JPG 是有损压缩）。

这是近乎标准印刷体的四位数字，只是有稍微倾斜，最开始想到的办法是 OCR 。

最初使用 Tesseract 进行本地 OCR 。效果不是很理想，重要问题是 Tesseract 是通用 OCR，他会识别所有的英文字符和标点，这就造成大量的识别不准确。而且 Tesseract 是一个神经网络，在本地运行相当耗费资源。在平时可以应付大部分情况，但在访问高峰时会消耗大量时间在多个识别线程中切换，甚至直接造成服务器宕机。 在没有新的解决方案之前使用了接近一年，只能说勉强能用。

前不久，发现百度云的 OCR 提供每天 5 万次的免费调用，测试发现可以使用且效果不错。使用一段时间后发现一些问题，异步的调用方式造成的延迟不可忽略，尤其是网络延迟。测试发现这个解决方案每个验证码识别有将近 1s 的网络延迟，这使得后台响应时间被延长，影响用户体验。虽然百度云不会将数字识别成其他字符，但经常出现只识别出两位数字的情况造成大量重试，更加影响性能。

两度更换解决方案后，还是没能找到令人满意的方案。决定自己实现验证码的识别，这里不需要训练神经网络，直接通过规则匹配能得到很好的性能与效果，最终单个验证码识别时间为 4-5ms，正确率 100%。

识别步骤如下：

1. 灰度化
2. 二值化
3. 切割为单个数字
4. 和字库对比

导入需要用到库

import mathimport timefrom io import BytesIOimport numpy as npfrom PIL import Imageimport data

最后一行导入的是字库，后面会写到。

灰度化

从之前的例子可以看到图像有一些噪点，为了不让其干扰识别需要进行降噪处理，第一步是将图片灰度化。所谓灰度化是将 RGB 色彩空间中三个量合并成一个量 L，这样原本的彩色图像变成灰度图了。每个像素的取值也由 $256^{3}$（16777216）个减少到 256 个，能够减少后继的计算量。将上面的图片灰度化之后变成下面的样子。

处理代码：

# 灰度处理并创建二维矩阵img_matrix = np.array(Image.open(BytesIO(image_bytes)).convert("L"))

其中 Image.open(BytesIO(image_bytes)).convert("L") 是从 image_bytes 中创建图像并转为灰度图， image_bytes  可以是从网络加载或从本地文件读入的字节数据。然后根据灰度图创建一个 NumPy 矩阵方便后面的运算。

灰度化之后与原图好像没有区别是因为原图本身是黑白的，如果原图是彩色的话能够很明显地看出区别。

二值化

二值化是将图像的像素与某个阈值比较，若大于这个阈值则设置为灰度最大值（这里是 1，白色），小于某个值则设为灰度最小值（这里是 0，黑色）。这样上一步的灰度图就转化为二值图，便于接下来的图像分割。选择合适的阈值还可以去除图像噪点。

二值化后噪点已经完全消失，数字的边界更加锐利。

处理代码：

# 获取矩阵（图像）的长宽rows, cols = img_matrix.shapefor i in range(rows):    for j in range(cols):        # 与阈值比较        if img_matrix[i, j] <= 128:            # 设为灰度最小值            img_matrix[i, j] = 0        else:            # 设为灰度最大值            img_matrix[i, j] = 1

切割为单个数字

二值化后可以看到图像中有大量的空白，这对于识别会造成一些影响，并且对比多个验证码发现数字的垂直位置并非固定，也就是上下边距是浮动的。因此要将空白部分删掉只保留有图像的部分 。 先看实现：

# 每行最小值row_min = np.min(img_matrix, axis=1)# 找到第一个有图像的行row_start = np.argmin(row_min)# 找到最后一个有图像的行row_end = np.argmin(np.flip(row_min))# 只取有图像的行img_matrix = img_matrix[row_start:-row_end, :]

row_min 的值为

[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1]

其中 1 表示该行最小值为 1 ，在本例中表示这一行都是 1 ，即没有黑色像素。0 则表示这一行有 0 的存在，即存在黑色像素，也就是这一行有图像，需要保留。np.argmin() 在 row_min 中查找最小值第一次出现的位置，即为图像开始行。将 row_min 反转之后再次查找最小值下标就得到了结束下标，这个下标的是从右向左计数的。 得到 row_start 和 row_end 后对矩阵进行切片，row_end 要取负值表示表示从右开始计数。

接下来将数字切片成单个：

codes = [0] * 4for i in range(4):    # 切片    imag_matrix_spited = img_matrix[:, 19 * i:19 * (i + 1)]    col_min = np.min(imag_matrix_spited, axis=0)    col_start = np.argmin(col_min)    col_end = np.argmin(np.flip(col_min))    # 图像宽度    width = col_min.shape[0] - (col_start + col_end)    # 宽度扩宽到 9 像素    width_rest = 9 - width    # 左边界    col_start -= int(math.ceil(width_rest / 2.0))    # 右边界    col_end -= int(math.floor(width_rest / 2.0))    # 裁剪为 9 像素宽的图像    imag_matrix_spited = imag_matrix_spited[:, col_start:-col_end]

先粗略裁剪为每个数字 20 像素，然后再判断左边界和右边界，同之前一样的算法。但是这里不能直接使用得到的边界，每个数字的宽度不一样，直接切片会导致矩阵大小不一样，会影响之后的计算。因此要将将宽度统一为 9 像素，即为最宽的数字宽度。

和字库对比

res = [0] * 10# 展开成一维x = imag_matrix_spited.flatten()for j in range(10):    # 一次取字库中标准数据    y = data.array_map[j]    # 通过异或计算不同元素的数量    res[j] = np.sum(x ^ y)    # 取差异最小的下标codes[i] = str(np.argmin(res))

首先将原先的二维矩阵展开为一维，再与字库中的数据对比找到差异最小的那个既是最终结果，这样整个验证码就识别出来了。字库则需要将展开后的矩阵按照顺序整理一下得到。

下面是针对这种验证码的字库（0~9）：

import numpy as nparray_map = [0] * 10array_map[0] = np.array(    [1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1,     0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1,     1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1])array_map[1] = np.array(    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1,     1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1,     0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1])array_map[2] = np.array(    [1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1,     1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0,     1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1])array_map[3] = np.array(    [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,     1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,     1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1])array_map[4] = np.array(    [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1,     1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0,     0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1])array_map[5] = np.array(    [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,     0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,     1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1])array_map[6] = np.array(    [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,     0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1,     1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1])array_map[7] = np.array(    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1,     1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0,     1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1])array_map[8] = np.array(    [1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1,     1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1,     1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1])array_map[9] = np.array(    [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1,     0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1,     1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1])

至此验证码识别成功。

最后

完整的代码和一百个测试验证码可以在 Dreace/IVC 找到。

要求环境为 Python 3+，运行前请先安装 requirements.txt 中的依赖。

因此有了编写一个命令行工具的想法，由于最近在学习 TypeScript，就决定用它来写。

准备环境

在开始编写逻辑代码前需要准备一下开发环境。

首先初始化项目¹：

yarn init -y

本文将使用 yarn 作为包管理工具。

安装 TypeScript 支持：

yarn add global typescript ts-node-dev

ts-node-dev 可以直接启动 .ts 文件，如果使用 tsc && node "path/to/file.js" 自行编译并启动则不需要这个依赖。

这两个依赖需要全局安装，因为他们分别提供 tsc 和 ts-node-dev 命令。

安装 Node.js 类型声明文件：

yarn add --dev @types/node

以上是必备的开发依赖，除此还可以使用 ESLint 和 Prettier 来检查语法和规范格式。

以下配置内容均为可选，可以单独使用或组合使用。

使用 ESLint²

ESLint 可以静态分析代码，能够尽早发现编码中的错误。

首先安装需要的依赖：

yarn add --dev @typescript-eslint/parser @typescript-eslint/eslint-plugin

在根目录下创建 .eslintrc.js 文件并写入：

module.exports = {    parser: '@typescript-eslint/parser',    extends: ['plugin:@typescript-eslint/recommended'],    plugins: ['@typescript-eslint'],    env: {        node: true,    }}

更多的配置可以查看 Configuring ESLint。

使用 Prettier

Prettier 可以通过配置文件来格式化代码，非常适合团队内规范代码。

首先安装 Prettier：

yarn add --dev prettier

在根目录下创建 prettier.config.js 文件，并写入³：

module.exports = {  // 一行最多 100 字符  printWidth: 100,  // 使用 4 个空格缩进  tabWidth: 2,  // 不使用缩进符，而使用空格  useTabs: false,  // 行尾需要有分号  semi: true,  // 使用单引号  singleQuote: true,  // 对象的 key 仅在必要时用引号  quoteProps: 'as-needed',  // jsx 不使用单引号，而使用双引号  jsxSingleQuote: false,  // 末尾不需要逗号  trailingComma: 'all',  // 大括号内的首尾需要空格  bracketSpacing: true,  // jsx 标签的反尖括号需要换行  jsxBracketSameLine: false,  // 箭头函数，只有一个参数的时候，也需要括号  arrowParens: 'always',  // 每个文件格式化的范围是文件的全部内容  rangeStart: 0,  rangeEnd: Infinity,  // 不需要写文件开头的 @prettier  requirePragma: false,  // 不需要自动在文件开头插入 @prettier  insertPragma: false,  // 使用默认的折行标准  proseWrap: 'preserve',  // 根据显示样式决定 html 要不要折行  htmlWhitespaceSensitivity: 'css',  // 换行符使用 lf  endOfLine: 'lf',};

更多配置可查看 What is Prettier?。

在 WebStorm 中启用 ESLint 和 Prettier

启用 ESLint

找到 File | Settings | Languages & Frameworks | JavaScript | Code Quality Tools | ESLint 配置项，选择 Automatic ESLint configuration。

WebStorm 会自动查找 ESLint 路径并执行检查。

启用 Prettier

找到 File | Settings | Languages & Frameworks | JavaScript | Prettier 配置项，选择 Prettier 路径，可以勾选 Run on save for files，在保存时自动执行检查。

使用 EditorConfig

EditorConfig 可以通过配置文件来指定不同 IDE 或编辑器的代码格式化行为，在编码期间就能根据团队规范格式化代码。

WebStorm 已经内置实现 EditorConfig 支持，在根目录创建 .editorconfig 文件，并写入：

# http://editorconfig.orgroot = true[*]indent_style = spaceindent_size = 2end_of_line = lfcharset = utf-8trim_trailing_whitespace = trueinsert_final_newline = true[*.md]trim_trailing_whitespace = false[*.ts]ij_typescript_spaces_within_imports = true[Makefile]indent_style = tab

以上配置效果和 Prettier 相同，更多配置可查看 EditorConfig。

配置 TypeScript

在根目录下创建 tsconfig.json 文件，并写入：

{  "compilerOptions": {    "target": "es5",    "module": "commonjs",    "outDir": "./dist",    "strict": true,    "esModuleInterop": true,    "skipLibCheck": true,    "forceConsistentCasingInFileNames": true  }}

outDir 指定 tsc 命令编译结果输出路径。

编写代码

使用 Commander.js

要编写的是命令行工具，自然要解析命令行参数，出于不重复造轮子的目的选择 Commander.js 来解析命令行参数。

安装 Commander.js：

yarn add commander

Commander.js 使用很简单，一个例子：

import { program } from 'commander';program  .version('1.0.3')  .name('upload-to-qiniu')  .requiredOption('-a, --access-key [ak]', 'access key')  .requiredOption('-s, --secret-key [sk]', 'secret key')  .option('-d, --upload-dir <dir>', '要上传的目录', './')  .requiredOption('-b, --bucket [bucket]', '对象存储空间名')  .option('-e, --exclude-prefix <prefixs...>', '忽略的文件名前缀，可以设置多个')  .parse();

import { program } from 'commander'; 导入全局对象，version 指定版本号，name 指定 -h 帮助信息的名称。

option 定义选项，一共三个参数：

• 第一个参数指定选项名称，指定选项的短名称和长名称，使用逗号、空格或 | 分割，必选
• 第二个参数为选项描述，可选
• 第三个参数为默认值，可选

option 定义的选项是非必选的，如需要定义必选选项可以使用 requiredOption，如果使用命令行时没有指定必选选项会有报错。

有两种最常用的选项，一类是 boolean 型选项，选项无需配置参数，另一类选项则可以设置参数（使用尖括号声明）。如果在命令行中不指定具体的选项及参数，则会被定义为 undefined。

代码中将长名称转化成小驼峰来获取用户指定的参数值，例如：

const mac = new qiniu.auth.digest.Mac(program.accessKey, program.secretKey);

program.accessKey 获取的是 -a 参数指定的值。

定义好选项后可以使用 -h 查看帮助信息：

> upload-to-qiniu -hUsage: upload-to-qiniu [options]Options:  -V, --version                      output the version number  -a, --access-key [ak]              access key  -s, --secret-key [sk]              secret key  -d, --upload-dir <dir>             要上传的目录 (default: "./")  -b, --bucket [bucket]              对象存储空间名  -e, --exclude-prefix <prefixs...>  忽略的文件名前缀，可以设置多个  -h, --help                         display help for command

编写逻辑代码

做了这么多准备终于可以正式开始编写代码了，在根目录创建 src 目录，然后在其中编写代码即可。

每个项目具体细节有很大差异，这里就不写具体细节了，不过有一点要注意，入口文件首行一定要加上 #!/usr/bin/env node 来指定解释器，否则会使用系统解释器，在 Windows 下不能正常使用。

本文涉及的具体代码可以在 Dreace/upload-to-qiniu 找到。

发布 npm 包

填写包信息

{  "name": "upload-to-qiniu",  "version": "1.0.4",  "license": "GPL-3.0",  "main": "dist/upload.js",  "bin": {    "upload-to-qiniu": "dist/upload.js"  },  "scripts": {    "lint": "eslint src --fix --ext .ts"  },  "files": [    "dist/**/*.js"  ],  "dependencies": {    "commander": "^6.0.0",    "qiniu": "^7.3.2"  },  "devDependencies": {    "@types/node": "^14.0.24",    "@typescript-eslint/eslint-plugin": "^3.7.0",    "@typescript-eslint/parser": "^3.7.0",    "eslint": "^7.5.0",    "eslint-plugin-prettier": "^3.1.4",    "prettier": "^2.0.5"  }}

name 指定包名，在 npm 中全局唯一，version 指定当前版本，license 指定许可证。

bin 指定命令行和要执行的 .js 脚本对应关系，一个包可以提供多个命令行工具。

files 指定打包时要包含的文件，除此 README.md 和 LICENSE 也会被打包。

本地测试

编写完代码后需要安装为全局包进行测试。

npm i -g .

将当前目录下的文件安装为全局包，安装后可以通过 bin 中指定的名称来使用。

发布

首先 注册一个 npm 账号。然后使用 npm login 登录到 npm。

登录后使用 npm publish 发布包，输出信息大致如下：

> npm publishnpm noticenpm notice package: upload-to-qiniu@1.0.5npm notice === Tarball Contents ===npm notice 35.8kB LICENSEnpm notice 6.0kB  dist/upload.jsnpm notice 6.6kB  dist/utils.jsnpm notice 931B   package.jsonnpm notice 1.0kB  README.mdnpm notice === Tarball Details ===npm notice name:          upload-to-qiniunpm notice version:       1.0.5npm notice package size:  16.4 kBnpm notice unpacked size: 50.4 kBnpm notice shasum:        73b867074f514761f6c6c9a442c38e83bc18aa9anpm notice integrity:     sha512-qHdhXhV/JjzMv[...]x6wD4OY1ysFnQ==npm notice total files:   5npm notice+ upload-to-qiniu@1.0.5

发布成功后可以在 https://www.npmjs.com/ 看到包信息。

这里的 TopK 不单指最大的 $k$ 个元素，也可以是最小的 $k$ 个元素，具体的例题可以看 剑指 Offer 40. 最小的k个数。本文的代码均为可以在力扣提交的题解，故不包含头文件和 main 函数。

堆

看到这种题，最先想到的可能是直接使用已有的排序函数，但是其时间复杂度为 $O(n \log n)$，大量的排序工作是多余。

一个优化的想法是，建立一个大小为 $k$ 的堆（针对求最小的 $k$ 个元素使用最大堆），只需要一次遍历将遍历到的元素和堆顶元素比较，若比堆顶小，则替换堆顶，然后进行堆调整。遍历完成后，堆中就是要求的最小的 $k$ 个元素（无序的）。

通过堆优化后时间复杂度为 $O(n \log k)$。

class Solution {public:    vector<int> getLeastNumbers(const vector<int> &arr, int k) {        vector<int> ans(k, 0);        if (k == 0) {            return ans;        }        // 建堆        for (int i = 0; i < k; ++i) {            ans[i] = arr[i];        }        for (int i = k / 2 - 1; i >= 0; --i) {            adjust(ans, i);        }        int n = arr.size();        for (int i = k; i < n; ++i) {            // 比堆中最大的要小            if (arr[i] < ans[0]) {                // 替换                ans[0] = arr[i];                // 调整后堆顶是最大的元素                adjust(ans, 0u);            }        }        return ans;    }    void adjust(vector<int> &heap, uint32_t index) {        uint32_t t = index;        // 左孩子        if ((index << 1u) + 1 < heap.size() && heap[(index << 1u) + 1] > heap[t]) {            t = (index << 1u) + 1;        }        // 右孩子        if ((index << 1u) + 2 < heap.size() && heap[(index << 1u) + 2] > heap[t]) {            t = (index << 1u) + 2;        }        // 孩子节点比父节点大        if (t != index) {            std::swap(heap[index], heap[t]);            // 递归调整            adjust(heap, t);        }    }};

快排

这里不是真的快排，而是借助快排的思想，将元素划分成比中间元素后大或小的两部分后，再对其中的一个部分再次划分。快排的思想是分治，这里解决 TopK 的思想是减治，因为划分后不符合条件的部分直接舍弃掉。

该方法的期望时间复杂度 $O(n)$，最坏时间复杂度 $O(n^2)$，因为可能每次选取的中间值都是最大值，为了解决这个问题，可以随机选择中间值（被注释掉的三行代码）。

class Solution {public:    std::vector<int> getLeastNumbers(std::vector<int> &arr, int k) {        uint32_t left = 0, right = arr.size() - 1;//        srand(time(nullptr));        while (left < right) {//            int t = rand() % (right - left + 1) + left;//            std::swap(arr[left], arr[t]);            int pivot = arr[left];            int i = left, j = right;            // 完成后以 i 为分界，左半部分比 arr[i] 小，右半部分比 arr[i] 大            while (i <= j) {                // 寻找左半部分比 pivot 大的元素                while (i <= j && arr[i] < pivot) {                    ++i;                }                // 寻找右半部分比 pivot 小的元素                while (i <= j && arr[j] > pivot) {                    --j;                }                if (i <= j) {                    std::swap(arr[i], arr[j]);                    ++i;                    --j;                }            }            if (i >= k) {                // 大于等于 k 个                right = i - 1;            } else {                // 小于 k 个                left = i;            }        }        return std::vector<int>(arr.begin(), arr.begin() + k);    }};

两种算法的选择

在数据量比较小时，两个算法没有太大的区别。

但是当数据量达到十亿级别（腾讯面试被问过这个问题）使用快排需要将所有数据读入内存（当然也可以优化，但是会更复杂）。

而使用堆只需要维护一个大小为 $k$ 的堆（实际来说是数组），由于只需要遍历一次数据，数据读入一次就行了，对磁盘的操作可以很少。相比 CPU 的速度，磁盘 I/O 的时间有数量级上的差异。

因此在大数据量上应该选择堆。

子密钥生成

初始化时由外部提供密钥，若密钥长度不足 8 字节（64 位）可以在末尾使用 0 补足长度。

if isinstance(key, str):    key = key.encode()if len(key) > 8:    key = key[8:]elif len(key) < 8:    key += b"".join(b"\x00" for _ in range(8 - len(key)))key_bit_list = self._bytes_to_bit_list(key)

提供的密钥可以是字符串或者是字节，若是字符串则需要编码得到字节，方便后续的处理，最后将长度裁剪或补足到 8 字节后转换成比特列表。字节到比特列表的函数如下：

def _bytes_to_bit_list(input_bytes: bytes) -> List[int]:    bit_list = [0] * 8 * len(input_bytes)    index = 0    for char_ascii in input_bytes:        loc = 7        while loc >= 0:            bit_list[index] = 0 if char_ascii & (1 << loc) == 0 else 1            loc -= 1            index += 1    return bit_list

字节使用 for 得到的元素是数字，这里命名为 char_ascii，从高位到低位依次取出 char_ascii 的每一位填充到比特列表中。

得到密钥的比特列表后需要使用 PC-1 生成两个 28 位半密钥（总共只使用了 56 位密钥，剩下的 8 位可以作为奇偶校验）。

left_half_key_block = self._transform(key_bit_list, pc1_left_table)right_half_key_block = self._transform(key_bit_list, pc1_right_table)

这里使用了一个置换工具函数，这个函数在 DES 算法中应该是最常用的了，通过查表进行变换。

def _transform(raw_list: list, transform_table: List[int]) -> list:    return list(map(lambda index: raw_list[index], transform_table))

在得到两个半密钥后下一步是生成 16 个子密钥，首先将两个半密钥循环左移（左移位数查表得）合并，再通过 PC-2 得到 48 位的子密钥。

sub_key_list = []for round_index in range(16):    left_half_key_block = self._circle_left_shift(left_half_key_block, key_left_shift_bits[round_index])    right_half_key_block = self._circle_left_shift(right_half_key_block, key_left_shift_bits[round_index])    sub_key_list.append(self._transform(left_half_key_block + right_half_key_block, pc2_table))self._sub_key_list = sub_key_list

_circle_left_shift 实现如下：

def _circle_left_shift(input_list: list, bits: int) -> list:    return input_list[bits:] + input_list[:bits]

将输入列表切片再合并实现循环左移效果。

分块加密

一次 DES 加密针对 64 位的明文，首先将明文进行 IP 后再分为两部分。

plain_block = self._transform(plain_block, ip_table)left_half_block = plain_block[:32]right_half_block = plain_block[32:]

将左半部分与右半部分经过 F 函数后的结果异或得到新的左半部分，原来的左半部分作为新的右半部分。如此进行十六次。

for round_index in range(16):    left_half_block, right_half_block = right_half_block, \                                        self._bit_list_xor(                                            left_half_block,                                            self._transform(                                                self._s_box_transform(                                                    self._bit_list_xor(                                                        self._transform(right_half_block,                                                                        extend_table),                                                        self._sub_key_list[round_index]                                                    )                                                ), p_table                                            )                                        )return self._transform(right_half_block + left_half_block, fp_table)

F 函数的过程：

1. 通过扩张置换将 32 位的半块扩展到 48 位
2. 与 48 位的子密钥进行异或
3. 每 6 位进行 S 盒变换，得到 4 位的输出，共 32 位
4. 最后再进行 P 置换

这里涉及到一个比特列表的异或操作，实现如下：

def _bit_list_xor(left: list, right: list) -> List[str]:    return list(map(lambda x, y: x ^ y, left, right))

和 S 盒变换工具函数：

def _s_box_transform(input_list: list) -> list:    transformed = [0 for _ in range(32)]    transformed_index = 0    r = 0    while r < 48:        m = (input_list[r] << 1) + input_list[r + 5]        n = (input_list[r + 1] << 3) + (input_list[r + 2] << 2) + (input_list[r + 3] << 1) + (input_list[r + 4])        s_value = s_box_tables[r // 6][(m << 4) + n]        transformed[transformed_index] = (s_value & 8) >> 3        transformed[transformed_index + 1] = (s_value & 4) >> 2        transformed[transformed_index + 2] = (s_value & 2) >> 1        transformed[transformed_index + 3] = s_value & 1        r += 6        transformed_index += 4    return transformed

每次取出 6 六位，最高位和最低位计算 m 为行号，中间四位计算 n 为列号。为了方便处理这里将二维的 S 盒表格展开为一维数组，根据 m 和 n 取出 S 盒中元素。

最后将元素转换成比特填充到 transformed 中。

明文加密

加密函数接受字符串和字节作为参数，若明文长度不是 8 的整数倍字节则需要补足。

if isinstance(plain_text, str):    plain_text = plain_text.encode()plain_text_len = len(plain_text)if plain_text_len % 8:    plain_text += b"".join(b"\x00" for _ in range(8 - plain_text_len % 8))

将明文分成 8 字节长的块后分别进行加密，全部块加密完成后得到若干个 64 位长的比特列表，将这些列表合并，再转换成字节。

encrypted_blocks = []for block in map(lambda s: plain_text[s:s + 8], range(0, plain_text_len, 8)):    encrypted_blocks.append(self._encrypt_block(self._bytes_to_bit_list(block)))encrypted_bit_list = list(chain(*encrypted_blocks))return self._bit_list_to_bytes(encrypted_bit_list)

比特列表到字节函数如下：

def _bit_list_to_bytes(bit_list: List[int]) -> bytes:    char_ascii = 0    byte_list = []    for index, bit in enumerate(bit_list):        char_ascii += bit << (7 - index % 8)        if index % 8 == 7:            byte_list.append(char_ascii)            char_ascii = 0    return bytes(byte_list)

解密

解密过程和加密过程完全相同，只不过子密钥使用顺序相反。

def decrypt(self, cipher_text: bytes) -> str:    self._sub_key_list.reverse()    plain_text = self.encrypt(cipher_text)    self._sub_key_list.reverse()    return plain_text.decode().rstrip('\0')

最近在学网络编程，需要在 Linux 下编译 C 源码，可我日常使用 Windows，在虚拟机里操作又不是很方便。于是 Clion + WSL 成了几乎完美的解决方案，在 Windows 下编码，Linux 环境下编译运行。

但是由于一个意外需要卸载已安装的 WSL（Ubuntu 18.04 LTS），凑巧巨硬最近发布了 Ubuntu 20.04 LTS 的 WSL，于是尝试了一下。尴尬的是最新版本的 Clion 还不能识别 20.04，但问题不大。

修改配置文件

原本 Clion 应能识别已安装的 WSL，但 20.04 的设置还未添加，故不能识别。解决办法很简答，手动添加即可。打开 C:\Users\<用户名>\AppData\Roaming\JetBrains\CLion<版本号>\options\wsl.distributions.xml，在 set 下添加¹：

<descriptor>    <id>UBUNTU2004</id>    <microsoft-id>Ubuntu-20.04</microsoft-id>    <executable-path>ubuntu2004.exe</executable-path>    <presentable-name>Ubuntu 20.04</presentable-name></descriptor>

保存，重启 Clion 即可。

再解决一个问题

在升级 20.04 的包时遇到 sleep: cannot read realtime clock: Invalid argument 错误，应该是一个 WSL 的 bug，据说已经在 Windows 2004 修复，但是 2004 要还没正式发布。目前的解决办法是降级导致问题的 libc6 包²：

wget "https://launchpad.net/~rafaeldtinoco/+archive/ubuntu/lp1871129/+build/19152555/+files/libc6_2.31-0ubuntu8+lp1871129~1_amd64.deb"sudo dpkg -i libc6_2.31-0ubuntu8+lp1871129~1_amd64.deb

在升级前将其版本冻结：

apt-mark hold libc6

这样该问题可以解决。但是降级会导致 gcc、cmake 等一大票编译工具无法正常安装。

最后

还是回到了 Ubuntu 18.04 LTS。

这便是噩梦的开始。

罪魁祸首

收到报警后看了一下系统各项指标，不仅内存占用高，CPU、磁盘使用率都是满负荷。

在凌晨一点半左右内存暴涨，紧接着 CPU 使用率也达到 100%。这个场景似曾相识，因为之前使用过 InfluxDB，也遇到过内存暴涨，结合前几天又用上了 InfluxDB，基本可以断定是 InfluxDB 的锅。

重启服务器后一切都恢复正常，但是 InfluxDB 可能随时又出现状况，只能一直盯着各种指标，盯数据的时候发现 InfluxDB 的内存占用肉眼可见地增长，可以说很恐怖了。

尝试解决

好在 InfluxDB 是通过 Docker 部署的，可以很方便地限制内存使用，尝试通过 docker-compose.yml 配置：

deploy:    resources:    limits:        memory: 500Mrestart: always

将 InfluxDB 可以使用的内存限制在 500MiB，超过这个数值就会被 kill，然后又自动重启。虽然这样可以避免 InfluxDB 将系统拖垮，但频繁 OOM 又重启终究不是什么好办法。

更改索引方式

查了一些资料后得知 InfluxDB 默认的索引是在内存上维护的，不断地数据增长会使用越来越多的内存，并有一个参数 index-version 可以设置索引方式¹。如果是直接在主机上部署的可以修改配置文件，Docker 部署则需要通过环境变量设置：

environment:    INFLUXDB_DATA_INDEX_VERSION: tsi1

将索引数据存储在磁盘上，可以通过日志或者查看分片的目录结构验证修改是否生效，若索引方式为 tsi1，在分片目录下会有一个名为 index 的目录，inmem 索引则没有。

具体位置是 /var/lib/influxdb/data/<数据库>/<保留策略>/<分片>。

[root@izuf6czs1dw6siz3zokdiez 1_day]# ls1  10  11  12  13  14  15  16  18  19  20  21  3  4  5  6  7  8  9[root@izuf6czs1dw6siz3zokdiez 1_day]# cd 15[root@izuf6czs1dw6siz3zokdiez 15]# ls000000001-000000001.tsm  fields.idx  index

禁用状态监控

默认情况下 InfluxDB 会维护一个 _internal 库，来监控系统状态，但是会产生不必要的数据，官方不推荐在生产环境下使用 _internal 库²。

InfluxData does not recommend using the _internal database in a production cluster. It creates unnecessary overhead, particularly for busy clusters, that can overload an already loaded cluster. Metrics stored in the _internal database primarily measure workload performance and should only be tested in non-production environments.

添加环境变量：

environment:    INFLUXDB_DATA_INDEX_VERSION: tsi1    INFLUXDB_MONITOR_STORE_ENABLED: "false"

效果验证

更改索引方式后内存使用依然在缓慢增长，但是保留策略设置的是一天，需要等到更改生效一天后才能看出真实的效果（待更新）。

超过保留策略（24 小时）的时间后（27 小时）内存增长停止，目前稳定在 235.3MiB，大致符合预期。

定位问题

随后用 ping 测试发现需要好几秒钟才能解析出 IP，而用 nslookup 测试解析速度又是正常的。这下子基本知道问题了，又是系统 DNS 服务的锅，为什么是又呢？因为之前系统 DNS 服务把一些域名解析到了教育网，导致一些网站 CSS 加载失败，加了 hosts 之后才勉强正常。前一次的问题影响不是很大，可这次就不一样了，所有的网站打开都要等几秒钟，这可忍不了。

这里说一下为什么通过 ping 和 nslookup 就能断定系统 DNS 服务有问题呢，因为 ping 在解析域名时用的时系统 DNS 服务，而 nslookup 是直接通过 Winsock 建立连接查询的¹。

用 Wireshark 抓包发现使用 ping 时 DNS 查询报文也是很快响应了的，但是 ping 客户端似乎没有收到。到这里就陷入死胡同了，我对 Windows 内部的细节不了解，不能再往下定位问题。

解决问题

由于上午事情比较多就暂时把这个问题放下了。

到了下午突然想起会不会又是 VMware 虚拟网卡的问题，这里又是一个又😫，因为之前遇到过虚拟网卡导致移动热点 IP 冲突问题。尝试禁用以 VMware Virtual Ethernet Adapter 开头的网卡，再次测试，ping 和打开网页都已正常。

后记

这次虽然解决了问题，但是具体原因还不清楚，日后搞清楚问题再更新这篇文章

分析

使用搜索引擎可以搜索使用空格分割的多个关键词，例如 Python MySQL 回滚 能够搜索到同时包含这个三个关键词的结果，并且是顺序无关的。要是用 LIKE 来进行模糊匹配就要拼接一个又臭又长的 SQL，这个可能并不是我们想要的，除了 LIKE 还有什么好的办法呢。正则表达式！用正则表达式可以很容易实现这个需求。

既然有了办法开始写代码，首先考虑如何根据搜索输入 Python MySQL 回滚 匹配下面的字符串：

Python 中回滚 MySQL 操作。

这个字符串中关键词输入顺序和输入的关键词顺序不同，但是顺序对结果不会产生影响。为了同时匹配多个关键词可以先拆分为多个独立的关键词分开匹配，若前一个成功则继续匹配知道所有关键词都成功匹配。

我们可以使用正则中的零宽先行断言（(?=exp)）¹，它可以匹配以 exp 为后缀的字符串，之后的匹配将从 exp 前一个位置继续。

如果写成 (?=.*exp)，它将从后向前匹配以 exp 为后缀的字符串，若匹配式中包含多个零宽先行断言每一次匹配都从最后开始。

这样关键问题已解决，对于 Python MySQL 回滚 完整的表达式为：

(?=.*Python)(?=.*MySQL)(?=.*回滚)

上面这个正则表达式可以判断一个字符串是否包含这三个关键词，若要提取成功匹配的字符串可以写成：

(?=.*Python)(?=.*MySQL)(?=.*回滚)^.*$

代码实现

下面写一个用正则在 MySQL 中进行多关键词查找的实例。

假设有一张表，结构如下：

CREATE TABLE `课程-2020-1`  (  `教学班编号` varchar(32) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,  `学院` varchar(50) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,  `课程名` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,  `教师` varchar(25) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,  `周次` varchar(20) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,  `星期` int(11) NOT NULL,  `开始节次` int(11) NULL DEFAULT NULL,  `时长节次` int(11) NULL DEFAULT NULL,  `教学楼` varchar(50) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,  `教室` varchar(50) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL,  PRIMARY KEY (`教学班编号`, `课程名`, `星期`) USING BTREE) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = Dynamic;

我们希望能够同时匹配 学院、 课程名、教师三个字段中的值，例如输入 工程 数据，能够同时查找出「大数据学院」的「物联网工程技术基础」 和「信息与通信工程学院」的「大数据与云计算」课程，对应的 SQL 如下：

SELECT * FROM `课程-2020-1` WHERE CONCAT_WS('', `学院`, `课程名`, `教师`) REGEXP '(?=.*工程)(?=.*数据)'

其中 CONCAT_WS('', `学院`, `课程名`, `教师`) 将每行中 学院、 课程名、教师 字段的值连接形成一个字符串，第一个参数作为剩余参数间的分隔符²，CONCAT_WS 的作用类似 Python 和 JavaScript 中的 join。这里不使用 CONCAT 是因为 教师 字段可能为空值，进而导致 CONCAT 的返回结果也为空， 而 CONCAT_WS 会忽略空值。

搜索结果为：

完美实现！下面是输入关键词字符串生成对应 SQL 的 Python 代码：

keywords_map = "".join(map(lambda k: "(?=.*%s)" % k, keywords.split(" ")))sql = "SELECT * FROM `课程-2020-1` WHERE CONCAT_WS('', `学院`, `课程名`, `教师`) REGEXP '%s^.*$'" % keywords_map

问题分析

从报错的字面意思就能看出来系统的 Socket 资源耗尽无法建立新的链接。经查询得知 Windows 10 中默认允许用户使用的端口数是 1500，并且端口关闭后需要经过 60 秒才能重新被使用¹。查看数据库已写入的数据在 1600 条左右，和 1500 这个限制比较接近，由此问题被大致定位。

解决问题

既然已经知道问题的根本原因，解决方法也呼之欲出：修改限制。在“注册表编辑器中”找到 HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters。，修改 MaxUserPort 的值为 65534（十进制）或 fffe（十六进制）。同时也可以修改端口关闭后可重新使用的等待时间，在相同位置新建一个 DWORD 类型名称为 TcpTimedWaitDelay 的项目，其值表示等待多少秒后端口可以被重新使用。

完成之后重启。

再次运行，问题已经解决。