脑洞:如何用一个整数来示意一个列表?_fm分享平台

一个小技巧助您减少if语句的状态判断 原题 | Storing a list in an int (https://iantayler.com/2020/12/07/storing…

一个小技巧助您减少if语句的状态判断

原题 | Storing a list in an int (https://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,又译作质因数剖析、素因子剖析等,指的是把每个数都写成用质数相乘的形式)

看一些例子:

【fmfrj分享】fm分享平台!

【Go语言绘图】图片添加文字(二)

专业网站SEO优化,百度排名收录,整站打包优化出售。代做网站排名优化Q:819640

一个数字可以通过其质因子(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 示意形式。

脚注

  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][2] 。我未来可能会在没有它们的语言中,写模拟迭代器的器械。
  6. 另请参见《 The Genuine Sieve of Erathosthenes》论文,它澄清了这一算法是若何被界说的。

Python猫注: 以上是所有译文,但我最后还想弥补一个有趣的内容。在《黑客与画家》中,保罗·格雷大师有一个惊人的预言,他以为在逻辑上不需要有整数类型,由于整数 n 可以用一个 n 元素的列表来示意。哈哈,这跟上文的脑洞正好反过来了!想象一下,一个只有整数类型没有列表的编程语言,以及一个只有列表类型没有整数的编程语言,哪一个更有可能在未来泛起呢?

代做网站排名优化Q:819640

《痞子衡嵌入式半月刊》 第 22 期

作者: admin

相关推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

友情链接