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 桁の数まで数えなければならないため、コンピューターの処理速度が遅くなります。試してみたら、コンピューターがクラッシュしました。

ループを高速化する方法はありますか?

ありがとうございました！

score 2 · Accepted Answer

あなたはコンピューターに力を入れすぎていますね :) 何兆もの数字をそのように計算しています。

あなたのケースには xrange の方が適しているようです。

cow = xrange(1000, 10000)

score 1 · Accepted Answer

数が多い場合の最速の解決策は、個々の数をまったく調べないことです。合計が 39 になる 10 桁の数字の数を知りたい場合は、最初に、合計が 39 になる 10 桁の一意の組み合わせをすべて見つけます (そのうち 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 億 700 万の 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))

score 0 · Accepted Answer

まず、他の多くの回答が示しているように、を使用する必要がありますxrange。これは、ジェネレーターのように機能し、各番号を 1 つずつ提供し、多くのメモリを節約します。

いくつかの最適化を組み込むことで、アルゴリズムを改善することもできます。

整数の合計が指定された合計になる、指定された範囲内の最小数と最大数を確認します。

例 - あなたの数字は 4 と 18 です。すべての数字をチェックする代わりに、1089 から 9900 までのループを実行できます。
一致が見つかった場合、すぐ次の数字が一致することはありません (数字の合計が現在の数字よりも 1 多いか、現在の数字よりも 8、17...少ないため)。同様に、次から次へも使用できません...など、そのような番号を安全にスキップするパターンを見つけることができます（別の回答で同様の戦略が提案されています）
最初に、sum の入力が 9 未満であるかどうかなど、いくつかのエッジケースを確認できます。

例-あなたの数字は4（桁数）と5（桁の合計）です。次に、6、7、8、9 の数字を含むすべての数字を安全に除外できます。

python - Python の While ループの高速化

6 に答える 6

Related

Reference