腦洞：如何用一個整數來表示一個列表？

2020 年 12 月 22 日
筆記
Python無止境

原題 | Storing a list in an int (//iantayler.com/2020/12/07/storing-a-list-in-an-int)

作者 | Computer Wit

譯者 | 豌豆花下貓（「Python貓」公眾號作者）

聲明 | 本翻譯已得到原作者授權。為便於閱讀，內容略有改動。

概要

與 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 的實現。這裡有幾點注意事項：

我們會使用帶有 yield 的函數，因為它極大地簡化了操作。[注5]
你會看到大量的 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 表示形式。

腳註

我認為在記憶體不足之前，程式也會出現中斷，但是文檔確實明確地提到它們具有無限的精度。
請注意，對於 Python3，這是正確的，但對於 Python2 則不然。對於 Python2，int 是固定大小的。我認為在 2020 年用 Python 指代 Python3 是沒問題的，但我也認為這個細節值得加一條腳註。
對於用哥德爾數表示列表，這很容易被反駁說是一種糟糕的表示形式。在後續的博文中，我們會討論有關表示形式的權衡問題。
我們可以將列表的長度存儲在單獨的 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.
請注意，跟使用 return 並將狀態變數作為參數相比，使用 yield 沒有區別（通常足以獲得最後一個返回的元素）。這有點像 Continuation Passing Style。也類似於平常的使非尾遞歸函數尾遞歸的累加器。如果你從未聽說過累加器技巧，這裡有一些鏈接[1] 、[2] 。我未來可能會在沒有它們的語言中，寫模仿迭代器的東西。
另請參見《 The Genuine Sieve of Erathosthenes》論文，它澄清了這一演算法是如何被定義的。

Python貓註： 以上是全部譯文，但我最後還想補充一個有趣的內容。在《黑客與畫家》中，保羅·格雷大師有一個驚人的預言，他認為在邏輯上不需要有整數類型，因為整數 n 可以用一個 n 元素的列表來表示。哈哈，這跟上文的腦洞恰好反過來了！想像一下，一個只有整數類型沒有列表的程式語言，以及一個只有列表類型沒有整數的程式語言，哪一個更有可能在未來出現呢？

Tags: Python無止境