python - 更快的 Python 技术，用于从互为倍数的数字列表中计算三元组

Question

假设我们有一个数字列表，l .我需要从 l 中计算所有长度为 3 的元组, (l_i,l_j,l_k)这样 l_i平分l_j , 和 l_j平分l_k .规定索引 i,j,k有关系i<j<k

即；

如果l=[1,2,3,4,5,6] , 那么元组就是 [1,2,6], [1,3,6],[1,2,4] , 所以 COUNT将是 3。

如果l=[1,1,1] , 那么唯一的元组就是 [1,1,1] , 所以 COUNT将是 1。

这是我到目前为止所做的，使用列表理解:

def myCOUNT(l):
    newlist=[[x,y,z] for x in l for y in l for z in l if (z%y==0 and y%x==0 and l.index(x)<l.index(y) and l.index(y)<l.index(z))]
    return len(newlist)

>>>l=[1,2,3,4,5,6]
>>>myCOUNT(l)
3

这有效，但作为 l变得更长(并且它可以大到 2000 个元素长)，它花费的时间增加太多。有没有更快/更好的方法来做到这一点？

Answer 1

我们可以计算给定数字在中间的三元组的数量，方法是计算该数字的左侧有多少个因数，计算该数字右侧有多少个倍数，然后相乘。对于长度为 n 的列表，对任何给定的中间元素执行此操作的复杂度为 O(n)，对所有 n 个可能的中间元素执行此操作的复杂度为 O(n^2)。

def num_triples(l):
    total = 0
    for mid_i, mid in enumerate(l):
        num_left = sum(1 for x in l[:mid_i] if mid % x == 0)
        num_right = sum(1 for x in l[mid_i+1:] if x % mid == 0)
        total += num_left * num_right
    return total

顺便说一句，您问题中的代码实际上不起作用。它陷入了调用 index 而不是使用 enumerate 来获取迭代索引的常见新手陷阱。不仅仅是效率低下，当输入有重复元素时，这实际上是错误的，导致您的 myCOUNT 为 return 0 instead of 1在 [1, 1, 1] 示例输入上。