那时难决

【使用 Python 实现算法】目录

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

Python 标准库中的functools和itertools模块，提供了一些函数式编程的工具函数。

functools 高阶函数

cache 与 lru_cache

用户缓存函数值的装饰器，可以缓存函数的调用结果。其中lru_cache函数可以设置一个缓存的最大容量，使用 LRU 算法淘汰长期不用的缓存。cache函数容量没有限制，相当于lru_cache(maxsize=None)。

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

@lru_cache(maxsize=3)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

assert [fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

@cache
def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

assert [factorial(n) for n in range(10)] == [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

partial 固定函数的一部分参数

partial() 会被“冻结了”一部分函数参数和/或关键字的部分函数应用所使用，从而得到一个具有简化签名的新对象。 例如，partial() 可用来创建一个行为类似于 int() 函数的可调用对象，其中 base 参数默认为二：

1
2
3
4

from functools import partial
basetwo = partial(int, base=2)
basetwo.__doc__ = 'Convert base 2 string to an int.'
assert basetwo('10010') == 18

reduce

Python2 中的reduce函数是一个内置函数，在 Python3 中被移入了functools模块中。
原因是reduce函数的效率没有寻常的 for 循环高，而往往使用了reduce函数的代码也不是特别容易理解（对比map和filter）。

1

assert reduce(lambda x, y: x + y, [1, 2, 3, 4, 5]) == 15

itertools 实用的迭代器

itertools模块是 Python 参考 APL，Haskell，SML 等编程语言的启发，实现的个快速、高效利用内存的核心工具集。
在算法实现中利用好itertools模块，可以有效提高代码编写速度、可维护性和算法的效率。

islice

首先介绍一下islice函数，可用于迭代器切片。

1

assert list(islice('ABCDEFG', 3)) == ['A', 'B', 'C']

无穷迭代器

count

count函数可以生成一个无穷的迭代器，每次调用返回一个整数，从 0 开始，每次增 1。
可以指定初始值，步长和生成数量。
count函数很适合替代while True:n +=1的循环。

1
2
3
4
5
6
7
8

def gen_primes():
    primes = []
    for n in count(2):
        if not any(n % p == 0 for p in primes):
            primes.append(n)
            yield n

assert list(islice(gen_primes(), 10)) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

cycle

cycle函数可以不断地迭代一个序列，直到迭代完成，然后重新开始迭代。

1

assert list(islice(cycle("ABC"), 6)) == ["A", "B", "C", "A", "B", "C"]

repeat

repeat函数会不断地重复生成一个元素。

1

assert list(map(pow, range(6), repeat(3))) == [0, 1, 8, 27, 64, 125]

有限数量的迭代器

accumulate

accumulate可以简单地理解为一个累加器。在很多需要计算列表的前缀和的算法中很有用。

1

assert list(islice(accumulate(count()), 5)) == [0, 1, 3, 6, 10]

chain

chain函数可以理解为合并多个序列的迭代器。

1

st(chain("ABC", "DEF")) == ["A", "B", "C", "D", "E", "F"]

dropwhile

dropwhile可以删除序列中的前缀元素，直到某个条件不满足。

1

assert list(dropwhile(lambda x: x < 5, [1, 4, 6, 4, 1])) == [6, 4, 1]

filterfalse

filterfalse可以过滤出一个序列中不满足某个条件的元素。

1

assert list(filterfalse(lambda x: x % 2 == 0, range(10))) == [1, 3, 5, 7, 9]

pairwise

pairwise类似于一个容量为 2 的滑动窗口，每次迭代返回一对元素。

1

asset list(pairwise([1, 2, 3, 4, 5])) == [(1, 2), (2, 3), (3, 4), (4, 5)]

takewhile

takewhile遍历一个序列，直到第一个不满足某个条件的元素。

1

assert list(takewhile(lambda x: x < 5, [1, 4, 6, 4, 1])) == [1, 4]

排列组合迭代器

product

product可以得到多个序列的笛卡尔积。

1

assert list(product("ABCD", "xy")) == [('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y'), ('D', 'x'), ('D', 'y')]

permutations

permutations可以得到一个序列的全排列。

1
2

assert list(permutations([1, 2, 3])) == [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
assert list(permutations([1, 2, 3], 2)) == [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

combinations

combinations可以得到一个序列的组合。

1

assert list(combinations(range(4),2)) == [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

combinations_with_replacement

combinations_with_replacement可以得到一个序列的可重复组合。

1

list(combinations_with_replacement([1,2,3],2)) == [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

总结

使用 Python 实现算法相比其他语言的一个优势就是标准库中的itertools，可以节省大量编写 for 循环和递归函数的时间。

【使用 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 先生写过一篇特性开关模式的文章，感兴趣的读者可以深入阅读。