时间戳

首页 > 解决方案 > 如何优化此函数以返回给定范围内具有唯一数字（即无重复数字）的整数数？

python - 如何优化此函数以返回给定范围内具有唯一数字（即无重复数字）的整数数？

问题描述

给定两个整数的列表（即 [1,20] 或 [10,10000]），我正在尝试创建一个函数，该函数返回范围（包括）内没有重复数字的整数个数（即。 8、9、10 会计数，但 11 不会）。当输入列表相对较小时，我在这里编写的代码可以正常工作，但当范围很大时效率较低。我怎样才能使它更有效率？

good_numbers = 0

current_count = list[0]

while current_count <= list[1]:
    list_of_digits = [int(i) for i in str(current_count)]
    if len(list_of_digits) == len(set(list_of_digits)):
        good_numbers += 1
    current_count += 1

print(good_numbers)

当范围相对较小时，这可以正常工作，但是当范围很大时，我会收到超时错误。

标签： pythonpython-3.xoptimizationwhile-looplist-comprehension

解决方案

在不改变算法的情况下，这是一个简单的 ~3 倍加速

In [38]: def a(start, end): 
    ...:     g = 0 
    ...:     for i in range(start, end+1): 
    ...:         s = list(f"{i}") 
    ...:         if len(s) == len(set(s)): 
    ...:             g += 1 
    ...:     return g      
    ...:

结果：

New 
In [35]: %timeit a(10, 10000)                                                                   
12.1 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Yours :
In [37]: %timeit b([10, 10000])                                                                 
33.5 ms ± 402 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

编辑：

对于 überfaster 解决方案，您需要玩得更聪明一点。

例如：基本上你需要能够在开始和结束边界之间找到数字的排列。

假设你有 ne 边界。该操作将简单地计算 n 位、n -1 位、n - 2 位的排列数的总和......

例如，如果我有 3 位数字，那么我需要有 9 + (9 * 9) + (9 * 9 * 8) 的总和（试试我的或你的代码，边界为 1, 1000 :)

在哪里，

In [80]: %timeit 9 + 9 * 9 + 9 * 9 * 8                                                          
11.2 ns ± 0.13 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

您需要提出一种算法，例如

In [89]: from functools import reduce
In [90]: def c(start, end): 
    ...:     sl = len(list(f"{start}")) 
    ...:     el = len(list(f"{end}")) 
    ...:     t = 0 
    ...:     for i in range(sl, el): 
    ...:         t += reduce(lambda x, y: x * y, [9 - j for j in range(i - 1)], 9) 
    ...:     return t 

In [91]: %timeit c(10, 10000)                                                                   
7.93 µs ± 46.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

但这缺少对边界值的控制，您需要检查可能的值是否高于起点和低于终点。

如您所见，最后一个速度快 1400 倍：D 但缺少您需要应用的必要控件

推荐阅读