Matlab ile Özel Dik Üçgen Bulma Yöntemi Geliştirme
Geleneksel programlamayı matlab ile uygulamak, döngü kullanarak işleri halletmek isteyenler için hazırladım.
Matlab kendi içinde bulundurduğu fonksiyonların ne kadar etkili olduğunu göstermek üzere bir çalışma yapmaya karar verdim. Burada sunum için matlab yeni özelliği olan live script yani .mlx dosya tipini kullandım.
Son denemelerimde döngü olmadan Matlab Broadcast Özelliğini kullandım. Bu özelliğin ne olduğunu sayfamdan öğrenebilirsiniz.
Son iki kısım video anlatmadım. s=1e5 yani 100000 ile denediğimde 13-14 saniye arası sürdü. diğer üstteki hiçbir algoritma bu kadar büyük sayıya karşılık bu kadar hızlı değil.
Video izlemek için bu linke tıklayabilirsiniz. Matlab Ders5 karar ve döngü ifadeleri
Uygulama Mathworks Sayfasında:
https://www.mathworks.com/matlabcentral/fileexchange/66120-pisagorfact
Uzun Kenar formülü z=sqrt(x.^2+y.^2)
pisagor=@(x,y) sqrt(x.^2+y.^2);
s=100;
Yavaş olan
c=[];
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
c=[c temp];
end
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Önceden hafızadan yer ayırtmak doğru olan. Fakat daha fazla yer kaplıyor.
c=zeros(s);
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Matlab parallel loop. DAHA HIZLI OLDU HMMM.
feval(fonksiyon,parametreler) parfor kullanırken kullanın.
c=zeros(s);
tic;
parfor b=1:s
for a=1:s
temp=feval(pisagor,b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Matlab parallel loop for döngüsü içinde. KULLANMAYI TAVSİYE ETMEM.
c=zeros(s);
tic;
for b=1:s
parfor a=1:s
temp=feval(pisagor,b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Boyut değişiyor görünse de bu ancak önceden ayrılan boyut yetmediğinde oluyor. Yeni bir eleman bulunduğunda hemen yer açıyor böylece daha az ram harcıyor.
l=0;
c=zeros(1,3);
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
if numel(c)<l
c=[c zeros(l-numel(c))]; %page expansion
end
l=l+1;
c(l)=temp;
end
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Ufak bir değişiklik. Fark ettiyseniz pisagor(a,a)==a*sqrt(2) ve( pisagor(3,4)==pisagor(4,3) veya pisagor(5,12)==pisagor(12,5) ). o halde a sayısı bnin bir fazlası olursa gereksiz kontrollerden kaçınmış oluruz.
Ayrıca boyutun artıp artmadığını
l=0;
c=zeros(2,3);
tic;
for b=3:s
for a=b+1:s
temp=pisagor(b,a);
if fix(temp)==temp
l=l+1;
c(l,:)=[b,a,temp];
end
end
if numel(c)<l
c=[c; zeros(l-numel(c),3)]; %page expansion
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Hadi döngü yerine matlab fonksiyonlarını kullanmayalım. Eğer döngü kullanmak istemezseniz sizi anlarım ve yaparım :)
Matlab içeriğindeki fonksiyonları kullanırken simd veya vektörleştirilmiş kod kullanmıış mı? diye sormanıza gerek yoktur. c/c++ dillerinde bile kendiniz daha hızlısını yazmanız zordur ama imkansız değildir. matlab döngüsü kullanmak kodunuzu yavaş gösterir bu yüzden matlab coder kullanırız.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
c2 = c2( fix(c2)==c2 );
disp(c2)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Eğer üretilen uzun kenarlara bakarsak kendini tekrarlıyor. 3-4-5 ve 4-3-5 gibi. O zaman matrisin diagonali ve üst üçgeni dışındaki tekrarlanan hesaplara ihtiyaç yoktur. böylece unique fonksiyonunu kullanmaya gerek kalmadı.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
c2 = c2( fix(c2)==c2 & triu(ones(size(c2)),0) );
disp(c2)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Uzun kenarı tam sayı olan üçgenleri bulsak da elimizde diğer iki kenar yok. bu kenarları ekleyelim.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
mask=fix(c2)==c2 & triu(ones(size(c2)),0);
[rows,cols]=find(mask);
c2 = c2( mask );
b2 = b( rows );
a2 = a( cols ); %unique
ucgenler=[b2.' a2.' c2];
disp(ucgenler)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Çok değişken tanımlamıştım önceden şimdi değişken sayısını azaltarak hesap süresini azaltmayı deneyeceğim.
Ayrıca iki kenarı çift olan üçgenlerin asıl 3-4-5 gibi üçgenlerin katlarıdır. Bunları hesaplamaya gerek yoktur.
b=3:2:s;
a=4:2:s;
tic;
c2=sqrt((b.').^2+a.^2);
mask=and(fix(c2)==c2 , triu(ones(size(c2)),0)); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
b=4:2:s;
a=5:2:s;
tic;
c2=sqrt((b.').^2-a.^2);
mask=and( and( triu(ones(size(c2)),0) , fix(c2)==c2 ) , isprime(c2) ); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([c2 b2.' a2.'])
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Burada amacım hızlandırmak değil. Sadece matlab concurent özelliğini tanıtmak için kullandım. matlab concurency olarak multiprocess kullanır. smpd bloğu çalışırken görev yöneticisine bakın, parallel toolbox içinden kaç thread açtıysanız o kadar process açar.
b=3:2:s;
a=4:2:s;
tic;
spmd
c2=sqrt((b.').^2+a.^2);
mask=and(fix(c2)==c2 , triu(ones(size(c2)),0)); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
end
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Benim asıl istediğim özel üçgenler sonraki öncekinin herhangi bir katı olmayacak ve uzun kenarı aynı olmayacak.
"sonraki öncekinin herhangi bir katı olmayacak" şartı ancak bir kenarı asal ise gerçekleşebilir. Prime fonksiyonu bizim için asal sayılardan olUşan bir vektör verir. Asal üretmek bize yük getirdiğinden bu yükün ne kadar etkilediğini öğrenmek istedim. Böylece hesap kümemiz oldukça daraldı.
Burada fazladan asal olan çift sayıyı silmem gerektiğini düşündüm. üçgenleri bulurken bize fazladan yük olacak fakat bu sayıyı silmek bize yine fazladan yük getireceğinden bende bu yükün ne kadar etkilediğini bulmak istedim.
ASALIN İLK ELEMANI SİLİNMİYOR.
tic;
b=primes(s);
%b(1)=[];
a=4:2:s;
c2=sqrt((b.').^2+a.^2);
mask=and( triu(ones(size(c2)),0) , fix(c2)==c2 );
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['s = ',num2str(s),' elleapse time: ',num2str(ellapse)])
ASALIN İLK ELEMANI SİLİNİYOR.
tic;
b=primes(s); b(1)=[];
a=4:2:s;
c2=sqrt((b.').^2+a.^2);
mask=and( triu(ones(size(c2)),0) , fix(c2)==c2 );
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['s = ',num2str(s),' elleapse time: ',num2str(ellapse)])
Matlab kendi içinde bulundurduğu fonksiyonların ne kadar etkili olduğunu göstermek üzere bir çalışma yapmaya karar verdim. Burada sunum için matlab yeni özelliği olan live script yani .mlx dosya tipini kullandım.
Son denemelerimde döngü olmadan Matlab Broadcast Özelliğini kullandım. Bu özelliğin ne olduğunu sayfamdan öğrenebilirsiniz.
Son iki kısım video anlatmadım. s=1e5 yani 100000 ile denediğimde 13-14 saniye arası sürdü. diğer üstteki hiçbir algoritma bu kadar büyük sayıya karşılık bu kadar hızlı değil.
Video izlemek için bu linke tıklayabilirsiniz. Matlab Ders5 karar ve döngü ifadeleri
Uygulama Mathworks Sayfasında:
https://www.mathworks.com/matlabcentral/fileexchange/66120-pisagorfact
Uzun Kenar formülü z=sqrt(x.^2+y.^2)
pisagor=@(x,y) sqrt(x.^2+y.^2);
s=100;
Yavaş olan
c=[];
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
c=[c temp];
end
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Önceden hafızadan yer ayırtmak doğru olan. Fakat daha fazla yer kaplıyor.
c=zeros(s);
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Matlab parallel loop. DAHA HIZLI OLDU HMMM.
feval(fonksiyon,parametreler) parfor kullanırken kullanın.
c=zeros(s);
tic;
parfor b=1:s
for a=1:s
temp=feval(pisagor,b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Matlab parallel loop for döngüsü içinde. KULLANMAYI TAVSİYE ETMEM.
c=zeros(s);
tic;
for b=1:s
parfor a=1:s
temp=feval(pisagor,b,a);
if fix(temp)==temp
c(b,a)=temp;
end
end
end
disp(c(not(c==0)))
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Boyut değişiyor görünse de bu ancak önceden ayrılan boyut yetmediğinde oluyor. Yeni bir eleman bulunduğunda hemen yer açıyor böylece daha az ram harcıyor.
l=0;
c=zeros(1,3);
tic;
for b=1:s
for a=1:s
temp=pisagor(b,a);
if fix(temp)==temp
if numel(c)<l
c=[c zeros(l-numel(c))]; %page expansion
end
l=l+1;
c(l)=temp;
end
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Ufak bir değişiklik. Fark ettiyseniz pisagor(a,a)==a*sqrt(2) ve( pisagor(3,4)==pisagor(4,3) veya pisagor(5,12)==pisagor(12,5) ). o halde a sayısı bnin bir fazlası olursa gereksiz kontrollerden kaçınmış oluruz.
Ayrıca boyutun artıp artmadığını
l=0;
c=zeros(2,3);
tic;
for b=3:s
for a=b+1:s
temp=pisagor(b,a);
if fix(temp)==temp
l=l+1;
c(l,:)=[b,a,temp];
end
end
if numel(c)<l
c=[c; zeros(l-numel(c),3)]; %page expansion
end
end
disp(c)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Hadi döngü yerine matlab fonksiyonlarını kullanmayalım. Eğer döngü kullanmak istemezseniz sizi anlarım ve yaparım :)
Matlab içeriğindeki fonksiyonları kullanırken simd veya vektörleştirilmiş kod kullanmıış mı? diye sormanıza gerek yoktur. c/c++ dillerinde bile kendiniz daha hızlısını yazmanız zordur ama imkansız değildir. matlab döngüsü kullanmak kodunuzu yavaş gösterir bu yüzden matlab coder kullanırız.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
c2 = c2( fix(c2)==c2 );
disp(c2)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Eğer üretilen uzun kenarlara bakarsak kendini tekrarlıyor. 3-4-5 ve 4-3-5 gibi. O zaman matrisin diagonali ve üst üçgeni dışındaki tekrarlanan hesaplara ihtiyaç yoktur. böylece unique fonksiyonunu kullanmaya gerek kalmadı.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
c2 = c2( fix(c2)==c2 & triu(ones(size(c2)),0) );
disp(c2)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Uzun kenarı tam sayı olan üçgenleri bulsak da elimizde diğer iki kenar yok. bu kenarları ekleyelim.
pisagor=@(x,y) sqrt(x.^2+y.^2);
b=3:s;
a=3:s;
tic;
c2=pisagor(b.',a);
mask=fix(c2)==c2 & triu(ones(size(c2)),0);
[rows,cols]=find(mask);
c2 = c2( mask );
b2 = b( rows );
a2 = a( cols ); %unique
ucgenler=[b2.' a2.' c2];
disp(ucgenler)
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Çok değişken tanımlamıştım önceden şimdi değişken sayısını azaltarak hesap süresini azaltmayı deneyeceğim.
Ayrıca iki kenarı çift olan üçgenlerin asıl 3-4-5 gibi üçgenlerin katlarıdır. Bunları hesaplamaya gerek yoktur.
b=3:2:s;
a=4:2:s;
tic;
c2=sqrt((b.').^2+a.^2);
mask=and(fix(c2)==c2 , triu(ones(size(c2)),0)); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
b=4:2:s;
a=5:2:s;
tic;
c2=sqrt((b.').^2-a.^2);
mask=and( and( triu(ones(size(c2)),0) , fix(c2)==c2 ) , isprime(c2) ); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([c2 b2.' a2.'])
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Burada amacım hızlandırmak değil. Sadece matlab concurent özelliğini tanıtmak için kullandım. matlab concurency olarak multiprocess kullanır. smpd bloğu çalışırken görev yöneticisine bakın, parallel toolbox içinden kaç thread açtıysanız o kadar process açar.
b=3:2:s;
a=4:2:s;
tic;
spmd
c2=sqrt((b.').^2+a.^2);
mask=and(fix(c2)==c2 , triu(ones(size(c2)),0)); %
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
end
ellapse=toc;
disp(['elleapse time: ',num2str(ellapse)])
Benim asıl istediğim özel üçgenler sonraki öncekinin herhangi bir katı olmayacak ve uzun kenarı aynı olmayacak.
"sonraki öncekinin herhangi bir katı olmayacak" şartı ancak bir kenarı asal ise gerçekleşebilir. Prime fonksiyonu bizim için asal sayılardan olUşan bir vektör verir. Asal üretmek bize yük getirdiğinden bu yükün ne kadar etkilediğini öğrenmek istedim. Böylece hesap kümemiz oldukça daraldı.
Burada fazladan asal olan çift sayıyı silmem gerektiğini düşündüm. üçgenleri bulurken bize fazladan yük olacak fakat bu sayıyı silmek bize yine fazladan yük getireceğinden bende bu yükün ne kadar etkilediğini bulmak istedim.
ASALIN İLK ELEMANI SİLİNMİYOR.
tic;
b=primes(s);
%b(1)=[];
a=4:2:s;
c2=sqrt((b.').^2+a.^2);
mask=and( triu(ones(size(c2)),0) , fix(c2)==c2 );
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['s = ',num2str(s),' elleapse time: ',num2str(ellapse)])
ASALIN İLK ELEMANI SİLİNİYOR.
tic;
b=primes(s); b(1)=[];
a=4:2:s;
c2=sqrt((b.').^2+a.^2);
mask=and( triu(ones(size(c2)),0) , fix(c2)==c2 );
[rows,cols]=find(mask);
c2 = c2( mask );
b2= b( rows );
a2= a( cols ); %unique
disp([b2.' a2.' c2])
ellapse=toc;
disp(['s = ',num2str(s),' elleapse time: ',num2str(ellapse)])
Yorumlar
Yorum Gönder