怎么用一個整數(shù)來表示一個列表

概要

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

這意味著，一個整數(shù)可以存儲無限大的值，只要內(nèi)存足夠。

例如，你可以打開 Python3 并運行以下命令：

>>> import math
>>> math.factorial(2020)
[number omitted]  # Python貓注：此處求2020的階乘，結(jié)果是一長串?dāng)?shù)字，所以省略
>>> 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 這樣的語言中，便利性高于速度和內(nèi)存效率，這確實很有用。

這種無限的精度，也意味著我們可以在單個 int 中存儲任意數(shù)量的信息。只要編碼正確，一整本書、一整個數(shù)據(jù)庫、甚至任何東西，都可以被存入一個單獨的 Python int 中。

(Python貓注：這有一篇文章 ，深度剖析了Python整型不會溢出的實現(xiàn)原理，可作關(guān)聯(lián)閱讀)

因此，我們可以設(shè)想出一種 Python 的方言，它只有整型，需要用 int 表示其它所有的類型（字典、列表、等等）。我們還有一些特殊的函數(shù)和方法，可以將 int 視為 list 、dict 等等。

這將會是一個有趣而好玩的練習(xí)，而這就是本文想要做的事。

有一個顯而易見的實現(xiàn)方法：所有數(shù)據(jù)結(jié)構(gòu)只是內(nèi)存中的位數(shù)組（bit-arrays）。最壞的情況下，它是一組相關(guān)的位數(shù)組（例如，像鏈表或樹中的每個節(jié)點），并且它們的集合也只是位數(shù)組。位數(shù)組可以被解釋為二進(jìn)制數(shù)。所以我們必然能這樣做。但這有點無聊。

在本博文以及本系列的后續(xù)博文中，我將介紹一些用 int 來表示復(fù)雜數(shù)據(jù)結(jié)構(gòu)的方法。它們不一定是最緊湊、最合理或最有效的，其共同的目標(biāo)是找到這些數(shù)據(jù)結(jié)構(gòu)的有趣的表示方式。[注3] 

哥德爾數(shù)（G?del numbering）簡介

我們要表示的第一個數(shù)據(jù)結(jié)構(gòu)是 list。我們將使用以邏輯學(xué)家 KurtG?del 命名的G?del數(shù)。為了方便起見，我們僅處理由無符號整數(shù)（即自然數(shù)）組成的列表。

哥德爾數(shù)的原理是令每個大于 1 的自然數(shù)都用唯一的質(zhì)數(shù)分解來表示。它依據(jù)的是算術(shù)的基本定理。

（Python貓注：質(zhì)數(shù)分解，即 prime factorization，又譯作質(zhì)因數(shù)分解、素因子分解等，指的是把每個數(shù)都寫成用質(zhì)數(shù)相乘的形式）

看一些例子：

 

一個數(shù)字可以通過其質(zhì)因子（prime factors ）的指數(shù)列表來唯一標(biāo)識（直到其最高位的非零指數(shù)）。所以，我們可以用 126 來表示列表[1, 2, 0, 1] 。列表中的第一個數(shù)字是 126 作質(zhì)數(shù)分解后 2 的指數(shù)，第二個數(shù)是 3 的指數(shù)，依此類推。

再來幾個例子：

 

如果列表末尾有 0 ，該怎么辦呢？好吧，基于這樣的編碼，不會出現(xiàn)這種情況。

在我們的質(zhì)數(shù)分解中，指數(shù)為 0 的質(zhì)數(shù)可能有無限個，因此我們需要停在某個地方。[注4] 我們選擇在最后一個非零指數(shù)處停止。

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

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

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

Python實現(xiàn)

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

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

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

質(zhì)數(shù)生成器

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

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

在這里，一個非常幼稚的實現(xiàn)就夠了：

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  
  

創(chuàng)建空列表

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  
  

試用這些函數(shù)

你可以打開一個 Python、iPython 或 bPython會話，并試試這些函數(shù)！

建議列表元素使用從 1 到 10 之間的數(shù)字。如果使用比較大的數(shù)字，則 append 和 access 可能會花費很長時間。

從某種程度上說，使用哥德爾數(shù)來表示列表并不實用，盡管可以通過優(yōu)化質(zhì)數(shù)生成及分解算法，來極大地擴(kuò)大可用數(shù)值的范圍。

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 編碼

我們看到了一種將自然數(shù)列表表示為 int 的方法。還有其它更實用的方法，這些方法依賴于將數(shù)字的二進(jìn)制形式細(xì)分為大小不一的塊。我相信你可以提出這樣的建議。

我以后可能會寫其它文章，介紹更好的用于生成和分解質(zhì)數(shù)的算法，以及其它復(fù)雜數(shù)據(jù)結(jié)構(gòu)的 int 表示形式。