勾股三倍效率 [英] Pythagorean Triples Efficiency

问题描述

我需要创建一个函数，该函数接受一个整数列表并返回列表中是否存在勾股数三元组.例如， [3, 5, 7, 4] 返回 True 因为 3, 4, 5 是勾股三元组.到目前为止，我有这个(在 Python 中):

I need to create a function that takes a list of integers and returns whether or not there is a Pythagorean triple inside the list. For example, [3, 5, 7, 4] returns True since 3, 4, 5 is a Pythagorean triple. So far I have this (in Python):

def containsPythagoreanTriple(a): 
    for i in xrange(len(a)): #square the numbers
        num = a[i]
        a[i] = num**2
    a = sorted(a)
    for start in xrange(len(a)): #compare every pair
        for i in xrange(start+1, len(a)):
            if a[start] + a[i] in a:
                return True
    return False

有没有办法让这更有效?

Is there a way to make this even more efficient?

推荐答案

就性能而言，该代码有一些可以改进的地方.

There are a few things that could be improved in that code, as far as performance is concerned.

当前的实现是 O(N**3)(其中 N 是 len(a))，因为您检查方块列表包含每对项目的每个总和.list 中的成员资格测试是 O(N) 并且有 O(N**2) 对要测试.

The current implementation is O(N**3) (where N is len(a)), as you check if the list of squares contains each sum of each pair of items. Membership testing in a list is O(N) and there are O(N**2) pairs to test.

您可以通过使用 set 而不是列表来保存您的项目来改进这一点.测试 set 中的项目成员资格是 O(1)，因此您将通过这种方式获得 O(N**2) 算法.

You can improve this bit by using a set rather than a list to hold your items. Testing item membership in a set is O(1), so you'll get an O(N**2) algorithm this way.

有一些进一步的变化可能会加快速度，但它们都没有进一步改变渐近复杂性.首先，您不需要调用 sorted，因为无论如何您都将测试每对项目.您还可以使用集合推导式进行平方，而不是覆盖原始的 a 列表.最后，您可以使用 itertools.combinations 生成平方对，并使用 any 在生成器表达式上测试它们的总和是否在集合中.

There are some further changes that might speed things up a bit, but none of them change the asymptotic complexity any further. To start with, you don't need to call sorted, since you are going to test every pair of items anyway. You can also use a set comprehension to do your squaring, rather than overwriting the original a list. Finally, you can use itertools.combinations to generate your pairs of squares, and any on a generator expression to test if their sums are in the set.

以下是使用相同算法的一些更优化的代码:

Here's some more optimized code using the same algorithm:

import itertools

def containsPythagoreanTriple(a):
    squares = {x*x for x in a} # set comprehension
    return any(x+y in squares for x,y in itertools.combinations(squares))

通过以更基本的方式更改算法，可能还有进一步优化的空间.例如，您不需要测试每一对，因为某些值永远不可能是三角形的短腿"(例如最大值).您可以过滤传递给 itertools.combinations 的平方，以便它们仅包含小于或等于 max(squares)-min(squares) 的平方.我不确定这是否值得，除非您的值列表非常大.

There might still be further room to optimize things a bit more, by changing the algorithm in more fundamental ways. You don't need to test every pair for instance, since some values can never be the "short leg" of a triangle (the largest value, for instance). You could filter the squares passed to itertools.combinations so that they include only those less than or equal to max(squares)-min(squares). I'm not sure if this would be worth while unless your list of values gets pretty large.

这篇关于勾股三倍效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！