在 python 中使用嵌套循环时提高性能的任何提示

Question

所以，我做了这个练习，我会收到一个整数列表，并且必须找出有多少对和是 60 的倍数

示例：

输入：list01 = [10,90,50,40,30]

结果 = 2

解释：10 + 50、90 + 30

示例 2：

输入：list02 = [60,60,60]

结果 = 3

解释：list02[0] + list02[1], list02[0] + list02[2], list02[1] + list02[2]

看起来很简单，所以这是我的代码：

def getPairCount(numbers):
    total = 0
    cont = 0
    for n in numbers:
        cont+=1
        for n2 in numbers[cont:]:
            if (n + n2) % 60 == 0:
                total += 1
    return total

它正在工作，但是，对于超过 100k+ 个数字的大输入来说运行花费的时间太长，我需要能够在 8 秒内运行，关于如何解决这个问题??

使用我不知道的另一个库或者能够在没有嵌套循环的情况下解决这个问题

Answer 1

这是一个应该非常快的简单解决方案（它在 O(n) 时间内运行s）。它利用了以下观察结果：我们只关心每个值 mod 60。 23和143实际上是一样的。

因此，我们不是对列表进行 O(n**2) 嵌套传递，而是计算我们拥有的每个值的数量，mod 60，因此我们计算的每个值都在范围内0 - 59.

一旦我们有了计数，我们就可以考虑总和为 0 或 60 的对。有效的对是：

0 + 0
1 + 59
2 + 58
...
29 + 31
30 + 30

在此之后，顺序颠倒了，但我们只想每对数一次。

值相同的情况有两种： 0 + 0 和 30 + 30。对于其中的每一个，数字对是 (count * (count - 1)) // 2。注意这在计数为 0 或 1 时有效，因为在这两种情况下我们乘以零。

如果两个值不同，则 cases 只是他们计数的产物。

代码如下：

def getPairCount(numbers):
    # Count how many of each value we have, mod 60

    count_list = [0] * 60
    for n in numbers:
        n2 = n % 60
        count_list[n2] += 1

    # Now find the total

    total = 0

    c0 = count_list[0]
    c30 = count_list[30]

    total += (c0 * (c0 - 1)) // 2
    total += (c30 * (c30 - 1)) // 2

    for i in range(1, 30):
        j = 60 - i
        total += count_list[i] * count_list[j]

    return total

这运行秒在 O(n) 时间内，由于初始的一次性传递，我们修改了输入值列表。最后的循环只是从 1 迭代到 29 并且没有嵌套，所以它应该运行几乎立即。

Answer 2

以下是 Tom Karzes 的回答的翻译，但使用的是 numpy。我对它进行了基准测试，只有当输入已经是一个 numpy 数组而不是列表时它才会更快。我仍然想把它写在这里，因为它很好地展示了 python 中的循环如何成为 numpy 中的单行代码。

def get_pairs_count(numbers, /):

    # Count how many of each value we have, modulo 60.
    numbers_mod60 = np.mod(numbers, 60)
    _, counts = np.unique(numbers_mod60, return_counts=True)

    # Now find the total.
    total = 0   
    c0 = counts[0]
    c30 = counts[30]
    total += (c0 * (c0 - 1)) // 2
    total += (c30 * (c30 - 1)) // 2
    total += np.dot(counts[1:30:+1], counts[59:30:-1]) # Notice the slicing indices used.
    return total

在 python 中使用嵌套循环时提高性能的任何提示

any tip to improve performance when using nested loops with python

python

performance

nested-loops