Programı hızlandırmak için neler yapılabilir?

2 beğenilme 0 beğenilmeme
134 kez görüntülendi

Project Euler 513 sorusu

https://projecteuler.net/problem=513

Üçgenin kenarları tamsayı , a <= b <= c <= 100000=n

ve  c kenarına ait kenarortay  tamsayı ise

üçgenlerin sayısı kaçtır?

a<=b<=c<=10 ise 3 üçgen

a<=b<=c<=50 ise 165 üçgen

a<=b<=c<=100 ise 835 üçgen

a<=b<=c<=150 ise 2125 üçgen

a<=b<=c<=200 ise 4088 üçgen

a<=b<=c<=250 ise 6806 üçgen  

a<=b<=c<=500 ise 32251  üçgen

a<=b<=c<=750  ise 79387  üçgen

a<=b<=c<=1000 ise 149869 üçgen olduğunu bulabildim.

a<=b<=c<=100000 ise K üçgen vardır.

K=?  Cevabı bulamadım.

Yazdığım Python Programı:

n=1+10

say=0

for a in range(1,n):

    a2=2*a**2

    for b in range(a,n):

        b2=2*b**2

        for c in range(b,n):

            if c%2 != 0: continue

            if a+b<=c : continue

            if b+c<=a: continue

            if a+c<=b : continue           

            m=0.5*((a2+b2-c**2)**0.5)

            if int(m)==m :

                say=say+1

                print(say,")",a,b,c,m)              

input("end")

18, Aralık, 2016 Bilgisayar Bilimi kategorisinde suitable2015 (3,893 puan) tarafından  soruldu

Konuyla ilgili makale  (Integer-Sided Triangles with integral medians)   şu linkten okunabilir:

https://arxiv.org/vc/arxiv/papers/0901/0901.1857v1.pdf

a <= b <= c<= 5000  ise 4982858 üçgen olduğunu bulabildim.

Programı IDLE yerine DOS'ta çalıştırınca, program daha hızlı çalışıyor.

Bu arada out of memory hatasıyla karşılaşmamak için kenar uzunluklarını ve

kenarortay uzunluğunu yazdırmadım.

Sorunun cevabını (n=100000 için) bulabileceğimi sanmıyorum. 

Şu ana dek bu sorunun  cevabını  bulmuş olan 202 kişiyi tebrik ederim.

Yorumlarınızı bekliyorum. 


'''

Analiz edilirse, O(N2) şeklinde bir karmaşıklığı vardır,

Bu yöntem hashing yöntemidir. Bu programın eşdeğeri C++ ile de yazılmış,

aynı aralık (a<=b=<c=5000) için 48 sn'de çözüm üretmiştir.

Eğer Memory sıkıntısı oluşturmasa C++, 48 sn'nin altında da çözüm üretir.


Python'da 100002 tabloların boyutu... C++'da benim makinem için 64000'lik bir

boyutta tablo tanımlayabildim.


Bu Python için bir avantaj ancak, ilk 5000 değer için,

bu kodun çalışma süresi benim makinem için yaklaşık 6 dakika...

C++'da çalışırsa 48 sn... C++ kodunu da koyacağım...


Tabii C++'da hashing tabloları oluşturmak daha zor. Linkli liste array'i

oluşturmak gerekiyor.


Suitable'ın programı, O(N3) karmaşıklıktadır. İlk 5000 değer için bile,

saatlerce çalışır bir sonuç verebilmek için.

Herhalde soruyu soranların amacı, günlerce çalışan program ile sonuç buldurmak

değildir. Suitable'ın programı aylarca çalışırsa 100000 (a<=b=<c<==100000)için

bir sonuç üretir.


Tabii Hashing yöntemini kullanabilmek için şunu düşünmek gerekirdi:


4*(mc**2)+(c**2)=2*(a**2+b**2)


Sol tarafta bir eşitlik, sağ tarafta bir eşitlik.


Suitable'ın çözümü Brute Force'tur. 3 adet döngüyü alt alta koymak ne zaman

bir çözüm verirdi, ilk 1000 değer veya daha düşük sayılar için. Gerçi, öyle

çalıştığı halde benim makinede (normal bir laptop bu arada) 2 dakikayı aşıyor

çalışma süresi. O durumda kod bir sonuç ürettiği için, belki O(N3) karmaşıklık

önemsenmeyebilirdi. Ancak, ben yine de önemserdim, o ayrı :)


Bu arada suitable'ın kodu ilk 5000 değer için saatlerdir çalışıyor hâlâ bir

çözüm üretmiş değil.


Neyse, nedir bu hashing? Kısaca, Modüler aritmetikten faydalanarak, kayıtları ilgili göze yerleştirme işlemidir.

Örneğin, elimizde 107 nolu bir kayıt var, eğer hashing function 23 ise, 107%23= N kaç ise oraya o kaydı yerleştirmektir.


Eğer aynı N değerini veren bir sonuçla karşılaşılırsa ki buna Hashing Collision denir, o zaman Linkli Liste array yapılarak,

buna bir çözüm üretilebilir. Bu yöntemlerden biri tabii ki, daha fazla ayrıntı gereksiz.

Gerçi ben bir zamanlar Tree'leri de anlatmıştım...  Nafile tabii.


Tabii a<=b=c<=100000 için Python kullanmadım, yöntem hashing bile olsa günlerce sürebilir. C++'da yazmak gerekir...


Ekran çıktısı da çalışma sürelerini gösteriyor milisaniye cinsinden...


Tekrar vakit bulduğumda görüşürüz...

'''

import time

time1=time.time()

lefttable=[[] for index in range(100002)]

quot=(3**0.5)/2 #mc till ...

print(quot)



for c in range(2,1002,2):

    upmc=int(quot*c)

    #print(c)

    c2=(c**2)//2

    for mc in range(1,upmc):

        t=2*(mc**2)+c2

        lefttable[t%100001].append((mc,c,t))


count=0

#print(righttable[100])


def Solve(rtable):


    count=0


    for i in range(100002):

        arr1=lefttable[i]

        #print(i,count)

        #print(len(arr1))

        for ii in range(len(arr1)):

            mc,c,t1=arr1[ii]

            arr2=rtable[i]

            

            for jj in range(len(arr2)):

                a,b,t2=arr2[jj]

                if t1==t2:

                    if c>=b:

                        if (a+b)>c:

                            if abs(a-b)<c:

                                #print("a=",a,"b=",b,"c=",c,"mc=",mc,"t=",t1)

                                count+=1

        #print("i=",i,"arr1=",len(lefttable[i]),"arr2=",len(rtable[i]))

         

    return count


def main():

    

    count=0

    


    start=1

    end=start+100

    while (start<1001):

        righttable=[[] for index in range(100002)]

        for a in range(start,end):

            a2=a**2

            #print("a=",a)

            amod2=a%2

            for b in range(a,1001):

                if amod2==b%2:

                    b2=b**2

                    t=a2+b2

                    righttable[t%100001].append((a,b,t))

    

        cnt=Solve(righttable)

        count+=cnt

        #print("Between..",start,end,cnt,count)

        start=end

        end=start+100

    print(count)


main()

print((time.time()-time1)*1000)

        

        




        




naim.jpe (0,2 MB)

Bu arada, suitable'ın kodunda ilk göze çarpan, a2 ile b2'yi hesaplarken 2 ile çarpma işlemini gereksiz yere bir defa kullanmasıdır. O(N3) karmaşıklığa evet desek bile...

...