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

Question

我正在尝试编写最快的算法，以返回3-2000个整数列表中的“魔法三元组”（即x，y，z，其中z是y的倍数，y是x的倍数）的数量

（注意：我相信列表应该是排序的和唯一的，但给出的一个测试示例是[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  

我花了相当多的时间手动浏览示例并删除列表中不必要部分的循环，但这仍然在大约一秒钟内完成了一个包含2000个整数的列表，其中O（n^2）我找到的解决方案在0.6秒内完成了相同的列表——看起来差别很小，但显然这意味着我的解决方案需要花费60%的时间

我是否错过了一个非常明显的方法来移除其中一个循环

此外，我还提到了制作有向图，我从中看到了希望。我可以使用一个内置函数从原始列表中生成第一个节点的列表，因此原则上我认为这意味着我可以用两个for循环生成整个图形，然后返回第三个节点列表的长度，但我也遇到了麻烦。没有第三个循环，我似乎无法取得进展

Answer 1

@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-plet的方法与查找tri-plet的方法相同，因此我们可以递归地解决该问题

根据我的测试，这个递归解决方案与迭代解决方案相比，如果不是更高的性能的话

Answer 2

使用itertools.combines而不是嵌套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

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%（与使用列表相比），但原则上，对于非常大的n，它可能是增长最快的项