原标题|将一个列表存储在一个int中(https://iantayler.com/2020/12...作者|电脑机智翻译|猫下豌豆花(《蟒猫》公众号作者)声明|本翻译已获得授权原作者。为了便于阅读，内容略有修改。总结与C、Rust和Go不同，Python默认为任意大小的int。[[注1]](https://iantayler.com/2020/12...,[[注2]](https://iantayler.com/2020/12...这意味着只要有足够的内存，整数可以存储无穷大的值。例如，您可以打开Python3并运行下面命令：>>>importmath>>>math.factorial(2020)[numberomitted]#Python猫注意：这里求2020的阶乘，结果是一长串数字，所以省略>>>math.log2(math.factorial(2020))19272.453841606068>>>type(math.factorial(2020))也就是说，在Python中，常用的int可以很轻松的容纳一个占19273位的C类型的值类型固定大小的unsignedint（C风格固定大小的unsigned整数）。在像Python这样方便胜过速度和内存效率的语言中，这确实很有用。这种无限的精度也意味着我们可以在一个int中存储任何数量的信息。只要编码正确，整本书、整个数据库，甚至任何东西都可以存储在一个Pythonint中。（Python猫注：这里有一篇文章，深入分析Python整数不会溢出的实现原理，可以作为相关阅读）因此，我们可以想象一个只有整数的Python方言，需要使用int表示所有其他类型（字典、列表等）。我们还有一些特殊的函数和方法可以将int视为列表、dict等。这将是一个有趣而有趣的练习，而这正是本文想要做的。有一个明显的方法可以做到这一点：所有数据结构都只是内存中的位数组。在最坏的情况下，它是一组相关的位数组（例如，就像链表或树中的每个节点），它们的集合也只是位数组。位数组可以解释为二进制数。所以我们必须能够做到这一点。但这有点无聊。在本博文和本系列的后续博文中，我将介绍一些使用int表示复杂数据结构的方法。它们不一定是最紧凑、最合理或最有效的，共同的目标是找到这些数据结构的有趣表示。[[注3]](https://iantayler.com/2020/12...哥德尔数法介绍我们要表示的第一个数据结构是列表，我们将以逻辑学家KurtG?del的名字命名哥德尔数为方便起见，我们只处理由无符号整数（即自然数）组成的列表。哥德尔数的原理是让每一个大于1的自然数都由一个唯一的素数分解表示。它是基于算术的基本的定理。它由其素因子的指数列表（直到其最高非零指数）唯一标识。因此，我们可以使用126来表示列表[1,2,0,1]。第一个在列表中的数是126质因数分解后2的指数，第二个数是3的指数，等等再举几个例子：如果列表末尾有一个0怎么办？嗯，基于这个编码，不会出现这种情况，在我们的素因数分解中，可能有无限多个指数为0的素数，所以我们需要停在某处。[[注释4]](https://iantayler.com/2020/12...我们选择在最后一个非零指数处停止。当列表包含更大的数字时，这种表示也适用于非常大的数字。那是因为列表中的数字代表指数，所以int的大小随着它们呈指数增长。例如[50,1000,250]需要使用大小为2266位的数字来表示。另一方面，那些包含非常长的列表与其他int编码列表相比，许多小整数，特别是大的稀疏列表（即大多数值都是0）具有非常紧凑的表示。提醒一下，将列表编码为int不是好的编程习惯，这只是一个有趣的实验。Python实现让我们看一下Python实现。这里有几个注意事项：我们将使用带yield的函数，因为它大大简化了事情。[[注释5]](https://iantayler.com/2020/12...你会看到很多while循环。这是因为列表理解、范围和大多数你计划在for循环中使用的东西,在只有int类型的方言中是被禁止的。所有这些都被while循环所取代。素数生成器我们将编写的第一个函数是一个迭代器，它将按顺序生成素数。至关重要。这里的实现是最简单的版本。我可能很快会写一整篇关于生成素数的算法的文章，因为它是一个很酷的话题，而且本身就是一个古老的研究领域。最广为人知的算法是埃拉托色尼筛法（SieveofErathosthenes），但是这只是冰山一角。[[注6]](https://iantayler.com/2020/12...在这里，一个非常幼稚的现实就够了：defprimes(starting:int=2):"""Yieldtheprimesinorder.Args:starting:设置要考虑的最小数。注意：`starting`可用于获取所有_大于_某个数的素数。默认情况下，它不会跳过任何候选素数。"""candidate_prime=startingwhileTrue:candidate_factor=2is_prime=True#We'lltr??yallthenumbersbetween2and#candidate_prime/2.如果它们中的任何一个除以我们的candidate_prime，那么它不是素数！whilecandidate_factor<=candidate_prime//2:ifcandidate_prime%candidate_factor==0:is_prime=Falsebreakcandidate_factor+=1ifis_prime:yieldcandidate_primecandidate_prime+=1创建空列表defempty_list()->int:"""Createanewemptylist."""#1istheempty李斯吨。它不能被任何素数整除。return1遍历元素defiter_list(l:int):"""产生列表中的元素，从头到尾。"""#我们按顺序遍历每个素数。#列表的下一个值等于列表被素数整除的次数。forpinprimes():#我们决定没有尾随的0，所以当#列表为1时，它就结束了。ifl<=1:break#计算分割数，直到列表不能被素数整除。num_divisions=0whilel%p==0:num_divisions+=1l=l//p#couldbe/asyieldnum_divisions访问元素defaccess(l:int,i:int)->int:"""返回l的第i个元素。"""#首先我们遍历所有素数，直到我们到达#第i个素数。j=0forpinprimes():ifj==i:ith_prime=pbreakj+=1#现在我们除l由第i个素数计算，直到我们不能再将它除尽为止。num_divisions=0whilel%ith_prime==0:num_divisions+=1l=l//ith_primereturnnum_divisions添加元素defappend(l:int,elem:int)->int:#第一步是找到最大的素因子.#我们查看所有素数直到l。#最后一个素数因子之后的下一个素数将成为我们需要用来追加的基础。#例如如果列表if18->2**1*3**2->[1,2]#那么最大的质因数是3，我们将#乘以_next_质因数的某个幂来#追加到列表。last_prime_factor=1#Justaplaceholderforpinprimes():ifp>l:breakifl%p==0:last_prime_factor=p#现在获取列表中最后一个素数之后的下一个素数。forpinprimes(starting=last_prime_factor+1):next_prime=pbreak#现在最后我们追加一个项目通过将列表#乘以下一个素数的“elem”次方。returnl*next_prime**elem尝试这些函数您可以打开Python、iPython或bPython会话并尝试这些函数！建议对列表元素使用1到10之间的数字。如果您使用更大的数字，追加和访问可能需要很长时间。使用哥德尔数来表示列表有些不切实际，尽管可以通过优化素数生成和因式分解算法极大地扩展可用值的范围。在[16]中：l=empty_list()在[17]中：l=append(l,2)在[18]中：l=append(l,5)在[19]中：list(iter_list(l))Out[19]:[2,5]在[20]:access(l,0)Out[20]:2In[21]:access(l,1)Out[21]:5In[22]:lOut[22]:972#Pythoncatnote:2^2*3^5=972其他int编码我们看到了一种将自然数列表表示为int的方法。还有其他更实用的方法依赖于将数字的二进制形式细分为不同大小的块。我相信你可以提出这样的建议。以后我可能会写其他文章，介绍更好的生成和分解质数的算法，以及其他复杂数据结构的int表示。脚注我认为程序也会在内存不足之前中断，但文档确实明确提到它们具有无限精度。请注意，这适用于Python3，但不适用于Python2。对于Python2，int是固定大小的。我认为用Python来指代2020年的Python3是可以的，但我也认为这个细节值得一个脚注。这很容易被认为是哥德尔数对列表的代表性较差。在后续博文中，我们将讨论围绕表示的权衡。我们可以将列表的长度存储在一个单独的int中，从中我们知道在列表末尾要考虑多少个0。（猫注：还有几句没看懂，就不翻译了）如果我们不想有一个完整的单独的int，我们总可以把list的长度写成的exponent2并以3的指数开始实际列表。不过，这有一些冗余信息。避免冗余信息的方法是存储列表中最后一个0的个数，而不是整个长度。不过，我们不会担心这些。请注意，使用yield与使用带有状态变量作为参数的return相比没有区别（通常足以获取最后返回的元素）。这有点像ContinuationPassingStyle。也类似于使非尾递归函数尾递归的常用累加器。如果您从未听说过累加器技巧，这里有一些链接[[1]](https://raganwald.com/2018/05...,[[2]](https://blog.appsignal.com/20...。我以后可能会用没有迭代器的语言写一些模仿迭代器的东西。另见《 The Genuine Sieve of Erathosthenes》论文，阐明了这个算法是如何定义的。Python猫注：上面是完整的翻译，但我想在最后补充一个有趣的内容。在《黑客与画家》中，PaulGray大师做了一个惊人的预言，他认为逻辑上不需要整数类型，因为整数n可以使用nelement哈哈，这和上面的脑洞正好相反！试想一下，一种只有整数类型没有列表的编程语言，和一种只有列表类型没有整数的编程语言，未来哪一个更有可能出现？
