为什么Python可以处理任意长度的整数运算——Python原理详解

在做LeetCode题目的时候，有一类题目是关于大数运算的。比如，全排列计算或者组合运算，在使用C语言或者Java代码解决这类问题的时候都会遇到变量数值超过阈值的情况。一般来说需要自己构造字符串数组或者是其它数组来存储超过长度的数值。但是，使用Python语言处理这类问题时候却毫无压力，这类题目的计算不会有任何问题，例如，如果使用Python计算$2^{20000}$时候，轻轻松松输出结果：

```python
>>> 2 ** 20000
398027684033796659235430720619120......
```

显然，这么大的数用C语言或者Java都是无法直接处理的。那么，Python是如何处理如此大的数的，为什么Python的整数类型没有长度限制？本文将从Python底层实现解释这个问题。

#### 一、Python大整数历史
先简单介绍一下，在Python2中，整数有两种类型，int与long。但是，我们使用的时候没有区分，只是在内部会有不同处理：

```python
# Python 2.7版本
>>> x=10
>>> print(type(x))
<class 'int'>
>>> y=111111111111111111111111111111111111111111111111111111111111111111
>>> print(type(y))
<class 'long'>
```

但是实际会有不同的类型存在。主要是因为Python底层是C语言实现的，因此，对于整数的长度有限制。在Python2中，int的最大值是受限于C语言的long类型（C语言中的long在32位机器和64位机器不一样长度，这也是导致python2编译后的pyc文件无法在不同架构机器移植的原因之一）超过这个数值都是long。不过，Python2的long也是没有长度限制的。在Python3中，long类型已经被删除，只保留int来处理数据。接下来我们描述Python如何使用int处理很大的数字的。

#### 二、Python大数字处理方式
尽管Python2在内部使用int或者long来区分整数类型，对用户来说这种区分不感知，但是依然有一些缺点。例如，编译后的代码迁移或者是性能方面都是有影响的。因此，Python3中全部使用一个int类型来处理所有整数数字。那么，Python是如何保证效率的同时又能处理超出长度限制的数值呢？这就是Python底层的实现了。

Python底层是C语言编写的，所有的数据类型都来自与C语言定义的一个结构（strut）：
```C
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size;
} PyVarObject;
```
这里涉及到C语言的基本知识，我们简单介绍一下，理解的童鞋可以跳过。`struct`是定义一个结构，你可以理解是一个对象，里面可以定义任意不同类型的字段属性。例如如果我们定义一本书，书包含书名字（字符串），编号（整形）。那么这个书就可以使用`struct`定义。里面的名字与编号就是结构中的基本类型了。`typedef`是类型别名，就是说我定义的`struct`这个类型名字太长了，不容易记住，所以我起个别名指代这个类型。

好了，大家可以看到PyVarObject是Python底层定义的所有对象的“父类”，其它所有的类型都需要实现这个类型。关于这里面的两个成员待会解释。那么，Python中int的类型就是下面这个：

```C
struct _longobject {
    PyObject ob_base;
    Py_ssize_t ob_size;
    digit ob_digit[1];
};
```

可以看到，Python中的int数字是一个C语言定义的`_longobject`结构，它可以存储大数字的核心就是把大数字变成一个数组存储，既不是简单的将数字的每一位变成char，也不是整体转换成其它类型。我们来详细解释一下。

可以看到，这个结构里面包含三个部分。

##### 2.1、PyObject ob_base
ob_base也是一个结构，类型是PyObject，里面存储了这个变量的一些基本信息，例如，著名的Python变量的引用计数（reference counting）就在这里，可以理解为基本变量的一些信息。

##### 2.2、 Py_ssize_t ob_size
ob_size是用来存储当前类型的元素数量的。前面说过，Python将大数字转成“数组”存储，那么这个变量主要就是存放数组中包含的元素个数，注意，这里的元素与原始数字中每一位并不是一一对应的。所以它的长度不等于数字的长度。这个数字让Python知道当前数值的一个范围，可以提升效率。

##### 2.3、 digit ob_digit[1];
这就是存放实际数字的数组了。默认初始化长度为1的数组。这个数组的类型是`uint32_t`，也就是C语言中的无符号整数类型。由于这是一个数组，实际上`ob_digit`是一个指针`digit *`。

需要注意的是，如果我们将原始数字，例如123转成 [1,2,3]这种类型，那么就大大浪费的内存空间了。所以，python并不是如此简单的转换。在Python内部，是将我们常见的10进制（其它一样）转成$2^{30}$进制数字存储的。对！你没看错，它是1073741824进制。也就是说，前面的digit数组中一个元素的最大值其实是1073741823。那么，例如，如果我们存`1152921504606846976`这么大的数字，实际上只是`100`就行了：

```math
1152921504606846976 = 1 \times (2^{30})^2 + 0 \times (2^{30})^1 + 0 \times (2^{30})^0
```

不过，Python内部是反过来存储的，也就是`ob_digit`最终的结果是`[0, 0, 1]`，而`ob_size`就是3了。

可以看到，由于一个digit元素是无符号32位整型，那么定义$2^{30}$进制会使得数组中每一个元素几乎都完全利用了所有的地址空间，这个效率就很高了。不过，针对超过$2^{30}$的数字，其加减乘除的计算就不能使用原生的C语言实现了，需要额外定义。不过，虽然稍增复杂性，但是做到了没有长度限制的整数。

那有童鞋会问，为啥不直接使用long或者更高进制的数组来表示呢？显然，如果更高进制数组，那么即使很小的数如1，也需要一个较大的空间存储，也不十分划算，因此，这也是权衡的结果。

参考1：https://www.codementor.io/arpitbhayani/how-python-implements-super-long-integers-12icwon5vk
参考2：https://peps.python.org/pep-0237/

为什么Python可以处理任意长度的整数运算——Python原理详解

欢迎大家关注DataLearner官方微信，接受最新的AI技术推送

相关博客

最热博客