时间戳

首页 > 解决方案 > 更快的 Python 技术，用于从相互为多个的数字列表中计算三元组

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

问题描述

假设我们有一个数字列表，l。我需要从 COUNT 长度为 3 的所有元组l，(l_i,l_j,l_k)以便l_i均分l_j和l_j均分l_k。规定指标i,j,k有关系i<j<k

IE;

如果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 个元素），所花费的时间会增加太多。有没有更快/更好的方法来做到这一点？

标签： pythonperformancelist-comprehension

解决方案

We can count the number of triples with a given number in the middle by counting how many factors of that number are to its left, counting how many multiples of that number are to its right, and multiplying. Doing this for any given middle element is O(n) for a length-n list, and doing it for all n possible middle elements is 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

Incidentally, the code in your question doesn't actually work. It's fallen into the common newbie trap of calling index instead of using enumerate to get iteration indices. More than just being inefficient, this is actually wrong when the input has duplicate elements, causing your myCOUNT to return 0 instead of 1 on the [1, 1, 1] example input.

推荐阅读