如何进一步优化计算所有十字和？

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内存似乎爆炸了;)

- doofesohr

---

你如何称呼十字和？ - user1196549

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中，这应该尽可能快。请小心打印结果，因为它可能比计算本身需要更多的时间（特别是如果您进行内存复制）。

- zch