从 0 开始实现 Python 简化版 List

从 0 开始实现 Python 简化版 List

轻雨酱初一初二那会儿刚接触 Python 的时候,就有一种好奇——这里,怎么没有数组呀?某度一番,发现 Python 有一个叫列表的东东,是所谓数组的一个超集,支持好多好多神奇的功能,甚至同一个列表里,可以放各种各样的元素,云云。

当然后面轻雨酱就发现,Python 所谓的,支持存取任意类型的 List,无非是一个 PyObject* 的数组,即 Python 中万物皆对象,我们把元素的指针排排坐,不就成了 List 了吗。

所以今天呢,轻雨酱就从 0 开始写一个简化版的 List,何为简化版呢,我们的 List 只支持存取 $[-2^{31},2^{31})$ 范围整数(32 位有符号)。不过原理都是一样的嘛,轻雨酱比较懒就瞎写着玩玩啦。

Warning!

本文的目标读者是新高考信息技术选考生,因此多少难免疏漏之处,欢迎在下方评论轻喷。

一个阅读提示,如果你是 Python 初学者,可以不用管我在前三章瞎比比,尝试动手实现一下最后一章的代码(较为简单),说不定能加深许多对 list 的理解。

0x01 Array 部分——通过 ctypes 调用 C module

前面我们说到,List 是 Array 的一个超集,实现 List 之前先让我们来想想怎么实现一个 Array。既然 Python 本身不提供 Array,我们只能从数组的原理来考虑实现:其本质是向内存申请了一段连续的地址以存储数据,如果我们能直接找 Python 兄“管理”一段内存,不就达到了我们的目的?

轻雨酱图省事,使用了 Python ctypes 标准库来解决这个问题。利用她,我们可以直接调用通过 C 编写的动态链接库(aka 动态共享对象),从而实现一些底层操作。我所编写的链接库的源码在这里:@github/my-list/c_module/arraymodule.cpp

细心的小伙伴可能发现了,为什么我的链接库源码用的不是 C,而是 C++,并且是 C++ & extern C 呢?一来主要为了图省事,用 C++ 现成的 new[]delete[](这东西的原理大概就下面这样),就不用和 C 一样手玩 *alloc 了:

二来由于 C++ 的函数和 dll 文件的函数表不是一一对应的(Name Mangling),如果不 extern C,就没法把在 C++ 里写的函数对应到动态链接库的函数表中,从而给我们的 Python 兄调用啦。

我的动态链接库实现了四个函数,即数组的四大基本操作:

函数 参数 功能
array_new(len) len 数组长度 【增】向内存申请 len 个 int 的连续空间,并返回起始位置指针,这个指针就指代该数组
array_delete(arr) arr 数组指针 【删】释放 arr 对应的数组在内存中占用的内存,即“删除”一个数组
array_set_value(arr, index, value) arr 数组指针 / index 下标 / value 值 【改】将数组 arr 的第 index 个元素修改为 value
array_get_value(arr, index) arr 数组指针 / index 下标 【查】获取数组 arr 的第 index 个元素(从 0 开始)
1
2
3
4
5
6
7
8
9
10
11
12
int *array_new(size_t len) {
return new int[len];
}
void array_delete(int *arr) {
delete[] arr;
}
int array_get_value(int *arr, size_t index) {
return *(arr + index);
}
void array_set_value(int *arr, size_t index, int value) {
*(arr + index) = value;
}

再在 Python 这边把 C 妹妹的接口导入过来:

1
2
3
array = cdll.LoadLibrary(path.join(dirname, r'c_module\arraymodule.dll'))
array.array_new.restype = POINTER(c_int)
array.array_new.argtypes = [c_size_t] # 另外三个接口也通过类似方法声明

如果不声明 restypeargtypes,ctypes 会统一将返回的 intint* 视为 number。

然后你就可以像 C 一样调用我们的 array_new 函数了,其返回类型是 POINTER(c_int)。如果我们再把她作为参数传递给下一个 C 函数,C 妹妹那边就能又能当成 int* 解析了。在此基础上进行简单的封装,便可完成我们的 Array 类,完整代码见 @github/my-list/my_array.py

需要注意的一点是,如果使用的版本高于 Python 3.8,上面的这段代码需要修改后才能运行,原因是 为加载第三方 dll 设置了新的安全机制。但轻雨酱的环境都是 Python 3.6,就没帮忙测试啦~ 感兴趣的童鞋可以自己改改。

以及上面的代码如果跑在非 Windows 的环境下,也需要自行编译动态共享对象(DSO)的 .so 文件。

0x02 List 基本操作——Python 也能重载运算符

刚刚我们实现了 Array,现在来想想我们的 List 怎么写。首先你得声明一个 List 类,最基本的,我们需要一个读元素和修改元素的操作。或许之前你用类来写代码时,都是通过实现一个个方法来完成的,但如果我们的 List 也长这样:

1
2
a.getByIndex(0)        #    ==>    a[0]
a.setByIndex(0, x) # ==> a[0] = x

嘛这就很不优美,肯定右边这种写法舒服啊!那怎么让我们的类也实现呢,就需要用到 __setitem____getitem__ 等方法了,详情参见 官方文档。这边就随便实现一下,以及 del 操作避免 内存泄漏。写出来大概长这样:

1
2
3
4
5
6
7
8
9
10
11
class List:
def __getitem__(self, index):
return self.arr[index if index >= 0 else index + self.len]

def __setitem__(self, index, value):
self.arr[index if index >= 0 else index + self.len] = value

def __delitem__(self, index):
for i in range(index, self.len - 1):
self.arr[i] = self.arr[i + 1]
self.len -= 1

0x03 List 元素增删——入门算法复杂度艺术

刚才我们完成了 List 的读取和修改,但怎么往里面添加或删除元素呢?如果你开始动键盘的话,或许要思考一个小问题,数组每次我们都只能申请或释放定长的空间,可我们的 List 却是变长的,我们并不知道其长度是多少,多申请了浪费,少申请了直接 boom,怎么取舍呢?

一个聪明的办法是,我们 List 的长度,做到动态了,但不是完全动态。怎么说呢?设定一个的阈值 $\texttt{STEP}$(应在 $[(k+1)/k,\sqrt{k}]$ 的范围内,其中 $k$ 是 $O(1)$ 的)。我们在类中记录当前列表的长度 $\texttt{len}$ 和开的内存长度 $\texttt{lim}$。如果添加元素后 $\texttt{len}$ 将要超过 $\texttt{lim}$,就将原来的内存释放,重新申请长度为 $\texttt{lim*SIZE}$ 的内存,并更新 $\texttt{lim}$。

虽然你不一定懂什么是复杂度,但我们可以一起简单分析下这个做法的正确性:

  1. 从空间上来说,我们一定有 $\texttt{len}*\texttt{STEP}\le\texttt{lim}$,所以我们并不会浪费太多空间,顶多也就 $(\texttt{STEP}-1)$ 倍嘛。

  2. 从时间上来说,我们要重开一次空间需要 $\texttt{len}$ 超过 $\texttt{lim}$ 对吧,粗略估计一下,我们存 $n$ 个数,实际上重开了 $\log{\texttt{STEP}}(n)$ 次空间,但是每次重开的开销和 $\texttt{lim}$ 是指数级增长的,我们可以计算总开销即:

    由于我们有 $n$ 次操作,故可以换句话说成:“单次操作均摊时空复杂度 $O(1)$”。

写出来大概长这样(self._malloc 即帮我们“申请”指定长度的区间,如果之前申请的空间足够只是没有使用,我们就不必找我们的 C 妹妹重新申请一段了):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def append(self, value):
self._malloc(self.len + 1)
self.arr[self.len] = value
self.len += 1

def pop(self, index=-1):
if index == -1:
self.len -= 1
return self.arr[self.len]
else:
result = self.arr[index]
for i in range(index, self.len - 1):
self.arr[i] = self.arr[i + 1]
return result

def extend(self, iterables):
source = [item for item in iterables]
self._malloc(self.len + len(source))
for value in source:
self.arr[self.len] = value
self.len += 1

0x04 List 修改查询——原理简单的点睛之笔

相信你一定迫不及待想动手写代码了,不如尝试实现一下 Python List 剩下的几个函数,让你的 List 有完整的功能吧:

方法 描述
list.count(obj) 统计某个元素在列表中出现的次数
list.index(obj) 从列表中找出某个值第一个匹配项的索引位置
list.insert(index, obj) 将对象插入列表
list.pop(index?=-1) 移除列表中的一个元素(默认最后一个元素),并且返回该元素的值
list.remove(obj) 移除列表中某个值的第一个匹配项
list.reverse() 反向列表中元素
list.sort(cmp=None, key=None, reverse=False) 对原列表进行排序

完整的代码在这里:@github/my-list/my-list.py;查看本文的所有代码请走这儿:@github/my-list