Python中处理非常大的数字

Question

Python中处理非常大的数字

189

我一直在考虑如何在Python中快速评估扑克牌手。我突然想到一个加速处理的方法是将所有卡面和花色表示为质数并将它们相乘以表示这些牌手。如下:

class PokerCard:
    faces = '23456789TJQKA'
    suits = 'cdhs'
    facePrimes = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 59, 61]
    suitPrimes = [2, 3, 5, 7]

并且

    def HashVal(self):
      return PokerCard.facePrimes[self.cardFace] * PokerCard.suitPrimes[self.cardSuit]

这将为每个手牌分配一个数字值，通过模运算可以告诉我手中有多少个国王或红心。例如，任何具有五张或更多草花的手牌都可以被2^5整除；任何具有四个国王的手牌都可以被59 ^ 4整除，等等。

问题在于，像AcAdAhAsKdKhKs这样的七张手牌的哈希值约为62.7万亿，需要使用超过32位才能在内部表示。有没有一种方法可以在Python中存储这样的大数，使我可以对其执行算术操作？

- Jekke

21

你确定一旦你以这种方式表示你的数据，你仍然会看到任何显著的速度提升吗？我知道这并没有回答你的问题，但是还是要说一下。 - Thomi

4

我的建议是：不要使用单独的变量来表示卡牌的值和花色，而是建议使用字典（例如：faces = {'2': 11, '3': 13, '4': 17, '5': 19, '6': 23, '7': 29, '8': 31, '9': 37, 'T': 41, 'J': 43, 'Q': 53, 'K': 59, 'A': 61} 和 suits = {'c': 2, 'd': 3, 'h': 5, 's': 7}），这样更加方便。 - JAB

1

依赖于整数乘法和因式分解听起来似乎会导致速度大幅下降，而不是提高。这可能也会导致内存损失。如果您真的想要优化手动存储，可以考虑使用每个等级3位的位域（因为每个等级可以有0到4张牌），以及每个花色4位。但我不确定Python是否是这种优化的最佳语言。也许使用collections.Counter会更简单。 - Stef

6个回答

121

Python自然地支持任意大的整数：

例如：

>>> 10**1000
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

例如，您甚至可以获得一个巨大的整数值fib(4000000)。

但目前它仍然不支持任意大的浮点数！

如果您需要一个大的浮点数，请查看decimal模块。此网站上有使用示例：OverflowError: (34, 'Result too large')

另一个参考：9.4. decimal — Decimal fixed point and floating point arithmetic

如果您需要加速，您甚至可以使用gmpy模块（这可能会引起您的兴趣）：Handling big numbers in code

另一个参考：gmpy（Google Code。只读）

- Nuno Aniceto

39

你可以出于兴趣这样做，但除此之外并不是一个好主意。我想不出它会加速任何操作。

获取一手牌需要进行整数因子分解操作，比访问数组要复杂得多。
添加卡片将涉及大型多字数数字的乘法，而删除卡片则需要用到除法，这两个操作都比从列表中添加或删除元素更昂贵。
一手牌的实际数值对你来说没有什么意义。你需要分解质数并遵循扑克规则来比较两手牌。对于这样的牌，h1 < h2 没有任何意义。

- Tom

29

Python自然地支持任意大的整数：

In [1]: 59**3*61**4*2*3*5*7*3*5*7
Out[1]: 62702371781194950

In [2]: _ % 61**4
Out[2]: 0

- Autoplectic

11

这些数字并不大。 - yav dat

3

他的例子不是很大，改用这个，它们就很大了：

593*614235735*7**230 2112200455965545784463763534981730015003287507654092906559062824748896024215265933823546366174073338762879285480688931763493239406757976048436785624579024287324291438651910344789488047853106653055212183616484650

- sunny-mittal

15

Python解释器会为您处理。您只需要执行操作（+、-、*、/），它就像正常一样工作。

int值是无限的。

在进行除法运算时要小心。默认情况下，商会转换为float，但是float不支持这么大的数字。如果您收到错误消息，指出float不支持这么大的数字，那么意味着商太大了，无法存储在float中，您将需要使用地板除法（//）。

忽略小数点后面的任何小数，这样结果将是int，因此您可以获得大数字结果。

>>>10//3
3

>>>10//4
2

- hedy

4

我的回答如何解决问题中的大量数字问题？ - StupidWolf

这意味着你可以像处理普通数字一样进行计算，但在除法运算时要小心。 - hedy

@Hedy 在除法运算中，我应该怎么做？我试图将(10^18 - 1)除以2，但结果不正确。它给出了一个约为5 * 10^17的数，而不是49999...99.5。我能做些什么来解决这个问题吗？我使用的是'/'除法。 - Robert F.

大数可能是圆周率中最多小数位的数字。 - yav dat

或者格雷厄姆数 - yav dat

1

为什么要这样做？如果您坚持将手牌存储为单个编码值而不是字典或列表，请使用位字符串代替质数的乘积。乘法和质数分解很慢。

将每张卡牌编码为2的幂次方（1、2、4、8、16等）。您可以使用hand |= card添加一张卡牌。您可以使用if hand & card > 0检查一张卡牌是否存在。

- Peter Theobald

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ben Blank · Accepted Answer

Python支持一种"bignum"大整数类型，可以处理任意大的数字。在Python 2.5+版本中，这个类型被称为long，与int类型分开，但解释器会自动使用其中更合适的类型。在Python 3.0+版本中，int类型已完全删除。

然而，这只是实现的细节 — 只要您拥有2.5或更高版本，执行标准数学运算时，任何超出32位数学范围的数字都会自动（且透明地）转换为bignum。

您可以在PEP 0237中找到所有详细信息。