更快的Python技术,可以从彼此倍数的数字列表中计算三元组

Question

假设我们有一个数字列表,l.我需要计算所有长度为3的元组l,(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到返回0而不是1对[1, 1, 1]例如输入.