【使用 Python 实现算法】目录

• 01 语言特性
• 02 原生类型与内置函数
• 03 标准库（数字与数学模块）
• 04 标准库（数据类型模块）
• 05 标准库（函数式编程模块）

算法实现中经常需要构造和处理一些特殊的数据结构，Python 标准库中有一些模块可以帮到我们。

collections 实用容器

collections模块实现了一些特定目标的容器，以提供 Python 标准内建容器 dict , list , set , 和 tuple 的替代选择。

deque

在 Python 中从list对象的头部删除元素，时间复杂度是 O(n)。deque类型是一个双向队列，类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)。

1
2
3
4
5
6
7
8
9

q = deque([1, 2, 3, 4])

q.append(5)
q.appendleft(0)
assert q == deque([0, 1, 2, 3, 4, 5])

assert q.pop() == 5
assert q.popleft() == 0
assert len(q) == 4

【使用 Python 实现算法】目录

• 01 语言特性
• 02 原生类型与内置函数
• 03 标准库（数字与数学模块）
• 04 标准库（数据类型模块）
• 05 标准库（函数式编程模块）

本期向大家介绍一些 Python 中用于处理数字和数学方面的标准库。

math 数学模块

作为 LeetCode Python 环境中默认导入的标准库模块之一，math模块提供了很多非常有用的数字和数学方面的函数。

数论与表示函数（number theoretic and representation functions）

gcd与lcm，用于计算多个整数的最大公约数与最小公倍数。

1
2
3
4
5

assert math.gcd(12, 18) == 6
assert math.gcd(3, 5, 7) == 1

assert math.lcm(12, 18) == 36
assert math.lcm(3, 5, 7) == 105

ceil：向上取整，floor：向下取整，trunc：移除小数部分。
对于正数来说，trunc与floor是等价的。
对于负数来说，trunc与ceil是等价的。

1
2
3
4
5
6
7

assert math.ceil(1.2) == 2
assert math.floor(1.2) == 1
assert math.trunc(1.2) == 1

assert math.ceil(-3.5) == -3
assert math.floor(-3.5) == -4
assert math.trunc(-3.5) == -3

【使用 Python 实现算法】目录

• 01 语言特性
• 02 原生类型与内置函数
• 03 标准库（数字与数学模块）
• 04 标准库（数据类型模块）
• 05 标准库（函数式编程模块）

本期话题是 Python 的原生类型和内置函数在算法实现中的一些技巧，首先从最常见的 Python 原生类型开始。

int

int类型有两个内置的方法bit_count与bit_length，分别用来获取整数二进制表达的1的个数和二进制位数，在很多场景下都很实用。

1
2
3

n = 9
assert n.bit_count() == 2
assert n.bit_length() == 4

float

float的as_integer_ratio方法可以获得浮点数的最简分数表达。

1
2

f = 6.125
assert f.as_integer_ratio() == (49, 8)

利用f-string可以轻松获得浮点数的指定小数位数的字符串表达。

1

assert f"{1/3:.4f}" == "0.3333"

【使用 Python 实现算法】目录

• 01 语言特性
• 02 原生类型与内置函数
• 03 标准库（数字与数学模块）
• 04 标准库（数据类型模块）
• 05 标准库（函数式编程模块）

最近加入了公司同事组织的刷题群，会定期参加 LeetCode 等平台的算法比赛。

作为一个资深 Pythonist，我一向是使用 Python 来实现各种算法题目的。Python 本身也提供了一些不错的语言特性、内置函数和标准库来更高效简洁的编写各类算法的代码实现。

本系列博客是我根据个人使用 Python 工作和刷题的经验总结的一些使用 Python 实现各类算法的一些技巧。

作为系列博客的第一篇文章，本期的主题是 Python 的语言特性。

解构赋值

交换两个变量的值是一个很常见的场景，在 C 和 C++语言中，我们需要使用一个临时变量。代码会比较冗长，并且会有微小的性能开销。

1
2
3

int tmp = x;
int x = y;
int y = x;

利用 Python 的解构赋值特性，我们可以使用一个赋值语句交换两个变量的值。

1

x, y = y, x

配置管理在现代应用开发和部署中至关重要，在十二要素应用（12 Factor App）中，配置管理也是第三个重要因素。

使用Pydantic库，我们可以方便灵活地在 Python 应用中管理配置。

使用 Pydantic

配置管理是Pydantic官方文档中列出的一个重要应用领域。

如果你创建了一个继承自 BaseSettings 的模型，模型初始化器将试图通过从环境中读取来确定任何没有作为关键字参数传递的字段的值。(如果匹配的环境变量没有被设置，默认值仍将被使用）。

简化了一下操作：

1. 创建一个明确定义的、有类型提示的应用程序配置类。
2. 自动从环境变量中读取对配置的修改。
3. 在需要时手动覆盖初始化器中的特定设置（例如在单元测试中）。

C 和 C++中的函数重载

我们在学习 C 和 C++的时候，会接触到一个概念叫做函数重载。简单来说函数重载指的是多个函数具有相同的名称，但是参数不同（包括参数类型和参数数量）。编译器在遇到重载函数的调用时，会在同名函数的不同重载实现中选择参数匹配的哪一个来调用。

这里举一个简单的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>

void desc(int n){
    std::cout << n << " is an integer" << std::endl;
}

void desc(double x){
    std::cout << x <<  " is a floating number" << std::endl;
}

int main(){
    desc(1);
    desc(2.0);
    return 0;
}

之前刷 LeetCode 题目的时候，偶尔会需要反转二维列表，这里总结了几种 Python 实现。

循环

简单的二维循环，将原始二维列表的每一行的第 N 个元素，放到新的二维列表的第 N 行中。

1
2
3
4
5
6
7
8

def invert_matrix(matrix: list[list[int]]) -> list[list[int]]:
    new_matrix = []
    for i in range(len(matrix[0])):
        new_row = []
        for row in matrix:
            new_row.append(row[i])
        new_matrix.append(new_row)
    return new_matrix

列表推导式

本质上和循环算法是相同的，使用列表推导式语法来实现。

1
2

def invert_matrix(matrix: list[list[int]]) -> list[list[int]]:
    return [[row[i] for row in matrix] for i in range(len(matrix[0]))]

最近在深入学习 Rust 语言，本着学以致用的原则，使用 Rust 编写了一个生成二维码的 Web 服务。

使用的库

• axum，一个基于 tokio 的 web 框架
• qrcode, 用于生成二维码

核心逻辑

生成二维码

直接调用qrcode库相关接口，返回生成的 PNG 文件的二进制内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fn gen_qr_code(content: &str) -> Vec<u8> {
    tracing::info!("Generating QR code for {}", content);

    let image = QrCode::new(content)
        .unwrap()
        .render::<Luma<u8>>()
        .min_dimensions(512, 512)
        .build();

    let mut buffer = Vec::new();
    PngEncoder::new(buffer.by_ref())
        .encode(&image, image.width(), image.height(), image::ColorType::L8)
        .unwrap();

    buffer
}

最近接到了一个新的需求。需求本身是一个简单的运营活动，不过这个运营活动并不是长期存在的，需要通过后台设置生效时间。

抽象一下的话就是需要通过开关来控制一个功能是否生效，也就是特性开关（Feature Flags）模式。

Martin Fowler 先生写过一篇特性开关模式的文章，感兴趣的读者可以深入阅读。

RAII 概念与在 Python 中的应用

RAII(Resource Acquisition Is Initialization)，即资源获取即初始化，是一种设计模式，用于解决资源的获取与初始化的问题，最早在 C++中提出与推广。
在这篇文章我来简单地介绍一下 RAII 的概念，以及在 Python 中的应用。

RAII 的概念

在计算机与程序的世界中，有一些资源，比如文件、网络连接、数据库连接、线程、进程等，这些资源在使用的时候需要获取，在使用完成后需要释放。如果不及时释放，会导致资源泄露，造成资源的浪费，程序出错甚至系统崩溃。

一个简单的示例就是文件的读写。

1
2
3
4

f = open('test.json', 'r')
raw = f.read()
data = json.loads(raw)
f.close()

这段代码看起来没有什么问题，但是当test.json文件的内容不是合法的 JSON 格式时，第四行代码反序列化数据就会抛出异常，导致第五行代码无法执行，文件没有被关闭。

这个例子告诉我们在处理一些资源时，需要注意在操作过程中是否会发生一些意外情况，例如抛出异常，并且在意外情况发生后，也需要关闭资源。

在 Python2.5 之前的版本中，我们用try-finally来保证程序最终会关闭资源。

1
2
3
4
5
6
7
8

try:
    f = open('test.json', 'r')
    raw = f.read()
    data = json.loads(raw)
except JSONDecodeError:
    ...
finally:
    f.close()

在简单的文件读取操作中，使用try语句多少有点大材小用。为了更好地处理类似的资源管理问题，Python2.5 引入了with语句，做到无论语句块中的代码执行是否抛出异常，都可以在退出with语句块时执行清零代码。

事实上在 Python 中进行文件读写的标准方式就是使用with open语句。

1
2
3

with open('test.json', 'r') as f:
    raw = f.read()
    data = json.loads(raw)