概要

與 C、Rust 和 Go 不同，Python 默認的int 具有任意大小。[注1] 、[注2]  

這意味著，一個整數可以存儲無限大的值，只要內存足夠。

例如，你可以打開 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] 

哥德爾數（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] 我們選擇在最后一個非零指數處停止。

當列表中包含較大的數字時，這種表示形式也會使用非常大的數字。那是因為列表中的數字表示的是指數，所以 int 的大小與它們成指數增長。例如，[50, 1000, 250] 需要使用大小為 2266 比特的數字表示。

另一方面，相比于其它用 int 編碼的列表，那些包含非常多小整數的長列表，尤其是大型稀疏列表（即大部分的值都為 0），則擁有非常緊湊的表示形式。

提醒一下，將 list 編碼為 int，這不是很好的編程實踐，僅僅是一個好玩的實驗。 

Python實現

讓我們看一下 Python 的實現。這里有幾點注意事項：

1. 我們會使用帶有 yield 的函數，因為它極大地簡化了操作。[注5]

2. 你會看到大量的 while 循環。這是因為列表生成式、range 和大多數你打算在 for 循環中使用的東西，都被禁止用在只有 int 類型的方言中。所有這些都被 while 循環替代了。 

質數生成器

我們要編寫的第一個函數是一個迭代器，它將按順序生成質數。它從頭到尾都很關鍵。這里的實現是最簡單可行的版本。

我可能很快會寫一篇完整的關于生成質數的算法的文章，因為這是一個很酷的話題，本身也是一個古老的研究領域。最廣為人知的算法是愛拉托遜斯篩法（Sieve of Erathosthenes ），但這只是冰山一角。[注6]  

在這里，一個非常幼稚的實現就夠了：

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 表示形式。