如何在合理的时间内将绝对大量的数字转换为字符串？

Question

这是我所知道的一个奇怪的问题,但我正在尝试获取文件中当前最大素数的副本.以整数形式获取数字非常简单.我跑了这个.

prime = 2**74207281 - 1

它需要大约半秒钟,它工作得很好.操作也相当快.将它除以10(不带小数)来移动数字很快.但是,str(prime)需要很长时间.我str像这样重新实现,发现它每秒处理大约一百个数字.

while prime > 0:
    strprime += str(prime%10)
    prime //= 10

有没有办法更有效地做到这一点？我在Python中这样做.我是否应该尝试使用Python,或者有更好的工具吗？

Answer 1

由于Python字符串是不可变的,因此重复的字符串连接是非常低效的.我会去的

strprime = str(prime)

在我的基准测试中,这始终是最快的解决方案.这是我的小基准程序:

import decimal

def f1(x):
    ''' Definition by OP '''
    strprime = ""
    while x > 0:
        strprime += str(x%10)
        x //= 10
    return strprime

def digits(x):
    while x > 0:
        yield x % 10
        x //= 10

def f2(x):
    ''' Using string.join() to avoid repeated string concatenation '''
    return "".join((chr(48 + d) for d in digits(x)))

def f3(x):
    ''' Plain str() '''
    return str(x)

def f4(x):
    ''' Using Decimal class'''
    return decimal.Decimal(x).to_eng_string()

x = 2**100

if __name__ == '__main__':
    import timeit
    for i in range(1,5):
        funcName = "f" + str(i)
        print(funcName+ ": " + str(timeit.timeit(funcName + "(x)", setup="from __main__ import " + funcName + ", x")))

对我来说,这打印(使用Python 2.7.10):

f1: 15.3430171013
f2: 20.8928260803
f3: 0.310356140137
f4: 2.80087995529

Answer 2

Python的整数到字符串转换算法使用简单的算法,运行O(n**2).随着数字的长度加倍,转换时间翻了两番.

我的计算机上的一些简单测试显示运行时间增加:

$ time py35 -c "n=str(2**1000000)"
user    0m1.808s
$ time py35 -c "n=str(2**2000000)"
user    0m7.128s
$ time py35 -c "n=str(2**4000000)"
user    0m28.444s
$ time py35 -c "n=str(2**8000000)"
user    1m54.164s

由于实际指数大约是我上一次测试值的10倍,因此它应该花费大约100倍的时间.或者只需3个多小时.

可以更快地完成吗？是.有几种方法更快.

方法1

将非常大的数字除以10的幂可以更快地分成两个大致相等但数量更小的数字.重复该过程直到数字相对较小.然后str()在每个数字上使用,并且前导零用于将结果填充到与最后10次幂相同的长度.然后连接字符串以形成最终结果.mpmath库使用此方法,文档暗示它应该快3倍.

方法2

Python的整数以二进制格式存储.二进制非常适合计算,但二进制到十进制转换是瓶颈.可以定义自己的整数类型,以100(或某些类似值)的十进制数字为单位存储值.操作(取幂,乘法,除法)将变慢,但转换为字符串将非常快.

许多年前,我实现了这样一个类,并使用高效的算法进行乘法和除法.代码在Internet上不再可用,但我确实找到了我测试的备份副本.运行时间缩短至约14秒.

更新

我更新了上面引用的DecInt代码,现在可以在https://github.com/casevh/DecInt上找到它.

如果使用Python的本机整数类型,则计算机上的总运行时间少于14秒.如果gmpy2使用整数类型,则运行时间约为3.5秒.

$ py35 DecInt.py
Calculating 2^74207281
Exponentiation time: 3.236
Conversion to decimal format: 0.304
Total elapsed time: 3.540
Length of result: 22338618 digits

方法3

我维护gmpy2库,可以轻松访问GMP库以进行快速整数运算.GMP在高度优化的C和汇编代码中实现方法1,并在~5秒内计算素数和字符串表示.

方法4

decimalPython中的模块将值存储为十进制数字.Python 3的最新版本包括十进制库的C实现,比Python 2的纯Python实现要快得多.C实现在我的计算机上运行3秒多一点.

from decimal import *
getcontext().prec = 23000000
getcontext().Emin = -999999999
getcontext().Emax = 999999999
x=Decimal(2)**74207281 - 1
s=str(x)

Answer 3

使用WinGhci(Haskell语言)输出文件大约需要32秒:

import System.IO

main = writeFile "prime.txt" (show (2^74207281 - 1))

该文件是21兆字节; 最后四位数,6351.