Singpath Python错误。“您的代码花了太长时间才返回。“

Question

我在玩弄SingpathPython练习题。遇到了一个简单的问题，问题如下：

Given an input of a list of numbers and a high number, 
return the number of multiples 
of each of those numbers that are less than the maximum number. 
For this case the list will contain a maximum of 3 numbers 
that are all relatively prime to each other.

我写了一个简单的程序，运行得非常好：

"""
 Given an input of a list of numbers and a high number, 
 return the number of multiples 
 of each of those numbers that are less than the maximum number. 
 For this case the list will contain a maximum of 3 numbers 
 that are all relatively prime to each other.

>>> countMultiples([3],30)
9
>>> countMultiples([3,5],100)
46
>>> countMultiples([3,5,7],30)
16
"""

def countMultiples(l, max):
    j = []
    for num in l:
        i = 1
        count = 0
        while num * i < max:
            if num * i not in j:
                j.append(num * i)
            i += 1
    return len(j)


print countMultiples([3],30)
print countMultiples([3,5],100)
print countMultiples([3, 5, 7],30)

但是当我尝试在SingPath上运行同样的程序时，它给了我这个错误

Your code took too long to return. 
Your solution may be stuck in an infinite loop. Please try again.

有没有人遇到过与Singpath相同的问题？你知道吗

Answer 1

我怀疑你所犯的错误和它说的一模一样。对于测试程序提供给您函数的某些输入，返回的时间太长。我自己对singpath一无所知，所以我不知道那可能需要多长时间。但我猜如果你使用最好的算法，他们会给你足够的时间来解决问题。你知道吗

如果您传入一个非常大的max值，您自己就会发现您的代码很慢。尝试将10000作为max传递，结果可能会等待一两分钟。你知道吗

在这种情况下，代码运行缓慢有几个原因。第一个是你有一个list到目前为止你已经找到的每一个倍数，你正在搜索列表，看看是否已经看到了最新的值。每次搜索所花费的时间与列表的长度成正比，因此对于整个函数的运行，它所花费的时间是二次的（相对于结果值）。你知道吗

通过使用set而不是list，您可以在这方面做很多改进。您可以测试一个对象是否在set（摊销）的固定时间内。但是，如果j是一个集合，那么在添加之前实际上不需要测试值是否已经在其中，因为set无论如何都会忽略重复的值。这意味着您可以将一个值add添加到集合中，而不必关心它是否已经存在。你知道吗

def countMultiples(l, max):
    j = set()                    # use a set object, rather than a list
    for num in l:
        i = 1
        count = 0
        while num * i < max:
            j.add(num*i)         # add items to the set unconditionally
            i += 1
    return len(j)                # duplicate values are ignored, and won't be counted

这比原始代码运行的速度要快得多，一百万或更多的max值将在不太合理的时间内返回。但如果你尝试更大的值（比如说1亿或10亿），你最终还是会遇到麻烦。这是因为您的代码使用循环来查找所有倍数，这需要线性时间（相对于结果值）。幸运的是，有一个更好的算法。你知道吗

（如果你想自己找出更好的方法，你可能不想在这里读了。）

更好的方法是使用除法计算每个值相乘多少次，得到一个小于max的值。严格小于max的num的倍数是(max-1) // num（这个-1是因为我们不想计算max本身）。整数除法比循环快得多！你知道吗

不过，还有一个额外的复杂性。如果你除以得到倍数，实际上你没有倍数本身来放入一个set像我们上面做的那样。这意味着，任何整数如果是一个以上输入数字的倍数，就会被计算多次。你知道吗

幸运的是，有一个很好的方法来解决这个问题。我们只需要计算有多少整数被过度计算，然后从总数中减去。当我们有两个输入值时，我们将对每个整数进行双重计数，这些整数是它们的最小公倍数的倍数（因为我们保证它们是相对素数，所以意味着它们的乘积）。你知道吗

如果我们有三个值，我们可以对每一对数字做同样的减法。但这也不完全正确。所有三个输入数的倍数的整数将被计数三次，然后再减去三次（因为它们是每对值的LCM的倍数）。所以我们需要添加一个最终值，以确保这三个值的倍数正好包含在最终和中一次。你知道吗

import itertools

def countMultiples(numbers, max):
    count = 0
    for i, num in enumerate(numbers):
        count += (max-1) // num       # count multiples of num that are less than max
    for a, b in itertools.combinations(numbers, 2):
        count -= (max-1) // (a*b)     # remove double counted numbers
    if len(numbers) == 3:
        a, b, c = numbers
        count += (max-1) // (a*b*c)   # add the vals that were removed too many times
    return count

对于max的任何值，都应该以类似于常数时间的方式运行。你知道吗

现在，对于给定的问题，这可能与您需要的效率一样高（它的值始终不超过三个）。但是，如果您想要一个能够处理更多输入值的解决方案，您可以编写一个通用版本。它使用与上一个版本相同的算法，并使用itertools.combinations更多的方法一次获得不同数量的输入值。奇数值的LCM的乘积数被加到计数中，而偶数值的LCM的乘积数被减去。

import itertools
from functools import reduce
from operator import mul

def lcm(nums):
    return reduce(mul, nums)   # this is only correct if nums are all relatively prime

def countMultiples(numbers, max):
    count = 0
    for n in range(len(numbers)):
        for nums in itertools.combinations(numbers, n+1):
            count += (-1)**n * (max-1) // lcm(nums)
    return count

下面是这个版本的输出示例，它的计算速度非常快：

>>> countMultiples([2,3,5,7,11,13,17], 100000000000000)
81947464300342