python - 加速 Python While 循环

Question

我有以下代码：

import math

print "Hey, lets solve Task 4 :)"

number1 = input ("How many digits do you want to look at? ")
number2 = input ("What would you like the digits to add up to? ")
final = []

if number1 == 1:
    cow = range(1,10)
elif number1 == 2:
    cow = range(10,100)
elif number1 == 3:
    cow = range(001,1000)
elif number1 == 4:
    cow = range(1000,10000)
elif number1 == 5:
    cow = range(10000,100000)
elif number1 == 6:
    cow = range(100000,1000000)
elif number1 == 7:
    cow = range(1000000,10000000)
elif number1 == 8:
    cow = range(10000000,100000000)
elif number1 == 9:
    cow = range(100000000,1000000000)
elif number1 == 10:
    cow = range(1000000000,10000000000)

number3 = cow[-1] + 1
number10 = number3
number8 = number3 - 1

if number1 == 1:
    test = range(1,number10)
elif number1 == 2:
    test = range(00,number10)
elif number1 == 3:
    test = range(000,number10)
elif number1 == 4:
    test = range(0000,number10)
elif number1 == 5:
    test = range(00000,number10)
elif number1 == 6:
    test = range(000000,number10)
elif number1 == 7:
    test = range(0000000,number10)
elif number1 == 8:
    test = range(00000000,number10)
elif number1 == 9:
    test = range(000000000,number10)
elif number1 == 10:
    test = range(0000000000,number10)

if number1 == 1:
    number7 = number8
elif number1 == 2:
    number7 = number8 + 1
elif number1 == 3:
    number7 = number8 + 1
elif number1 == 4:
    number7 = number8 + 1
elif number1 == 5:
    number7 = number8 + 1
elif number1 == 6:
    number7 = number8 + 1
elif number1 == 7:
    number7 = number8 + 1
elif number1 == 8:
    number7 = number8 + 1
elif number1 == 9:
    number7 = number8 + 1
elif number1 == 10:
    number7 = number8 + 1



n = 0
while n < number7:

    a = test[n]
    a = str(a)
    print a

    number4 = sum(int(x) for x in a)

    if number4 == number2:
        final.append(number4)

    n = n + 1



print len(final)

基本上，这段代码计算出有多少位数字包含整数，这些整数加起来等于某些数字。当它运行时，它会询问您想要多少位数（例如 4）以及您希望它们相加的数字。例如，您可以选择 4 和 18，它会计算从 1000 到 9999 的数字中有多少整数加起来为 18（例如 4545）。

问题是，最后一个问题问有多少个 10 位数字加起来是 39。使用这个代码，我的电脑会花很多时间，因为它必须从 1 一直数到最大的 10 位数字。当我尝试它时，它使我的电脑崩溃了！

有没有办法加快循环？

谢谢！

Answer 1

你把电脑推得太紧了，伙计 :) 像这样计算数万亿个数字。

看起来 xrange 更适合您的情况。

cow = xrange(1000, 10000)

Answer 2

import math

print "Hey, lets solve Task 4 :)"

number1, number2, answer = 4, 18, 0

for num in xrange(10 ** (number1 - 1), 10 ** number1):
    total = 0
    while num:
        total += num % 10
        num /= 10
    if total == number2: answer += 1

print answer

Answer 3

您似乎正在使用一些蛮力方法来执行此操作，您应该找到一种方法来跳过一些迭代。

例如，您选择 4 和 18 并且您在号码 1809 上：

1809 = 18  # match
1810 = 10
1811 = 11
1812 = 12

有一种模式，您需要对其进行优化以跳过一些迭代。

Answer 4

您的蛮力算法是指数级的，因此无论您如何实现它都会很慢。aIKid 的建议将帮助您避免内存泛滥，但仍然需要很长时间才能运行。

我会建议一种不同的增量算法：

number1 = 4
number2 = 18

options={}
for i in range(1,10):
    options[i]=1 # for single digit numbers there is one option for each target total

for _ in range(1,number1):
    new_options={}
    for i in range(0,10): # for each new digit we can add
        for option in options: # go through all the options
            cur_total=i+option
            if cur_total not in new_options:
                new_options[cur_total]=0
            new_options[cur_total]+=options[option] # and calc how many options this digit add for each target total
    options=new_options

print(options[number2])

Answer 5

当您有大量数字时，最快的解决方案根本不会查看单个数字。如果你想知道有多少个 10 位数字总和为 39，首先找到所有 10 位数字的唯一组合，总和为 39（其中 2630 个）。

您可以这样做的方法是针对每个数字d，找到 9 位数字的所有唯一组合，总和为 39-d，其中没有数字小于d。

def unique_combos(digits, total, smallest=0):
    if digits*9 < total or digits*smallest > total:
        return
    if digits==1:
        yield [total]
        return

    for i in range(smallest, 10):
        for combo in unique_combos(digits-1, total-i, i):
            yield [i]+combo

然后为每个独特的数字组合找出可以排列的方式。这只是简单的数学运算，只有您必须避免计算以前导零开头的任何数字。

import operator
from collections import Counter
from math import factorial
def npermutations(l):
    """From stackoverflow 16453188"""
    num = factorial(len(l))
    mults = Counter(l).values()
    den = reduce(operator.mul, (factorial(v) for v in mults), 1)
    return num / den

现在只需将每个组合的数字相加，您就会得到答案。鉴于我们不再担心速度，我只是减去了位数更少的数字。

def answer(digits, total):
    n_or_fewer = sum(npermutations(l) for l in unique_combos(digits, total))
    fewer = sum(npermutations(l) for l in unique_combos(digits-1, total))
    print("There are {} {}-digit numbers with digits summing to {}".format(
        n_or_fewer - fewer,
        digits, total))

if __name__=='__main__':
    answer(4,18)
    answer(10,39)

输出不到 1 秒：

C:\Temp>digitsum2.py
There are 615 4-digit numbers with digits summing to 18
There are 307100365 10-digit numbers with digits summing to 39

为了完整起见，Sudipta 建议优化您逐步浏览数字的方式。这里有一些代码可以做到这一点：它直接从一个数字转到下一个数字，并且对于 4 位数字得到相同的答案，但我仍然对运行 3.07 亿个 10 位数字感到厌烦。它可能会被优化很多，但是蛮力是错误的方法。

def smallest_sum(n, digits, first=1):
    """Find the smallest number with 'digits' digits that sum to 'n'
    Returns the value as a list of digits because that's what we need next anyway"""
    k = max(first,n + 9 - 9*digits)
    assert k <= 9, "Impossible values"
    if digits > 1:
            return [k]+smallest_sum(n-k, digits-1, 0)
    return [k]

def all_sums(digits):
    """Find the next string of digits with the same sum.
    We can do this by finding the last non-zero digit and decrementing it
    then incrementing the previous non-nine, and sorting any digits that
    follow it."""
    yield digits
    while True:
        was = list(digits)
        for i in range(len(digits)-1,-1,-1):
            if digits[i] != 0:
                decrement = i
                break
        else:
            return
        for i in range(decrement-1,-1,-1):
            if digits[i] != 9:
                increment = i
                break
        else:
            return
        digits[decrement] -= 1
        digits[increment] += 1
        if increment < len(digits)-2:
            digits[increment+1:] = digits[increment+1:][::-1]
        assert digits > was
        yield digits

def count(num_digits, total):
    try:
        digits = smallest_sum(total, num_digits)
    except AssertionError:
        return 0
    return sum(1 for _ in all_sums(digits))

if __name__=='__main__':
    print(count(4,18))
    print(count(10,39))

Answer 6

首先，正如许多其他答案所表明的那样：您需要使用xrange，它就像一个生成器，一个一个地为您提供每个数字并节省大量内存。

您还可以通过合并一些优化来改进您的算法：

1. 检查给定范围内的最小和最大数字，其整数加起来等于给定的总和。

   示例 - 您的数字是 4 和 18。您可以运行 1089 到 9900 的循环，而不是检查所有数字。

2. 如果并且当您找到匹配项时，下一个数字永远不会是匹配项（因为它的数字总和将比当前数字多 1，或者比当前数字少 8,17...）。同样，即使 next to next 也不能​​使用...等等，您可以找到一种安全地跳过此类数字的模式 （在另一个答案中提出了类似的策略）

3. 一开始，您可以检查一些边缘情况，例如 sum 的输入是否小于 9。

   示例-您的数字是 4（位数）和 5（位数）。然后我们可以安全地排除所有数字为 6、7、8、9 的数字。