Эффективность пифагорейских троек

Question

Мне нужно создать функцию, которая берет список целых чисел и возвращает, есть ли в списке пифагорейская тройка. Например, [3, 5, 7, 4] возвращает True, так как 3, 4, 5 является пифагорейской тройкой. До сих пор у меня это (в Python):

Есть ли способ сделать это еще более эффективным?

Answer 1

В этом коде есть несколько вещей, которые могут быть улучшены в отношении производительности.

Текущая реализация - O(N**3) (где N - len(a)), поскольку вы проверяете, содержит ли список квадратов каждую сумму каждой пары предметов. Тест на членство в list равен O(N), а для тестирования - O(N**2).

Вы можете улучшить этот бит, используя set, а не список для хранения ваших предметов. Элемент тестирования элемента в set равен O(1), поэтому вы получите алгоритм O(N**2).

Есть некоторые дальнейшие изменения, которые могут немного ускорить работу, но ни одна из них не изменит асимптотическую сложность. Для начала вам не нужно звонить sorted, так как вы собираетесь тестировать каждую пару элементов в любом случае. Вы также можете использовать понимание набора, чтобы выполнить возведение в квадрат, а не переписывать исходный список a. Наконец, вы можете использовать itertools.combinations для генерации ваших пар квадратов и any для выражения генератора для проверки их сумм в наборе.

Вот некоторые более оптимизированный код, используя тот же алгоритм:

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). Я не уверен, что это будет стоить, если ваш список значений не станет довольно большим.

Answer 2

же, но немного по-другому

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