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

2 beğenilme 0 beğenilmeme
240 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,914 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...

Python programımın aynısını Java'da kodladım.

n=5000 için 64 saniyede aynı  sonuç bulundu.

n=10000 için 525 saniyede  üçgen sayısı 22083294 olarak bulundu.



F(8000) nedir Java Kodunuzda?  F(10000), 10 dakikadan daha düşük bir zamanda sonuç verdiğine göre, F(8000) daha kısa sürede yanıt verir. :)

Java, Python, Basic fark etmez üstteki algoritmada. algoritmanız, N3 karmaşıklıktadır. $a$ ve $b$ sayılarının paritelerinin aynı olması gerekiyor, gözden kaçmış, düşünülmemiş. Yâni her ikisi de çift veya her ikisi de tek sayı olmak zorunda. Ondan sonra kodunuzda, üçgende gereklilik testini 3 $if$ ile yapmışsınız. Halbuki, $(a+b)>c$ ve $abs(a-b)<c$ ifadesi ile ve tek bir if ile yapılabilir.

$a2$ ve $b2$ sayılarını her birini 2 ile çarpmak yerine,  $a2+b2$ sayısı $2$ ile çarpılmalıydı.

Java kodunuzun ekran çıktısını görmek isterim çalışma süresi ile birlikte, jpeg dosyası olarak benim yaptığım gibi gömebilirsiniz yorumunuza.

Java'da 269 saniyede  F(8000) =13689669   olarak bulundu.


F(100000)'i ne kadar sürede bulmasını bekliyorsunuz? Çalışma hızlarını da eklerseniz jpeg formatında daha iyi olur. İlgilenenler görebilir böylelikle.

Kodunuza baktıkça başka şeyler de görmeye başladım, $a$ ile $b$ yi toplayıp $c$ ile karşılaştırdığınız kısım için, toplama işlemi $c$ döngüsünden önce olmalıydı.

Görüldüğü üzere çok fazla bilgi paylaşıldı...

Son olarak şunu ifade edeyim, $c$ döngüsündeki o üç döngü, üçgen testini gerçekten yapıyor mu? Hiç kullanmadım...


public class euler513  {

public static void main(String[] args){  

 long begin = System.currentTimeMillis();                           

int n=1000;   int say=0;  int a,b,c,a2,b2;   double m;

for (a=1;a<=n;a++){ a2=2*a*a;

 { for (b=a; b<=n;b++){ b2=2*b*b;

  for (c=b;c<=n;c++){ if ((c%2) != 0) continue;

if (a+b<=c )  continue; if (b+c<=a) continue; if (a+c<=b) continue;

m=0.5*(Math.sqrt( a2+b2-c*c  )); if (m != (int) m) continue; say  += 1;

}}}} System.out.println(say);

long end = System.currentTimeMillis();

System.out.println((end-begin)/1000 + "saniye"); }}


Yazdıklarımı okuyor musunuz? $c$ döngüsünün altında $a$ ile $b$ toplamı işlemi yapıyorsunuz, bunu düzeltmeniz mümkün değil mi? Diğer dediklerimi de (Artık tekrar edemeyeceğim) uygularsanız, $N3$  karmaşıklıkta, düzgün bir kod elde etmiş olursunuz. 

Amaç, $N3$ karmaşıklıkta kod ile sonuç bulmak mı Sizce? Sorunun, 1 dakikalık bir çözümü var. $N=100000$ i kast ediyorum.

Sayın kartalın önerilerini C++  programımda  uyguladım. 

Önceki Java programım n=12000 için 990 saniyede sonuç verirken, 

aşağıdaki C++  programım 1365 saniyede aynı cevabı verdi. Yani  32616082 üçgen.

#include <iostream>

#include <math.h> 

using namespace std;

int main()  

 { cout << "\nEnter n=";

int n=0;

cin >> n;

n=n+1;

long say=0;

for (int a=1;a<n;a++)

{ long a2=a*a;

for (int b=a;b<n;b++)

{  int ta=a+b;  

int te=abs(a-b) ;

long b2=b*b;

long k=a2+b2;

for ( int c=b;c<n;c++){

if (c%2 !=0) continue;

if ((te>= c) || ( ta <= c) ) continue;

//if ( t<=c ) continue;

//if (b+c<=a) continue;

//if (a+c<=b) continue;

double m=0.5*(sqrt(2*k-c*c) );

if (m ==(int) m)

{  say = say+1;

} } } }

cout << "n=" << n-1 <<  " ucgen =" << say << endl;

return 0;

}

Demek ki eksik uygulamışsınız, Siz yazılanları ya okumuyorsunuz ya anlamıyorsunuz. a ile b aynı paritede olacak, ben hiçbir kodunuzda bunu göremiyorum. İşe Python ile başladınız, hâlâ Python programınızın kaç saat çalıştığını söylemediniz. Söylemek yetmez. Farkında mısınız, hiçbir programınızın ne kadar sürede yanıt verdiğini gösteren ekran çıktısı jpeg olarak yok. Şu şu kadar sürede şunu yaptı, bu bunu bu kadar sürede yaptı, kusura bakmayın Sizin tüm kodlarınızı alıp çalıştıracak halim yok. İkimizden başka konuşan olmadığına göre, bir üçüncünün çalıştıracağını hiç sanmam.

Üstelik, o eksik uygulamanızı bir de Java'da çalıştırıp görmeniz gerekir. İkisini karşılaştırmanız gerekir. Sizin kodunuz üçgen testi yapmıyor. Çünkü, kodunuzda üçgen gereklilik testi yapan fonksiyon yok. Aşağıda göreceksiniz, tıpkı GCD'de atlama yapmıştınız, orada da atlama yapıyorsunuz. 

Sorunuz neydi, Programım nasıl hızlandırılırdı? N3'lük programınızın (Python'daki), N2'lik seviyeye indirilerek, hızlandırıldı. Yani, istenen şey yapıldı.

2 saat çalışan belki de daha fazla bilemiyorum,Python programınıza 5 dakikada yanıt üreten eşdeğeri yapıldı. Üstelik o 5 dakikalık kodda, yapılması gereken çok önemli bir şey daha vardı, herhalde anlama zahmetine girmediğiniz için, fark edemediniz, "Hashing tabloları" oluşturulurken c ile olan bölümde, döngü 1 ile mc arasını kontrol ediyor. 1'den başlamayacak, mc'nin en küçük değeri c'ye bağlı olan bir fonksiyon. Sizin yerinizde olsam, o Python programını önce anlamaya çalışırım, daha sonra bunu uygularım, 5 dakikanın inanılmaz derecede aşağıya indiğini görürdüm. Daha sonra da o algoritmayı, Java veya C++ hangisinde isterseniz, o platformlarda çalıştırırım.

Vaktiyle, bir GCD muhabbetiniz de olmuştu, aradan 2 sene geçti, en sonunda benden başka birinin söylemesi üzerine düzeltmek zorunda kaldınız. Düşünebiliyor musunuz, tam 2 sene. 

Benim buradaki handikapım, öyle bir üçüncü kişi yok burada maalesef.

İsterseniz, o GCD muhabbetini buraya kopyalabilirim. GCD ki en temel fonksiyonlardan biridir. 

Bütün bunlarla birlikte, daha hızlı program yazıyordunuz, peki neden burada sorma gereği duydunuz? Amacınız cidden nedir?

Dün, digitsums diye bir şey paylaştınız, orada amacınız neydi? Burada amacınız nedir? Siz Bilgisayar Bilimcisi misiniz? Bilgisayar Mühendisi? O halde, bu muhabbeti uzatmanın mânâsı yok benim tarafımdan.

Ama Size şunu tavsiye edebilirim, bence Spor yapın, stresinizi kontrol edersiniz.

Üzerinde hiç düşünmeden bodoslama program yazıyorsunuz, hâlâ benim programım şöyle benim programım böyle diye, cahilane konuşuyorsunuz. Programınız, N3 karmaşıklıkta.

Üstelik, hâlâ orjinal soruya yanıt üretebilmiş değilsiniz. Bir kaç gün daha çalıştırın, belki bulursunuz. Selametle.

Edit:

Burada, Jim'in dedikleri.

Kaynak da bu.

https://enigmaticcode.wordpress.com/2014/08/26/enigma-217-auntie-gretas-age/#comments

I am going to edit or remove comments in this thread that don’t add to the discussion of this particular puzzle.

Naim: As Ahmet points out the program you have posted solves a variation on the puzzle where the ages of the nieces are both prime (which does ensure that they have no common factor greater than 1, but is not a necessary condition). It turns out that in the solution the nieces ages happen to both the prime, so your program does find the right answer. It also doesn’t seem to check the condition that the aunt’s age is not an exact multiple of either of the nieces ages.

If you want to post an amended version of your code please feel free to.

2014'te uyarmışım, en sonunda Jim araya girmiş, 2016'da düzeltmişsiniz. Oldukça basit bir soru. Temel seviyede.

Son olarak, eğer N3 karmaşıklığı indiremiyorsanız, ya da bunun ne olduğunu kavrayamıyorsanız, oturun 1 ay bu konuya zamanınızı ayırın. N3, N2, LogN...

Gerçi nafile, Kalp doktoru olmayan birine git Anatomi çalış demeye benziyor. :)

Sonuç olarak, burası babanızın sitesi değilse, bir yerde başka bir entry açtığınızda, o programın en tepesine dileyen hashing, dileyen tree kullanabilir dememelisiniz, sanki yazdığınız o Python'daki program (set ve dict'li olduğu) için, optimum bir program. Kim ne yapacak o programı? Siz bilgi verecek durumda değilsiniz, çünkü uzman değilsiniz bu konularda. Çok fazla zaman ayırdım gereksiz yere burada. Gitti yarım saatim en az.

c ile başlayan döngünün altında a ile b'yi topluyordunuz. Temel algoritmik hata. c döngüsünün altında a ve b'nin değerleri değişiyor mu? Değişmiyor, o zaman neden defaatle aynı değerleri topluyordunuz? Siz denileni anlıyor musunuz? Kaç defa dönüyordu, orada aynı işlem? 

   if a+b<=c : continue Bu satırdan bahsediyorum. c döngüsünün altında, a ve b değerlerini değiştirebilecek bir şey var mı? 

Aslında, program nasıl hızlandırılır demek, soruyu yapıver demekle eşdeğer bir şey, çünkü, sorunun amacı zaten hızlı çalışan program yazabilmek,   neyseki, LogN karmaşıklıktaki kodu burada paylaşmadım, etik açıdan bir sorun yok. Ancak, bir daha burada kod paylaşacağımı sanmıyorum, çünkü yersiz.Bir kere de kalacak. Oldu olacak yanıtı da yazayım buraya...

İnsanların belki günlere çalışıp emek ürettiği bir soru için, "Program nasıl hızlandırılır" diye başlık açıp, sorunun yanıtını bulmak, beklemek... İşte bütün mesele bu.

Hani, buradaki öğrenciler hiç uğraşmadan,  soruları copy paste edip, yant bekliyorlar ya, aynen durum o. 

 if a+b<=c : continue

            if b+c<=a: continue

            if a+c<=b : continue      

Bu üç satırın, üçgen testini yaptığını ispatladınız mı? Nereden geldi bu? Nerede doğruladınız bu üç ifadeyi? Yani, $a+b>c$  and $|a-b|<c$ ile aynı kapıya çıktığını nerede gösterdiniz?

Kırıcı eleştiri yapmayı, karşınızdaki insanı robot gibi görmeyi patron oluşunuza bağlıyorum.


Kırıcı eleştiri mi? Burada yaptığınız kekin şekeri fazla mı olmuş veya buna benzer öznel şeyleri konuşmuyoruz, Bilgisayar Bilimi'ni konuşuyoruz. Bu sorunun Bilgisayar Bilimi ile ilişkisi yeterince anlatılmıştır. 

Kendimi anlatmak yerine, gurur duyduğum arkadaşlarımdan birinin röportajı.

http://www.cio.com.tr/roportaj/saydamlasmak-icin-dijital-donusumu-oncelik-goruyoruz/

http://matkafasi.com/105432/olasilik-sorusu

Bu işin patron olmayla, kendini beğenmiş olmayla, narsisist olmayla falan ilgisi yok. Esas kibir nedir bilir misiniz? Bilmeden soran, bilmeden yanıt verendir. Kısaca, bir başkasının benim hakkında taşıdığı düşünce hiç önemli değildir. Sizin için önemli mi? Bence olmamalı... Yoksa, benim de bir sürü var.

Basit bir olasılık sorusuna bile yanlış yanıt üretmek... İşte mesele bu. 

Bilgisayar Mühendisliği bir meslektir, öyle yazı yazmaya benzemez. Kod yazmak düşünebilmektir, yoksa klavye tuşlamak değil. 

Diğer bölümlerde verdiğiniz cevaplara teker teker bakacak değilim, buna vaktim de yok, ancak gördüğüm kadarıyla burada hatalı cevaplar siteden kaldırılmıyor.

Öğrencilerin işi zor gerçekten... Kolay gelsin...


1 cevap

0 beğenilme 0 beğenilmeme

$4$$m^2$=$2$$a^2$+$2b^2$-$c^2$, bu bilinen kenarortay bağıntısı...

$m^2$+$(c/2)^2$=$t^2$+$u^2$

$a$=$t$+$u$, $b$=$t$-$u$

$((c/2)-t)$$((c/2)+t)$=$(u-m)$$(u+m)$

$k1$=$((c/2)-t)$

$k2$=$((c/2)+t)$

$k3$=$(u-m)$

$k4$=$(u+m)$

$k1*k2=k3*k4$

$k1$ ile $k3$ ile dolanarak, $k2$ ile $k4$'ü hesaplanırsa, daha kısa sürede bir çözüme ulaşılır.

21, Ocak, 21 kartal (496 puan) tarafından  cevaplandı

Project Euler olunca site, orada sorulan soruların, bu arada soruları kimlerin hazırladığını bilmiyorum, ancak, kısa sürede sonuç veren program ile yanıt alınabileceğini biliyorlardır varsayımını taşıyorum. Üstteki cevap ile kısa sürede bir yanıt alınır, yanıtı buraya yazamıyorum, etik açıdan şık olmaz, bir ipucu olarak 2 milyarla başlayan bir cevabı var.

Bence, bu soru Bilgisayar Bilimleri veya Mühendisliği veya Yazılım gibi bilimlerden çok, Matematik kokuyor. Parametrik düzenlemelerle, uygun eşitlikler elde edilmek suretiyle, soruya cevap arandığını düşünmekteyim.

Belki bundan daha iyi bir çözüm de vardır, buna Matematikçiler yanıt verir herhalde.

http://matkafasi.com/103459/ilkel-ucgenlerin-sayisi-nasil-bulunabilir

Bu kadar sağda solda bilgi varsa, gösterdiğiniz üzere, yaparsınız bu soruyu, yapmalısınız, ben Sizin kadar merak etmediğim halde yaptım, 205. kişi diyor, soru beni pek zorlamadı.

Bir ufak tavsiye de buradan gelsin, başkalarının yaptığını değil, kendi yaptığınız Matematiksel analizi paylaşınız. 

Son cümle, zamanım pek yok, Siz 513. sorunun yanıtını buluncaya kadar bir yorum yapmayacağım.


...