如何在python中对此进行优化？
我想找到配对的数量，一个很大的数字。如果我给数字n，并要求确定配对的数量，这样
- <代码>S（x）
而constants是i
例如，假设数字是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.，问题就出现了我怎样才能优化，我试图搜索，但无法找到任何有效的解决方案。
共有3个答案
让我们暂时忽略第二个约束x
然后，一种策略是将所有具有相同数字总和的数字集中在一起。例如，如果你的 n 是 10^250，那么 s.o.d. 1000 将恰好出现 1983017386182586348981409609496904425087072829264027113757253089553808835917213113938681936684409793628116446312878275672807319027255318921532869897133614537254127444640190990014430819413778762187558412950294708704055125267388491053875845430856889 次，而 s.o.d. 10 将出现在313933899756954150 次。因此，这两个s.o.d.一起将产生这些数字的乘积，即622536381330141298432969991820256911356499404510841221727177771404498196898219200726905190334516036530761185604472351714146659153338691825580165670694714765688631611013643183449188160088364429780094383087473530152672586062700335444189441183499432858425871184639350对。
或者稍微少一些自大狂的数字：n=88，s. o. d.1=10，s. o. d.2=7，我们得到8和8，因此是64对。
下面的代码使用一个简单的逐位递归关系来实现这个策略（functionnonsod）。由于存在大量冗余分支，因此使用了缓存。
n的完整计数=10^250（仍不强制执行x
现在让我们回到约束二:x
我们可以通过分别在x和y的最左边的数字上进行条件反射来使用无约束代码。如果它们是相同的，我们可以将它们切掉并使用重复。否则，属于 x 的那个必须更小。在砍掉两者之后，我们基本上又回到了一个约束问题上。只需要一个额外的“宽限期”参数。例如，如果 x 的第一个数字比 y 的第一个数字小 3，则 x 的其余 s.o.d.s 可能比 y 大 2。
这个算法给出了67535的预期结果，10^250仍然是可行的（在我相当普通的笔记本电脑上2分钟）。结果：<代码>2598432876928289815621598707009376029783628175362674070663539302491878168392867045441700080080359016753562441860435526658122496959595959574112524315789160318453327454310549931452802202972740234656382974003670663786733595223855584565606250091432915144227765983937731644519405697849130924480596441949272675753063863819393113 30430481858629007849038014387295963595185191082258266151695431627559869068540412688085631222123413887008350968291853549694641333334284365470703250347001
import itertools as it
_cache_a = {}
_cache_b = {}
_max_k = 300*9 + 1 # good for up to 300 digits
def maxsod(n):
# find largest posssible sum of digits
return (len(n) - 1) * 9 + int(n[0]) + all(d == '9' for d in n[1:])
def nonsod_str(n, k):
# first anchor the recurrence and deal with some special cases
if k < 0:
return 0
elif k == 0:
return 1
elif n == '0':
return 0
elif len(n) == 1:
return int(k <= int(n))
max_k_n = maxsod(n)
if k >= max_k_n:
return 0
max_k_n = min(_max_k, max_k_n)
_cache_n = _cache_a.setdefault(int(n), max_k_n * [-1])
if _cache_n[k] < 0: # a miss
# remove leftmost digit and any zeros directly following
lead = int(n[0])
for j, d in enumerate(n[1:], 1):
if d != '0':
break
next_n = n[j:]
nines = (len(n) - 1) * '9'
_cache_n[k] = sum(nonsod_str(nines, k-j) for j in range(lead)) \
+ nonsod_str(next_n, k-lead)
return _cache_n[k]
def nonsod(n, k):
"number of numbers between 0 and n incl whose sum of digits equals k"
assert k < _max_k
return nonsod_str(str(n), k)
def count(n):
sods = [nonsod(n, k) for k in range(maxsod(str(n)))]
sum_ = sum(sods)
return (sum_*sum_ - sum(s*s for s in sods)) // 2
def mixed(n, m, grace):
nsods = [nonsod(n, k) for k in range(maxsod(str(n)))]
msods = ([nonsod(m, k) for k in range(maxsod(str(m)))]
if n != m else nsods.copy())
ps = it.accumulate(msods)
if len(msods)-grace < len(nsods):
delta = len(nsods) - len(msods) + grace
nsods[-1-delta:] = [sum(nsods[-1-delta:])]
return sum(x*y for x, y in zip(it.islice(ps, grace, None), nsods))
def two_constr(n):
if (n<10):
return (n * (n+1)) // 2
if not n in _cache_b:
n_str = str(n)
lead = int(n_str[0])
next_n = int(n_str[1:])
nines = 10**(len(n_str)-1) - 1
# first digit equal
fde = two_constr(next_n) + lead * two_constr(nines)
# first digit different, larger one at max
fddlm = sum(mixed(next_n, nines, grace) for grace in range(lead))
# first digit different, both below max
fddbbm = sum((lead-1-grace) * mixed(nines, nines, grace)
for grace in range(lead-1))
_cache_b[n] = fde + fddlm + fddbbm
return _cache_b[n]
匿名用户
预期的输出是有效对的数量，而不是所有有效对的列表。您可以通过简单的组合来计算这个数字，并且不需要检查所有可能性。
对于< code>n=3，对数将是< code>n=2的对数，格式为< code>(x，3)。x可以在<代码>范围内
代码可以使用递归或循环或公式，所有这些代码都应该计算机使用相同的数字，公式显然是最快的。
def countPairs(n):
if n == 1:
return 1 # pair (0,1)
return countPairs(n-1) + n
def countPairs(n):
ret = 0
for x in xrange(1,n):
ret+=x
return ret
def countPairs(n):
return n*(n-1)/2
注意：此答案不考虑约束（x
似乎没有必要实际生成货币对。这意味着不要存储和操作像（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：出现}，我们使它成为一个反向列表。对于 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
-
问题内容： 想象一下这个目录结构： 我正在编码，我需要从中导入一些东西。我该怎么办？ 我尝试过，但是得到了“未打包的相对导入尝试”。 我四处搜寻，但只发现骇客。有没有一种干净的方法？ 问题答案： 每个人似乎都想告诉你应该做什么，而不仅仅是回答问题。 问题是你通过将作为参数传递给解释器而将模块作为运行。 从PEP 328： 相对导入使用模块的属性来确定该模块在包层次结构中的位置。如果模块的名称不包含
-
GHC能否简化id=（\（a，b）- 更复杂的情况呢： GHC将简化映射到映射中？ 我试图使用简单的beta缩减，但由于糟糕的模式匹配，这些术语看起来是不可缩减的。 因此，我很好奇GHC的优化技术如何处理这个问题。
-
本文向大家介绍如何在Python对Excel进行读取，包括了如何在Python对Excel进行读取的使用技巧和注意事项，需要的朋友参考一下 在python自动化中，经常会遇到对数据文件的操作，比如添加多名员工，但是直接将员工数据写在python文件中，不但工作量大，要是以后再次遇到类似批量数据操作还会写在python文件中吗？ 应对这一问题，可以将数据写excel文件，针对excel 文件
-
问题内容： 在Python中scp文件的最pythonic方式是什么？我知道的唯一路线是 这是一种骇客，并且在类似Linux的系统之外不起作用，并且需要Pexpect模块的帮助来避免出现密码提示，除非你已经为远程主机设置了无密码的SSH。 我知道Twisted的，但是我希望避免通过低级ssh模块自己实现scp。 我知道，一个支持SSH和SFTP的Python模块；但它不支持SCP。 背景：我正在连
-
本文向大家介绍如何进行SQL优化？相关面试题，主要包含被问及如何进行SQL优化？时的应答技巧和注意事项，需要的朋友参考一下 （1）选择正确的存储引擎 MyISAM 适合于一些需要大量查询的应用，但其对于有大量写操作并不是很好。甚至你只是需要update一个字段，整个表都会被锁起来，而别的进程，就算是读进程都无法操作直到读操作完成。另外，MyISAM 对于 SELECT COUNT(*) 这类的计算
-
（这个问题与此密切相关，但它是一个更具体的问题，我希望能就此得到答案）