Python中的大整数输出缓慢

Question

有没有办法提高在Python中使用“str(bigint)”和“print bigint”的性能？打印大整数值需要花费很多时间。我尝试使用以下递归技术：

def p(x,n):
    if n < 10:
            sys.stdout.write(str(x))
            return
    n >>= 1
    l = 10**n
    k = x/l
    p(k,n)
    p(x-k*l,n)

n = 数字的位数，

x = 大整数

但是这个方法在某些情况下会失败，比如在子调用中，x 有前导零。有没有其他替代方案或者更快的方法？（请不要建议使用任何外部模块或库）。

Answer 1

对于互动应用来说，内置的 print 和 str 函数运行得非常快。

>>> print(2435**356)
392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625
>>> str(2435**356)
'392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625'

不过，如果你要打印很大的整数（比如输出到标准输出），让其他程序能够读取这些数据（从标准输入），而你发现把二进制转换成十进制的过程影响了整体性能，那么你可以看看这个链接：有没有更快的方法把一个任意大的整数转换成大端字节序列？（虽然接受的答案建议使用numpy，这是一个外部库，但还有其他的建议）。

Answer 2

把一个Python中的整数转换成字符串的过程，时间复杂度是O(n^2)，这里的n是数字的长度。对于特别大的数字，这个过程会很慢。比如说，对于一个有1,000,001位的数字，我的电脑上用str()函数大约需要24秒。

如果你真的需要把非常大的数字转换成字符串，你的递归算法是个不错的选择。

下面这个版本的递归代码应该能正常工作：

def p(x,n=0):
    if n == 0:
        n = int(x.bit_length() * 0.3)
    if n < 100:
        return str(x)
    n >>= 1
    l = 10**n
    a,b = divmod(x, l)
    upper = p(a,n)
    lower = p(b,n).rjust(n, "0")
    return upper + lower

它会自动估算输出中数字的位数。对于一个有1,000,001位的数字，这个方法大约快了4倍。

如果你想要更快的速度，可能需要使用一些外部库。