关于python:脑洞如何用一个整数来表示一个列表

原题 | Storing a list in an int (https://iantayler.com/2020/12…

作者 | Computer Wit

译者 | 豌豆花下猫（“Python 猫”公众号作者）

申明 | 本翻译已失去原作者受权。为便于浏览，内容略有改变。

概要

与 C、Rust 和 Go 不同，Python 默认的 int 具备任意大小。[[注 1]](https://iantayler.com/2020/12…、[[ 注 2] ](https://iantayler.com/2020/12…

这意味着，一个整数能够存储无限大的值，只有内存足够。

例如，你能够关上 Python3 并运行以下命令：

>>> import math
>>> math.factorial(2020)
[number omitted]  # Python 猫注：此处求 2020 的阶乘，后果是一长串数字，所以省略
>>> math.log2(math.factorial(2020))
19272.453841606068
>>> type(math.factorial(2020))
<class 'int'>

也就是说，在 Python 中，平时应用的 int 能够轻松地保留一个占用 19273 比特的 C 类型固定大小无符号 int 类型的值（C-style fixed-size unsigned int）。在 Python 这样的语言中，便利性高于速度和内存效率，这的确很有用。

这种有限的精度，也意味着咱们能够在单个 int 中存储任意数量的信息。只有编码正确，一整本书、一整个数据库、甚至任何货色，都能够被存入一个独自的 Python int 中。

(Python 猫注：这有一篇文章，深度分析了 Python 整型不会溢出的实现原理，可作关联浏览)

因而，咱们能够构想出一种 Python 的方言，它只有整型，须要用 int 示意其它所有的类型（字典、列表、等等）。咱们还有一些非凡的函数和办法，能够将 int 视为 list、dict 等等。

这将会是一个乏味而好玩的练习，而这就是本文想要做的事。

有一个不言而喻的实现办法：所有数据结构只是内存中的位数组（bit-arrays）。最坏的状况下，它是一组相干的位数组（例如，像链表或树中的每个节点），并且它们的汇合也只是位数组。位数组能够被解释为二进制数。所以咱们必然能这样做。但这有点无聊。

在本博文以及本系列的后续博文中，我将介绍一些用 int 来示意简单数据结构的办法。它们不肯定是最紧凑、最正当或最无效的，其独特的指标是找到这些数据结构的乏味的示意形式。[[注 3]](https://iantayler.com/2020/12…

哥德尔数（Gödel numbering）简介

咱们要示意的第一个数据结构是 list。咱们将应用以逻辑学家 KurtGödel 命名的 Gödel 数。为了不便起见，咱们仅解决由无符号整数（即自然数）组成的列表。

哥德尔数的原理是令每个大于 1 的自然数都用惟一的质数合成来示意。它根据的是算术的根本定理。

（Python 猫注：质数合成，即 prime factorization，又译作质因数分解、素因子合成等，指的是把每个数都写成用质数相乘的模式）

看一些例子：

一个数字能够通过其质因子（prime factors）的指数列表来惟一标识（直到其最高位的非零指数）。所以，咱们能够用 126 来示意列表 [1, 2, 0, 1]。列表中的第一个数字是 126 作质数合成后 2 的指数，第二个数是 3 的指数，依此类推。

再来几个例子：

如果列表开端有 0，该怎么办呢？好吧，基于这样的编码，不会呈现这种状况。

在咱们的质数合成中，指数为 0 的质数可能有有限个，因而咱们须要停在某个中央。[[注 4]](https://iantayler.com/2020/12… 咱们抉择在最初一个非零指数处进行。

当列表中蕴含较大的数字时，这种示意模式也会应用十分大的数字。那是因为列表中的数字示意的是指数，所以 int 的大小与它们成指数增长。例如，[50, 1000, 250] 须要应用大小为 2266 比特的数字示意。

另一方面，相比于其它用 int 编码的列表，那些蕴含十分多小整数的长列表，尤其是大型稠密列表（即大部分的值都为 0），则领有十分紧凑的示意模式。

揭示一下，将 list 编码为 int，这不是很好的编程实际，仅仅是一个好玩的试验。

Python 实现

让咱们看一下 Python 的实现。这里有几点注意事项：

1. 咱们会应用带有 yield 的函数，因为它极大地简化了操作。[[注 5]](https://iantayler.com/2020/12…
2. 你会看到大量的 while 循环。这是因为列表生成式、range 和大多数你打算在 for 循环中应用的货色，都被禁止用在只有 int 类型的方言中。所有这些都被 while 循环代替了。

质数生成器

咱们要编写的第一个函数是一个迭代器，它将按程序生成质数。它从头到尾都很要害。这里的实现是最简略可行的版本。

我可能很快会写一篇残缺的对于生成质数的算法的文章，因为这是一个很酷的话题，自身也是一个古老的钻研畛域。最广为人知的算法是爱拉托逊斯筛法（Sieve of Erathosthenes），但这只是冰山一角。[[注 6]](https://iantayler.com/2020/12…

在这里，一个十分童稚的实现就够了：

def primes(starting: int = 2):
    """Yield the primes in order.
     
    Args:
        starting: sets the minimum number to consider.
     
    Note: `starting` can be used to get all prime numbers
    _larger_ than some number. By default it doesn't skip
    any candidate primes.
    """
    candidate_prime = starting
    while True:
        candidate_factor = 2
        is_prime = True
        # We'll try all the numbers between 2 and
        # candidate_prime / 2. If any of them divide
        # our candidate_prime, then it's not a prime!
        while candidate_factor <= candidate_prime // 2:
            if candidate_prime % candidate_factor == 0:
                is_prime = False
                break
            candidate_factor += 1
        if is_prime:
            yield candidate_prime
        candidate_prime += 1

创立空列表

def empty_list() -> int:
    """Create a new empty list."""
    # 1 is the empty list. It isn't divisible by any prime.
    return 1

遍历元素

def iter_list(l: int):
    """Yields elements in the list, from first to last."""
    # We go through each prime in order. The next value of
    # the list is equal to the number of times the list is
    # divisible by the prime.
    for p in primes():
        # We decided we will have no trailing 0s, so when
        # the list is 1, it's over.
        if l <= 1:
            break
        # Count the number of divisions until the list is
        # not divisible by the prime number.
        num_divisions = 0
        while l % p == 0:
            num_divisions += 1
            l = l // p  # could be / as well
        yield num_divisions

拜访元素

def access(l: int, i: int) -> int:
    """Return i-th element of l."""
    # First we iterate over all primes until we get to the
    # ith prime.
    j = 0
    for p in primes():
        if j == i:
            ith_prime = p
            break
        j += 1
    # Now we divide the list by the ith-prime until we
    # cant divide it no more.
    num_divisions = 0
    while l % ith_prime == 0:
        num_divisions += 1
        l = l // ith_prime
    return num_divisions

增加元素

def append(l: int, elem: int) -> int:
    # The first step is finding the largest prime factor.
    # We look at all primes until l.
    # The next prime after the last prime factor is going
    # to be the base we need to use to append.
    # E.g. if the list if 18 -> 2**1 * 3**2 -> [1, 2]
    # then the largest prime factor is 3, and we will
    # multiply by the _next_ prime factor to some power to
    # append to the list.
    last_prime_factor = 1  # Just a placeholder
    for p in primes():
        if p > l:
            break
        if l % p == 0:
            last_prime_factor = p
    # Now get the _next_ prime after the last in the list.
    for p in primes(starting=last_prime_factor + 1):
        next_prime = p
        break
    # Now finally we append an item by multiplying the list
    # by the next prime to the `elem` power.
    return l * next_prime ** elem

试用这些函数

你能够关上一个 Python、iPython 或 bPython 会话，并试试这些函数！

倡议列表元素应用从 1 到 10 之间的数字。如果应用比拟大的数字，则 append 和 access 可能会破费很长时间。

从某种程度上说，应用哥德尔数来示意列表并不实用，只管能够通过优化质数生成及合成算法，来极大地扩充可用数值的范畴。

In [16]: l = empty_list()
 
In [17]: l = append(l, 2)
 
In [18]: l = append(l, 5)
 
In [19]: list(iter_list(l))
Out[19]: [2, 5]
 
In [20]: access(l, 0)
Out[20]: 2
 
In [21]: access(l, 1)
Out[21]: 5
 
In [22]: l
Out[22]: 972  # Python 猫注：2^2*3^5=972

其它 int 编码

咱们看到了一种将自然数列表示意为 int 的办法。还有其它更实用的办法，这些办法依赖于将数字的二进制模式细分为大小不一的块。我置信你能够提出这样的倡议。

我当前可能会写其它文章，介绍更好的用于生成和合成质数的算法，以及其它简单数据结构的 int 示意模式。

脚注

1. 我认为在内存不足之前，程序也会呈现中断，然而文档的确明确地提到它们具备有限的精度。
2. 请留神，对于 Python3，这是正确的，但对于 Python2 则不然。对于 Python2，int 是固定大小的。我认为在 2020 年用 Python 指代 Python3 是没问题的，但我也认为这个细节值得加一条脚注。
3. 对于用哥德尔数示意列表，这很容易被反驳说是一种蹩脚的示意模式。在后续的博文中，咱们会探讨无关示意模式的衡量问题。
4. 咱们能够将列表的长度存储在独自的 int 中，据此晓得要在列表开端思考多少个 0。（猫注：还有几句话没看懂，不译）If we don’t want to have a whole separate int, we can always write the length of the list as the exponent of 2 and start the actual list with the exponent of 3. This has some redundant information, though. The way to avoid redundant information is to store the number of final 0s in the list, instead of the entire length. We won’t be worrying about any of this, though.
5. 请留神，跟应用 return 并将状态变量作为参数相比，应用 yield 没有区别（通常足以取得最初一个返回的元素）。这有点像 Continuation Passing Style。也相似于平时的使非尾递归函数尾递归的累加器。如果你从未据说过累加器技巧，这里有一些链接 [[1]](https://raganwald.com/2018/05…、[[2]](https://blog.appsignal.com/20…。我将来可能会在没有它们的语言中，写模拟迭代器的货色。
6. 另请参见《The Genuine Sieve of Erathosthenes》论文，它廓清了这一算法是如何被定义的。

Python 猫注： 以上是全副译文，但我最初还想补充一个乏味的内容。在《黑客与画家》中，保罗·格雷巨匠有一个惊人的预言，他认为在逻辑上不须要有整数类型，因为整数 n 能够用一个 n 元素的列表来示意。哈哈，这跟上文的脑洞恰好反过来了！设想一下，一个只有整数类型没有列表的编程语言，以及一个只有列表类型没有整数的编程语言，哪一个更有可能在将来呈现呢？