python - 如何进一步优化计算所有交叉和？

Question

昨天我有一些空闲时间，不知何故想到了计算交叉和。我的目标是计算给定数字 n 以内的所有总和。不要问为什么 - 这只是为了好玩和学习东西。所以对于 n = 11，我希望我的结果看起来像这样:[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

这是我的代码:

def dynamicCheckSumList(upperLimit):
    dynamicChecksumList = []
    for i in range(0, 10):
        dynamicChecksumList.append(i)
    for i in range(10, upperLimit+1):
        length = getIntegerPlaces(i)
        size = 10**(length-1)
        firstNumber = i // size
        ancestor = i-(firstNumber*size)
        newChecksum = firstNumber + dynamicChecksumList[ancestor]
        dynamicChecksumList.append(newChecksum)
    return dynamicChecksumList

首先，我创建了一个空列表，然后用数字 0-9 各自的微不足道的总和填充了这些数字。然后我查看 9 以上的所有数字，直到上限。得到他们的长度。然后我继续找出数字的第一位数字。之后我计算没有前导数字的数字。例如:如果我的 i 是 5432，我将得到 432。因为我已经保存了 432 的交叉和，所以我可以将该交叉和添加到我的前导数字，我基本上完成了。

def getIntegerPlaces(theNumber):
    if theNumber <= 999999999999997:
        return int(math.log10(theNumber)) + 1
    else:
        counter = 15
        while theNumber >= 10**counter:
            counter += 1
        return counter

第二个函数是我在询问如何计算给定数字中的位数的问题时在这里找到的。

这里有什么方法(我想会有)来加快速度吗？还感谢有关如何节省内存的提示。只是为了好玩，我试图将 n 设置为 10 亿。我的内存 (16GB) 有点爆炸了 ;)

Answer 1

def digitSums2(n):
    n = (n + 9) // 10 * 10 # round up to a multiple of 10
    result = bytearray(range(10))
    for decade in range(1, n//10):
        r_decade = result[decade]
        for digit in range(10):
            result.append(r_decade + digit)
    return result

主要有两个区别:

• bytearray 每个计算值使用一个字节，这样可以节省大量内存。它只允许最多 255 个数字，但对于少于 26 位的数字就足够了。
• 剥最后一个数字比剥第一个数字容易得多。

这在 python 中应该尽可能快。打印结果时要小心，因为它可能比计算本身花费更多的时间(特别是如果你做内存中的副本)。