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

问题描述

我知道这是一个很奇怪的问题，但是我正在尝试获取文件中当前最大质数的副本.以整数形式获取数字非常容易.我只是运行这个.

This is quite an odd problem I know, but I'm trying to get a copy of the current largest prime number in a file. Getting the number in integer form is fairly easy. I just run this.

prime = 2**74207281 - 1

大约需要半秒钟，并且效果很好.操作也相当快.将其除以10(不带小数)即可快速移动数字.但是，str(prime)需要很长时间.我像这样重新实现str，发现它每秒处理大约一百位数.

It takes about half a second and it works just fine. Operations are fairly quick as well. Dividing it by 10 (without decimals) to shift the digits is quick. However, str(prime) is taking a very long time. I reimplemented str like this, and found it was processing about a hundred or so digits per second.

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

有没有一种方法可以更有效地做到这一点?我在Python中执行此操作.我应该使用Python还是尝试一下，还是有更好的工具?

Is there a way to do this more efficiently? I'm doing this in Python. Should I even try this with Python, or is there a better tool for this?

推荐答案

由于Python字符串是不可变的，因此重复的字符串连接效率极低.我会去

Repeated string concatenation is notoriously inefficient since Python strings are immutable. I would go for

strprime = str(prime)

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

In my benchmarks, this is consistently the fastest solution. Here's my little benchmark program:

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):

For me, this prints (using Python 2.7.10):

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

这篇关于如何在合理的时间内将绝对大数转换为字符串?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！