python - 如何在 python 中优化它？

Question

我想找到一个大数对的数量。如果我给出数字 n 并要求确定，这样的对数

• S(x) < S(y) where S(k) denotes the sum of digits of integer k.
• 0 <= x < y <= n

约束是i <= n <= 10^250

例如，假设数字是 3因此有效对将是 (0,1)、(0,2)、(0,3)、(1,2)、(1,3) 和 (2,3)，因此它计数为 6。这就是答案。为此，我编写了代码:

#!/bin/python3

import sys
from itertools import permutations

def sumofelement(n):
    sum = 0
    while(n>0):
        temp = n%10
        sum = sum + temp
        n = n//10
    return sum

def validpair(x):
    x, y = x
    if sumofelement(x) < sumofelement(y):
        return True

def countPairs(n):
    z = [x for x in range(n+1)]
    permuation = permutations(z, 2)
    count = 0
    for i in permuation:
        print(i, validpair(i))
        if validpair(i):
            count += 1
    return count%(1000000007)

if __name__ == "__main__":
    n = int(input())
    result = countPairs(n)
    print(result)

但是当数字变化很大时就会出现问题，比如说 10^250。我该如何优化，我尝试搜索但无法找到任何有效的解决方案。

Answer 1

注意:这个答案没有考虑约束 (x<y)这是后来添加到问题中的。并且不接受任何像 10^250 这样的巨大输入.建议按要求改进OP的代码。

---

似乎没有必要实际生成对。这意味着不要存储和操作像 (1000, 900) 这样的元素。但直接是他们的数字总和:(1,9)

因此您可以对现有函数进行此修改:

def countPairs(n):
    z = [sumofelement(x) for x in range(n+1)]
    p = permutations(z, 2)
    count = 0
    for x,y in p:
        if (x<y):
            count += 1
    return count%(1000000007)

测试 n=2K

> time python3 test.py #old
1891992

real    0m15.967s
user    0m15.876s
sys     0m0.049s
> time python3 test2.py #new
1891992

real    0m0.767s
user    0m0.739s
sys     0m0.022s

对于 n=5K

11838575

real    1m32.159s
user    1m30.381s
sys     0m0.444s

11838575

real    0m4.280s
user    0m4.258s
sys     0m0.012s

虽然它快了 95%，但似乎是 O(n^2)

---

所以这是一种不同的方法:

from collections import Counter

def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def count_pairs(n):
    z = [sum_digits(x) for x in range(n+1)]
    c = Counter(z)
    final = sorted(c.items(), reverse=True)
    print(final)

    count = 0
    older = 0
    for k,v in final:
        count += older * v
        older += v
    return count

if __name__ == "__main__":
    n = int(input())
    print(count_pairs(n))

我们创建一个字典 { sum_of_digits: occurences }和我们使它成为一个反向列表。例如 n=10这将是

[(9, 1), (8, 1), (7, 1), (6, 1), (5, 1), (4, 1), (3, 1), (2, 1), (1, 2), (0, 1)]

当我们遍历它时，在任何节点，出现次数乘以先前节点的总和就是具有该数字总和的任何数字对总计数的贡献。它可能是 O(n)。与我们的实际数据相比，计数器大小很小。

测试 N=2K

[(28, 1), (27, 4), (26, 9), (25, 16), (24, 25), (23, 36), (22, 49), (21, 64), (20, 81), (19, 100), (18, 118), (17, 132), (16, 142), (15, 148), (14, 150), (13, 148), (12, 142), (11, 132), (10, 118), (9, 100), (8, 81), (7, 64), (6, 49), (5, 36), (4, 25), (3, 16), (2, 10), (1, 4), (0, 1)]
1891992

real    0m0.074s
user    0m0.060s
sys     0m0.014s

N=67535

[(41, 1), (40, 5), (39, 16), (38, 39), (37, 80), (36, 146), (35, 245), (34, 384), (33, 570), (32, 809), (31, 1103), (30, 1449), (29, 1839), (28, 2259), (27, 2692), (26, 3117), (25, 3510), (24, 3851), (23, 4119), (22, 4296), (21, 4370), (20, 4336), (19, 4198), (18, 3965), (17, 3652), (16, 3281), (15, 2873), (14, 2449), (13, 2030), (12, 1634), (11, 1275), (10, 962), (9, 700), (8, 490), (7, 329), (6, 210), (5, 126), (4, 70), (3, 35), (2, 15), (1, 5), (0, 1)]
2174358217

real    0m0.278s
user    0m0.264s
sys     0m0.014s