Чрезвычайно неэффективный код python

Question

Я сделал программу, позволяющую пользователям вводить максимально возможную гипотенузу прямоугольного треугольника, и моя программа будет перечислять список всех возможных сторон треугольников. Проблема в том, что программа навсегда запускается, когда я ввожу значение, такое как 10000. Любые предложения о том, как повысить эффективность программы?

Код:

largest=0 
sets=0 
hypotenuse=int(input("Please enter the length of the longest side of the triangle")) 
for x in range(3,hypotenuse): 
    for y in range(4, hypotenuse): 
     for z in range(5,hypotenuse): 
      if(x<y<z):     
       if(x**2+y**2==z**2): 
        commonFactor=False 
        for w in range(2,x//2): 
         if (x%w==0 and y%w==0 and z%w==0): 
          commonFactor=True 
          break 
        if not(commonFactor): 
         print(x,y,z) 
         if(z>largest): 
          largest=z 
         sets+=1 
print("Number of sets: %d"%sets) 
print("Largest hypotenuse is %d"%largest) 

Спасибо!

Answer 1

нравится это?

hypothenuse=10000 
thesets=[] 
for x in xrange(1, hypothenuse): 
    a=math.sqrt(hypothenuse**2-x**2) 
    if(int(a)==a): 
     thesets.append([x,a]) 
print "amount of sets: ", len(thesets) 
for i in range(len(thesets)): 
    print thesets[i][0],thesets[i][1], math.sqrt(thesets[i][0]**2+ thesets[i][1]**2) 

изменения: изменен, так что вы можете распечатать наборы тоже (этот метод в O (N), который является самым быстрым возможным способом я думаю?) Примечание: если вы хотите, количество наборов, каждый из которых дается дважды, например: 15 * 2 = 9 * 2 + 12 * 2 = 12 * 2 + 9 ** 2

Не уверен, если я понимаю ваш код правильно, но если вы даете в 12 , вам, чем нужно, чтобы все возможные треугольники с гипотенузой меньше 12? или вы, чем хотите знать возможности (насколько я знаю) написать 12 * 2 = a * 2 + b ** 2?

, если вы хотите, чтобы все возможности, чем я буду редактировать код немного

для всех возможностей * 2 + б * 2 = с ** 2, где с < гипотенуза (не уверен, что это, что вы хотите):

hypothenuse=15 
thesets={} 
for x in xrange(1,hypothenuse): 
    for y in xrange(1,hypothenuse): 
     a=math.sqrt(x**2+y**2) 
     if(a<hypothenuse and int(a)==a): 
      if(x<=y): 
       thesets[(x,y)]=True 
      else: 
       thesets[(y,x)]=True 
print len(thesets.keys()) 
print thesets.keys() 

это решает в O (п ** 2), и ваше решение даже не работает, если гипотенуза = 15, ваше решение дает:

(3, 4, 5) (5, 12, 13) Количество комплектов: 2

в то время как правильным является: [(5, 12), (3, 4), (6, 8)]

, так как 5 * 2 + 12 * 2 = 13 * 2, 3 * 2 + 4 * 2 = 5 * 2, и 6 * 2 + 8 * 2 = 10 * * 2, в то время как ваш метод не дает этот третий вариант? изменить: изменилось numpy на математику, и мой метод также не дает множителей, я просто показал, почему я получаю 3 вместо 2 (эти три разных варианта - это разные решения проблемы, поэтому все 3 действительны, поэтому ваше решение для проблема неполна?)

Answer 2

Вот краткая попытка использовать предварительно рассчитанные квадраты и кешированные квадратные корни. Вероятно, существует множество математических оптимизаций.

def find_tri(h_max=10): 
    squares = set() 
    sq2root = {} 
    sq_list = [] 
    for i in xrange(1,h_max+1): 
    sq = i*i 
    squares.add(sq) 
    sq2root[sq] = i 
    sq_list.append(sq) 
    # 
    tris = [] 
    for i,v in enumerate(sq_list): 
    for x in sq_list[i:]: 
     if x+v in squares: 
     tris.append((sq2root[v],sq2root[x],sq2root[v+x])) 
    return tris 

Демо:

>>> find_tri(20) 
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)] 

Answer 3

Один очень простой оптимизации произвольно решать x <= y. например, если (10,15,x) не является решением, то (15,10,x) также не будет решением. Это также означает, что если 2x**2 > hypoteneuse**2, то вы можете завершить алгоритм, поскольку нет решения.