关于从函数中删除嵌套 for 循环的指南

Question

我正在尝试编写最快的算法 return "magic triples" 的数量（即 x、y、z，其中 z 是 y 的倍数，y 是 x 的倍数) 在 3-2000 个整数的列表中。

(注意：我相信该列表应该是排序的并且是唯一的，但给出的测试示例之一是 [1,1,1]，预期结果为 1 - 虽然这是挑战本身的错误因为魔法三元组的定义被明确标记为 x < y < z，而 [1,1,1] 不是。无论如何，我试图优化一个算法以用于唯一整数的排序列表。）

我一直无法找到不包含三个连续循环的解决方案，因此是 O(n^3)。我在网上看到一个 O(n^2) 的，但我无法理解它在做什么，所以提交它感觉不对。

我的代码是：

def solution(l):
    if len(l) < 3:
        return 0
    elif l == [1,1,1]:
        return 1
    else:
        halfway = int(l[-1]/2)
        quarterway = int(halfway/2)
        quarterIndex = 0
        halfIndex = 0
        for i in range(len(l)):
          if l[i] >= quarterway:
            quarterIndex = i
            break
        for i in range(len(l)):
          if l[i] >= halfway:
            halfIndex = i
            break
        triples = 0
        for i in l[:quarterIndex+1]:
            for j in l[:halfIndex+1]:
                if j != i and j % i == 0:
                    multiple = 2
                    while (j * multiple) <= l[-1]:
                        if j * multiple in l:
                            triples += 1
                        multiple += 1
    return triples

我花了很多时间手动查看示例并删除列表中不必要部分的循环，但这仍然在大约一秒钟内完成了一个包含 2,000 个整数的列表，其中 O(n^2) 解决方案 I found 在 0.6 秒内完成相同的列表 - 看起来差别很小，但显然这意味着我的时间要长 60%。

我是否遗漏了一种非常明显的删除循环的方法？

另外，我看到有人提到制作有向图，我看到了其中的前景。我可以使用内置函数从原始列表中创建第一个节点的列表，所以原则上我认为这意味着我可以使用两个 for 循环创建整个图，然后 return 第三个节点列表的长度，但我也碰壁了。没有第三个循环，我似乎无法取得进展！！

Answer 1

from array import array

def num_triples(l):
    n = len(l)
    pairs = set()
    lower_counts = array("I", (0 for _ in range(n)))
    upper_counts = lower_counts[:]
    for i in range(n - 1):
        lower = l[i]
        for j in range(i + 1, n):
            upper = l[j]
            if upper % lower == 0:
                lower_counts[i] += 1
                upper_counts[j] += 1        
    return sum(nx * nz for nz, nx in zip(lower_counts, upper_counts))

这里，lower_counts[i]是第i个数是y的对数，z是对中的另一个数（即此 y).

的不同 z 值的数量

同理，upper_counts[i]是第i个数是y的对数，x是对中的另一个数（即此 y).

的不同 x 值的数量

所以第 i 个数字是 y 值的三元组的数量就是这两个数字的乘积。

这里使用数组存储计数是为了访问时间的可伸缩性。测试表明，直到 n=2000 它在实践中产生的差异可以忽略不计，甚至直到 n=20000 它只对运行时间产生大约 1% 的差异（与使用列表相比），但它可以principle 是非常大的 n 增长最快的术语。

Answer 2

如何使用 itertools.combinations 而不是嵌套 for 循环？结合列表理解，它更干净、更快。假设 l = [您的整数列表] 并假设它已经排序。

from itertools import combinations

def div(i,j,k): # this function has the logic
    return l[k]%l[j]==l[j]%l[i]==0

r = sum([div(i,j,k) for i,j,k in combinations(range(len(l)),3) if i<j<k])

Answer 3

@alaniwi 提供了一个非常聪明的迭代解决方案。

这是一个递归的解决方案。

def find_magicals(lst, nplet):
    """Find the number of magical n-plets in a given lst"""
    res = 0
    for i, base in enumerate(lst):
        # find all the multiples of current base
        multiples = [num for num in lst[i + 1:] if not num % base]
        res += len(multiples) if nplet <= 2 else find_magicals(multiples, nplet - 1)
    return res


def solution(lst):
    return find_magicals(lst, 3)

问题可以分解为选择原列表中的任意一个数作为基数（即x），在比基数大的数中，我们可以找到多少个du-plets。由于查找所有二元组的方法与查找三元组的方法相同，因此我们可以递归地解决问题。

根据我的测试，此递归解决方案与迭代解决方案相当，如果不是更高效的话。

Answer 4

这个答案是@alaniwi 提出的第一个建议，也是我发现最快的一个（2,000 个整数列表只需 0.59 秒）。

def solution(l):
    n = len(l)
    lower_counts = dict((val, 0) for val in l)
    upper_counts = lower_counts.copy()
    for i in range(n - 1):
        lower = l[i]
        for j in range(i + 1, n):
            upper = l[j]
            if upper % lower == 0:
                lower_counts[lower] += 1
                upper_counts[upper] += 1        

    return sum((lower_counts[y] * upper_counts[y] for y in l))

我想我已经设法解决了这个问题。它本质上做的是将列表中的每个数字与其他每个数字进行比较，以查看较小的数字是否可以被较大的数字整除并生成两个字典：

一个数字被一个更大的数字整除的次数数，
一个有它被小数整除的次数它。

您比较两个字典并将每个键的值相乘，因为其中一个键中有 0 基本上意味着它不是三元组中的第二个数字。

示例：

l = [1,2,3,4,5,6]
lower_counts = {1:5, 2:2, 3:1, 4:0, 5:0, 6:0}
upper_counts = {1:0, 2:1, 3:1, 4:2, 5:1, 6:3}
triple_tuple = ([1,2,4], [1,2,6], [1,3,6])

关于从函数中删除嵌套 for 循环的指南

Guidance on removing a nested for loop from function

python

nested-loops