string - 在合理的时间内,python 如何将绝对大量的数字转换为字符串?

  显示原文与译文双语对照的内容
89 4

我知道这是一个奇怪的问题,但是我正在试图在文件中获得当前最大的素数。以整数形式获取数字是相当容易的。我只是运行这个。

prime = 2**74207281 - 1

花了大约半秒钟的时间,而且效果很好。操作也相当快。将它除以 10 ( 不带小数) 以快速移动数字。但是 str(prime) 花了很长时间。像这样重新实现 str,发现它每秒处理的数字是a 左右。

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

是否有一种更有效的方法?我在 python 里做这个。我应该用 python 试试这个,还是有更好的工具?

时间:原作者:0个回答

92 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
原作者:
103 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

用power-of-10将非常大的数字分割成两个大致相等但更小的数字。这个过程不断重复,直到数字相对较小。然后使用 str() 在每个数字上,前导零用于将结果与最后一个power-of-10的长度相同。然后连接字符串以形成最终结果。这个方法被 mpmath 库使用,文档意味着它应该比 3x 快。

方法 2

python的整数以二进制格式存储。二进制对于计算非常有用,但binary-to-decimal转换是瓶颈。可以定义自己的整数类型,以 100个( 或者一些类似的值) 十进制数字存储值。操作( 幂,乘法,除法) 会比较慢,但是转换到字符串会非常快。

很多年前,我实现了这样一个类,并使用了高效的乘法和除法算法。代码在互联网上不再可用,但我确实找到了我测试过的备份副本。运行时间缩短到 ~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 for库,为快速整数算法提供对GMP库的容易访问。GMP在高度优化的C 和汇编代码中实现方法 1,并在 ~5 秒内计算素数和字符串表示。

方法 4

python 中的decimal 模块将值存储为十进制数。最近版本 python 3包含一个十进制库的C 实现,它比纯python实现包含 python 2要快得多。C 实现在我的电脑上运行超过 3秒。

from decimal import *
getcontext().prec = 23000000
getcontext().Emin = -999999999
getcontext().Emax = 999999999
x=Decimal(2)**74207281 - 1
s=str(x)
原作者:
79 5

使用 WinGhci ( Haskell语言) 输出文件所用的时间大约 32秒:

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

文件为 21兆字节;最后4 位数字 6351.

原作者:
...