dmd'ye -O -release -inline seçeneklerini vermeyi hatırladın, değil mi? Duyduğuma göre gdc daha hızlı programlar üretiyormuş.

Ama hız yarıya bile inse algoritmaların getirebileceği kazançlar (veya kayıplar ;)) yanında hiç önemi kalmıyor.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Arkadaşlar bu algoritmanın gerçek hayatta faydası nedir?

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Aslında Salihcim bu algoritma tam senlik :)

Gerçek hayattaki kullanım alanlarına gelince dijital fotoğrafçılık, bir ağdaki bilgisayarlar, sosyal ağlar ve Ali beyin de bahsettiği gibi elektronik. Hatta fizikte Hoshen-Kopelman Algoritmasında bir maddenin geçirgenliğinin tespitinde ve elektriksel iletkenliğin modellenmesinde kullanılıyor.

http://www.programlama.tk/resim/resim/hoshen1.png

Örneğin yukarıdaki matriste yalıtkan alanlar 0 ile bakırdan yapılmış kısımlar 1 ile gösterilmiş olsun. Hoshen-Kopelman algoritmasını uyguluyoruz ve sonuç.

http://www.programlama.tk/resim/resim/hoshen2.png

Eagle benzeri programlarla baskılı devre kartı oluştururken buna benzer şekiller ortaya çıktığını görmüşsündür.

Bu anlattıklarım biraz kabaca özeti olmuş oldu. Pratikte uygulama konuları çok ilginç..

Ali beyin de bahsettiği gibi bu yavaş çalışan yöntemlerden bir tanesi. Hatta bu veri sayısı milyarlara çıkınca 30 yıl falan sürebiliyormuş. Evladiyelik! :) Sen çalıştır torunun sonuçlarını görsün.

Ama diğer taraftan dengeli ağaç gibi veri yapıları kullanarak çok hızlı çalışması sağlanabiliyor. Yanlış algoritma kullanarak süper bilgisayarla 10 yılda çözülebilecek bir problemi, kişisel bilgisayarınızda doğru bir algoritma kullanarak çok kısa bir sürede çözmek mümkün. Böylede ilginç bir şey var.

Tabi oyunlardan hiç bahsetmiyorum bile.

http://programlama.tk/resim/resim/adim1.png

Beyazlara dikkat.
<
http://programlama.tk/resim/resim/adim2.png>

Artık bundan bir Pacman [Tetris demek istemiştim] mı yaparsın başka bir oyun mu yaparsın sana kalmış :)

Bir de bol bol D reklamı yapıyorum.

https://github.com/erdemoncel/algoritmalar

Olur ya belki hocalardan bir tanesi merak eder bakar sonra D ile de uygulamalar çok rahatmış. Bir sonraki kitabımı D ile yazayım diye düşünür :)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Problem şu: Bir elektronik paneli var. (Aslında "board"un Türkçe'si ne ise ondan. İşin garibi, panel de Türkçe sayılmaz.:)) Bu panelin üzerinde numaralı noktalar var.

Dosyanın her satırı, iki nokta arasında bağlantı (örneğin, lehim) olduğunu belirtiyor. Erdem'in gösterdiği resimdeki her kırmızı bağlantı öyle bir bağlantı: 4-3, 3-8, vs.

Amaç, daha önceden aralarında bağlantı olmayan noktalar arasında ilk defa öğrenilmiş bir bağlantı görüldüğünde bunu çıkışa yazdırmak. Ama daha önce öğrenilen bilgilere göre zaten bağlantı varsa bunu yazdırmamak.

Örneğin, 8-9 bilgisi okunduğunda çıktıya 8-9 yazdırılmıyor çünkü onların arasında zaten şu yolla bir bağlantı daha önceki bilgilerden biliniyor: 8-3-4-9. (Soldaki gri renkli bilgiler yazdırılmayan satırlar.)

Bu algoritmanın esas güzelliği, hepimizin de böyle yazabileceği bu çözümün aslında en yavaşlardan birisi olması! :) Erdem daha iyi yöntemler gösterecektir.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (erdem:1347974065):

Tabi aslında o grafik genel olarak bağlama işleminin nasıl yapılması gerektiğini gösteriyor. Ama benim yazdığım programın nasıl çalıştığını grafiksel olarak göstermiyor. Yukarıda yazdığım örneği grafiksel olarak gösterirsek:

   6      4
  /|\    /|\
 2 0 5  8 3 9
/ \
7   1

bağlama işlemlerinin sonunda bu şekilde iki tane ağaç oluşuyor. En sonunda değişkenleri yazdırırsanız da şu değerleri görebilirsiniz.

bag[]      : 6 2 6 4 4 6 6 2 4 4
buyukluk[] : 1 1 3 1 4 1 6 1 1 1

Program iki tane ağacı karşılaştırıyor. Her zaman küçük olan ağacı büyük olan ağacın altına ekliyor.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Evet haklısınız :)

Hatta ağaç kullanan yöntemin de hızlısı sanırım. Örneğin iki tane ağacı birbirine bağlayacaksa her zaman küçük ağacın kökünü büyük ağacın köküne bağlıyor.

Bunu ben de ilk planda farkedememiştim. Ama iki tane dizinin değerlerine bakarak çalışma mantığını anlamıştım.

Bir de gene pratik uygulamalarına örnek verecek olursak Fizikte iletkenliğin, geçirgenliğin tespitini çok kolayca yapabiliyoruz.

Buradaki ilk resimde beyazlar geçirgen olan kısımları gösteriyor. Eğer üstte ve altta beyazlar arasında bir bağlantı varsa geçirgen olmuş oluyor. Bu durumda ilk resim geçirgen, ikincisi değil.

http://www.programlama.tk/resim/resim/iletkenlik.png

Bir de Monte Carlo yöntemi var. N x N boyutlarında bir ızgara oluşturuyoruz. Beyazlar açık, siyahlar kapalı noktaları gösteriyor. Sonra alt ve üst arasında bir bağlantı sağlanıncaya kadar rastgele noktaları açıyoruz. Böylece beyazlardan oluşan yukarıdan aşağıya rastgele bir yol yapmış oluyoruz.

http://www.programlama.tk/resim/resim/montecarlo.png

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (erdem):

O zaman benim heyecanım yersizmiş. :) Ben şimdilik bize en yavaş işleyen algoritmayı gösteriyorsun sanmıştım. Ağaç kullanıyorsa hızlıdır, değil mi?

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Ben hala bu algoritmanın gerçek hayatta (pratikte) ne işe yarayacağını anlayamadım. Tamam, elektronikte baskılı devre hazırlamada (PCB routing) kullanılabilir gibi görünüyor; hoş, önceki sayfadaki sadeleştirilmemiş ve sadeleştirilmiş siyah/beyaz kutular (hatta bunlar aynı!) arasındaki farkı da göremedim ya... :blush:

Neyse, bunlar benim anlayışımın kıt oluşundan kaynaklanmakta. Bana belki üç yaşındaki çocuğun anlayabileceği dilde anlatabilirtsiniz...:)

"Bak yavrum, sobanın çevresinden geçersen belki bu vakit alacak ama bil ki hiç bir yerin cız olmayacak! O yüzden ortasından geçme. Ortada kuyu var yandan geç...:D"

Alıntı (acehreli):

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

Baskılı devre üzerine lehim yerleştiren bir robot için program yazıyorsun. Giren bilgiler, hangi iki noktanın bağlı olması gerektiğini söylüyorlar. Örneğin 3,4 geldiğinde "3 ile 4 arasında elektriksel bir bağlantı olmalı" anlamına geliyor.

Senin işin, o noktalar arasında mevcuk bağlantı yoksa robota lehim yerleştirtmek, uzun bir yoldan da olsa bağlantı zaten var ise lehim yerleştirmemek.

Pratikte başka bir oyunda da kullanılabilir: Bombanın düştüğü noktanın rastladığı adadaki bütün evler yıkılacak. Siyah beyazlı resimler buna benziyor: Beyazlardan oluşan adalar gibi.

Alıntı:

Bağlı liste düğümlerinin belleğin her tarafında bulunmaları nedeniyle mikroişlemcinin ara belleğinin dışına çıkmak zorunda kaldıkları için dizilerden daha yavaş kalacaklarını konuşmuştuk.

Alıntı:

Evet.

Ağaç O(log N) karmaşıklıkta arama yapan bir veri yapısı olduğundan bu problem için gayet iyi. Ben onu demek istedim.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (erdem:1348152793):

Çok ilginç aslında Monte Carlo bir integral alma yöntemiymiş.

Örneğin bizden pi sayısını hesaplamamızı istiyorlar.

http://farm8.staticflickr.com/7433/10711729515_d3a462c363_o.png

Birim çemberin alanının pi olduğunu ve çeyreğinin alanının da pi/4 olduğunu bildiğimiz için çeyrek çemberi kullanıyoruz.

Burada rastgele noktalar koyuyoruz. Daha sonra çemberin içine düşen noktalarla toplam noktaların oranını buluyoruz. Örneğin 10 nokta koymuşsak ve bunlardan 9 tanesi çemberin içine düştüyse

çemberin içine düşen nokta / toplam nokta = 0.9

olmuş oluyor.

Peki noktanın çemberin içinde olduğunu nasıl anlıyoruz.

(x,y) noktamız olsun. Çemberin denklemi x^2 + y^2 idi hatırlayacağınız üzere. Yarıçapı 1 olan çember kullandığımız için x^2+y^2 <= 1 ise nokta çemberin içinde değilse dışında oluyor.

Bu şekilde örneğin 1.000.000 kadar nokta oluşturduğumuzda çemberin içine dışına düşen noktaların oranı 0.786054 gibi bir rakam çıkıyor. Bunu dörtle çarptığımızda

pi = 4 * 0.786054 = 3.144216 gibi bir rakam çıkıyor.

Bahsettiğim gibi Monte Carlo bir tümlev alma yöntemi olduğu için tümlevi alınabilen tüm işlevlerle kullanabiliyoruz. Diğer yöntemlerle kolayla tümlevi alınamayan, ya da hesaplanması güç katlı tümlev hesabında Monte Carlo integrali kullanılıyor.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]