CODEWITHSUNDEEP
pythonpython-2.7
sammuh
sammuh

Reputation: 51

Pythagorean Triples Efficiency

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?

Upvotes: 0

Views: 1082

Answers (2)

user3883456
user3883456

Reputation: 11

same, but little bit differently

import math    
def tripple(array): 
    array = sorted(array)
    for start in xrange(len(array)): #compare every pair
      m = array[start]
      for i in xrange(start+1, len(array)):
        n = array[i]
        if math.sqrt(n*n+m*m) in array:
          print m, n, math.sqrt(n*n+m*m)

array=[4, 6, 2, 3, 7, 5, 9, 8, 10, 12, 15, 40, 41];     
tripple(array);

Upvotes: 1

Blckknght
Blckknght

Reputation: 104712

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

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.

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.

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))

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.

Upvotes: 2

Related Questions