优化Python代码，计算从1到n中数字9的个数。

Question

def count_nines(n):
    x = list(map(str,range(n + 1)))
    count = 0
    for i in x:
        c = i.count('9')
        count += c 
    return count

执行超时（12000毫秒）

我该如何优化这段代码？

- ĽUBOŠ MOTOŠICKÝ

---

你首先将范围强制转换为字符串列表。不要那样做。正常使用for i in range(n):然后将此“i”转换为字符串。然后你可能想采用另一种方法。作为人类，您如何检查1到99之间有多少个九？您真的需要检查11、12、13等吗？还是可以想出更有效的方法？ - Sembei Norimaki

或者至少迭代map对象(for i in map(str,range(n + 1)))，这样你就不会生成一个大的字符串列表，而是逐个处理每个值。 - Yevhen Kuzmovych

你不需要优化这段代码。你需要基于完全不同的原则编写全新且无关的代码。 - n. m.

优化的第一件事情总是测量性能，因此您定义了一些要优化的基准。然后，您使用分析器找出代码的每个部分花费时间的位置，从而形成一个最有利于优化的想法。 - Ulrich Eckhardt

@UlrichEckhardt 然后意识到你的算法复杂度太高，根本不可能有一点点通过测试的希望，放弃这段代码，重新开始。这样做，你甚至不必知道什么是分析器或运行单个基准测试。 - n. m.

Answer 1

这是一些工作的代码（我在一些不太大的数字上进行了测试，并且它返回与您相同的结果），基于我的评论：

def count_nines(n):
    if n==0:
        return 0
    k = len(str(n))-1
    leading_digit, remainder = divmod(n, 10**k)  # Thanks @Stef for this optimization
    # Number of nines in numbers from 1 to leading_digit * 10**k - 1
    count1 = leading_digit * k*10**(k-1)
    # If the leading_digit is 9, number of times it appears
    # (in numbers from  9 * 10**k to n)
    count2 = remainder+1 if leading_digit==9 else 0
    # Number of nines in remainder
    count3 = count_nines(remainder)
    # Total number of nines
    return int(count1 + count2 + count3)

解释

• 首先，1-10^k 中数字 9 的数量（以下简称 c9()）为 k * 10^(k-1)。这很容易通过递归证明，但我将以一个例子来说明： 假设 c9(1000) = 300，则数字 0xxx、1xxx…9xxx 的 xxx 部分中数字 9 的数量等于 10 * 300；加上 9000 到 9999 中的 9 的数量为 1000（共 1000 个九），因此得到 c9(10000) = 10*300 + 1000 = 4000。

• 现在假设你想知道 c9(7935)：你有 7 * 300 个数字 9 在 1-7000 中，然后是 7 000 到 7 900 中的 9 * 20 个数字 9，接着是数字 900 到 935 中的 36 个前导数字 9，然后...

例子

count_nines(9254287593789050756)
Out[12]: 16880680640899572416

- Swifty

---

为了清晰的代码风格，我还会将 return int(leading_digit*k*10**(k-1) + (remainder+1 if leading_digit==9 else 0) + count_nines(remainder)) 替换为 self_explaining_name1 = leading_digit*k*10**(k-1); self_explaining_name2 = remainder+1 if leading_digit==9 else 0; self_explaining_name3 = count_nines(remainder); return self_explaining_name1 + self_explaining_name2 + self_explaining_name3。 - Stef

另外，我不明白为什么在返回语句中还需要调用 int( ... )，它们不已经是整型了吗？ - Stef

这是我一开始想的，但它返回了一个浮点数（我承认我没有调查过）；也许使用divmod就不再需要了。我会测试一下（并考虑像你建议的那样分段计算）。编辑：已经测试过了；没有int，它返回xxx.0。 - Swifty