我们有一个像 (10**1500000)+1 这样的大数,想把它转换成 3 进制。 下面是我们用普通 Python 发现的最快方式运行代码(不使用 numpy 或 CAS 库)。
如何提高碱基转换(到基数 3)的性能?
我们想知道如何通过以下两种方式做到这一点:
- 仅使用 Python 3 的内置函数(没有 numpy)?
- 在普通 Python 3 程序中使用 numpy(或其他 CAS 库)?
非常欢迎任何帮助。这是我们当前的代码:
#### --- Convert a huge integer to base 3 --- ####
# Convert decimal number n to a sequence of list elements
# with integer values in the range 0 to base-1.
# With divmod, it's ca. 1/3 faster than using n%b and then n//=b.
def numberToBase(n, b):
digits = []
while n:
n, rem = divmod(n, b)
digits.append(rem)
return digits[::-1]
# Step 2: Convert given integer to another base
# With convsteps == 3, it's about 50-100 times faster than
# with with convsteps == 1, where numberToBase() is called only once.
def step2(n, b, convsteps):
nList = []
if convsteps == 3: # Here the conversion is done in 3 steps
expos = 10000, 300
base_a = b ** expos[0]
base_b = b ** expos[1]
nList1 = numberToBase(n, base_a) # time killer in this part
nList2 = [numberToBase(ll, base_b) for ll in nList1]
nList3 = [numberToBase(mm, b) for ll in nList2 for mm in ll]
nList = [mm for ll in nList3 for mm in ll]
else: # Do conversion in one bulk
nList = numberToBase(n, b) # that's the time killer in this part
return nList
if __name__ == '__main__':
int_value = (10**1500000)+1 # sample huge numbers
# expected begin: [2, 2, 0, 1, 1, 1, 1, 0, 2, 0]
# expected time: 4 min with convsteps=3
base = 3
# Convert int_value to list of numbers of given base
# -- two variants of step2() using different convsteps params
numList = step2(int_value, base, convsteps=1)
print(' 3-1: numList begin:', numList[:10])
# A value of '3' for the parameter "convsteps" makes
# step2() much faster than a value of '1'
numList = step2(int_value, base, convsteps=3)
print(' 3-3: numList begin:', numList[:10])
在How to calculate as quick as possible the base 3 value of an integer which is given as a huge sequence of decimal digits (more than one million)? 是一个类似的问题,在基本转换之前还有一些步骤。在这里的这个问题中,我们专注于那部分,它占用了大部分时间,而且我们还没有得到答案。
也在 Convert a base 10 number to a base 3 number 中, HUGE numbers 的性能方面没有处理。
最佳答案
这是一个扩展您的convsteps
解决方案的方法,它通过在每次调用时使用基本平方进行递归。需要一些额外的工作来删除前导零。
def number_to_base(n, b):
if n < b:
return [n]
else:
digits = [d for x in number_to_base(n, b*b) for d in divmod(x, b)]
return digits if digits[0] else digits[1:]
我的快速计时测试表明它与您的 step2
相同,但在误差范围内。但它更简单,错误可能更少。
关于python - 使用 Python 3 快速计算实数的基数 3 值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53642569/