如何尽可能快地计算一个整数的基3值，这个整数是一个巨大的十进制数字序列（超过一百万）？

Question

我们从教授那里得到了这个任务。先决条件是：

• 使用python3并且只使用内置函数（不使用numpy）。你知道吗
• 主要任务：在5秒内找到并存储结果。你知道吗
• 小任务，很好：不仅要找到基b=3的值，还要找到基b=3**k（k=2,3,4）的值。你知道吗

与我们的第一个直接解决方案相比，我们实现了96倍的改进（几乎快了100倍），但仍然没有达到5秒的限制（目前，我们在i7笔记本电脑上的时间是25秒）。[我们的教授也没有纯Python的解决方案，所以这是一项研究任务。]

完整的代码（包括测试调用）在这里：总的来说，它显示了从最初的2400秒（=40分钟）到25秒的改进。然而，我们需要另一个性能提高系数5。有没有人有想法可以帮忙？你知道吗

# -*- coding: utf-8 -*-
#
# Convert a long random sequence of base-10 digits to integers base 3**k with k=1,2,3,4
# 
# Task for phdgroupA: length of sequence is 1.5*(10**6)
#                     time < 5 sec
#                     Use Python 3 (standard libraries only, no numpy) !
#
# Testcase with a very small sequence, made purely of the digit 7:
# (see sagemath or www.math.com/tables/general/base_conv.htm)
# numlen = 12  -->  777777777777_base10
#                =  2202100120200002212221010_base3
#                =  2670520085833_base9
#                =  2k9fi2np3_base27   ("digits": 0123456789ab...pq)
#                   [2, 20, 9, 15, 18, 2, 23, 25, 3]
#                =  2[61]5[18]8[53][30]_base81
#                   [2, 61, 5, 18, 8, 53, 30]
# 


# 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 0: Create string of nlen digits
def step0(nlen):
    rd = 7  # which digit to repeat
    string_val = "".join(str(rd) for i in range(nlen))
    return string_val  # end of step0()


# Step 1: Convert string to int (the string contains only decimal digits)
def step1(string_val, option_chunk=True):
    if option_chunk == True:
        string_val_len = len(string_val)
        Chunk_len = 90000
        Read_len = 0
        int_valChunk = 0
        int_valLocal = 0
        ii = 0
        while Read_len < string_val_len:
            string_val_ChunkRead = string_val[ii*Chunk_len:(ii+1)*Chunk_len]
            Chunk_lenRead = len(string_val_ChunkRead)
            int_valChunk = int(string_val_ChunkRead)
            ii += 1
            int_valLocal = int_valLocal * 10**Chunk_lenRead + int_valChunk
            Read_len += Chunk_lenRead
        int_val = int_valLocal
    else:
        int_val = int(string_val)
    return int_val  # end of step1()


# Step 2: Convert given integer to another base
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)  # That's the 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)
    return nList  # end of step2()



if __name__ == '__main__':

    # Calculate the string of digits
    numlen = 1500000  # number of digits = length of sequence
    string_value = step0(numlen)

    # Calculate the integer value of the string_value
    int_value = step1(string_value, option_chunk=True)

    # Convert int_value to list of numbers of the given bases
    convsteps = 3  # value of '3' makes step2() 50-60 times faster than value '1'

    b = 3
    numList = step2(int_value, b, convsteps)
    print('3**1: numList begin:', numList[:10])  # Expect: [2, 0, 1, 0, 0, 1, 1, 0, 2, 1]

想法可能是，第一步中的块可以有另一个大小？或者中间转换的两大基础可以更好地平衡？或者可以更直接地将十进制数字串转换为基数为3的列表？你知道吗

说明：上述Python代码中的算法分3步工作：

• 第0步：获取数据。 为了测试的目的，我们在这里创建一个 长度为150万位的十进制数字。 这个值通常是我们从文件中随机得到的值。 然后将序列存储为字符串。你知道吗
• 步骤1：将该字符串转换为整数（默认值是以10为基数）。你知道吗
• 第2步：将该整数转换为以b=3为基数的整数。你知道吗

这三个变化导致了最大的改善（与最初的直接解决方案相比）：

1. 步骤2中使用的helper函数numberToBase（n，b）， 将整数n转换为以b为底的整数。结果是一个列表 以b为基数的十进制整数。以序列的形式读取列表 是基数b中的结果数。通过 使用内置函数“divmod”而不是两个命令n%b 在while循环中n//=b。这带来了 因素2。

2. 函数step2（n，b，convsteps）将给定的整数n转换为 基数b的整数（b=3）。最初，我们称之为 助手函数一次。然后，我们介绍了 第二步的中间步骤，所以n没有迁移到最后一步 一步到位，三步到位。中间碱含量较高 比最终的碱基b大。这些中间碱基的转换使步骤 2快得多：60倍。

3. 通过分块读取字符串并分别对每个垃圾进行转换，使函数step1的速度提高了4倍。

任何想法都欢迎。请用time（）测试你的想法，并给出一个关于它的优势的定量说明。我们在这里检查的其他答案没有使用这么长的十进制数字序列（在字符串中），或者没有关注基转换的性能。你知道吗

Answer 1

好吧，我想这就是解决办法

base3to9={
   "00":"0",
   "01":"1",
   "02":"2",
   "10":"3",
   "11":"4",
   "12":"5",
   "20":"6",
   "21":"7",
   "22":"8",   
}
def convert_base3_to_base9(s):
    s = '0'*(len(s)%2) + s # ensure that the string is the right length
    return "".join(base3to9[s[i:i+2]] for i in range(0,len(s),2))

print(convert_base3_to_base9("12012120121010"))
# 5176533

然后你可以推断出来

base3to27 = {
    "000":"0",
    "001":"1",
    ...
    "222":"Q"
}
def convert_base3_to_base27(s):
    s = '0'*(len(s)%3) + s # ensure that the string is the right length
    return "".join(base3to27[s[i:i+3]] for i in range(0,len(s),3))

基本上没有数学要做。。。只是O（1）dict查找。。。应该很快