Dünyanın En Güzel Cot(x) Fonksiyonu

Geçen gün bizim evde dünyanın en süper cot(x) fonksiyonunu çizmiş bizim kız (sol kol biraz bozuyor gibi ama tecrübesizliğine verdim) :) .

Fonksiyonlarla dans figürlerinin hepsini bizim kıza çizdirmeye karar verdim. Denk geldikçe eklerim artık buraya :) .

IMG-20150622-WA0003

Do You Know What Time It Is?

Birkaç gün önce Marvel Civil War serisine başladım. Epey keyifli görünüyor.

Bu da çizgi romanların bir tanesinden bir sayfa. Tony Stark'ın Peter Parker'a öğütlerinden bir tanesi. Avukatlar için söylemiş ama yazılım dünyasından kime uyarlarsan tutuyor :)

time

K-Means

Dün biri bana "şirkette yazdığım en karmaşık algoritma k-means yea" diye hava attı. Düşündüm de şimdiki işimde kullandığım en karmaşık algoritma DFS. O da abuk subuk bir yerde. Altta kalmamak için ben de k-means yazayım neyim eksik dedim :) .

K-means bir çeşit sıkıştırma algoritması olarak da kullanılabiliyor, Bishop'un kitabında örneği de var. Eğer bir resmi k-means ile sıkıştırmak istiyorsak standart k-means'i pikseller üzerinde tek boyutta uygulayabiliriz. Yanlış hatırlamıyorsam Bishop kitabında her bit için uyguluyordu, sadece 3 renk için uygulamak daha kolayıma geldi :) .

Elimizdeki resim şu olsun (kaynak);

ironman

K=2 ile sıkıştırdığımızda elimizdeki resim aşağıdaki gibi olacak;

ironman_k_2

K arttıkça resmin orijinale yaklaşmasını bekliyoruz. K=5 ile sıkıştırdığımızdaysa resim aşağıdaki gibi olacak;

ironman_k_5

Ben kendime C#'ta k-means yazmadı dedirtmem! :) (Bu arada cidden Python'daki list comprehension'lar hayat kurtarıyormuş, bir kez daha anlamış oldum).

Software Transactional Memory ve .NET

Software Transactional Memory (STM), veritabanlarında bulunan transaction yapısının avantajlarını kullanarak kodun herhangi bir parçasında transaction bütünlüğünü sağlayabileceğimiz bir mekanizma. STM'yi direkt olarak kullanabildiğimiz diller (Clojure) olabileceği gibi, Java, C# gibi dillerde de farklı kütüphaneler ile STM desteğini sağlayabiliyoruz. Örnek kodlarda, bulabildiğim en güncel C# STM kütüphanesi olan Shielded'ı kullandım.

Mesela elimizde aşağıdaki gibi bir kod olduğunu düşünelim;

Kod aslında counter 'ı 2 thread kullanarak \(2 \times 10^8\) yapmaya çalışıyor ama thread-safe olmadığı için her çalıştırmada rastgele ve beklenen değerden küçük sonuçlar verecek. Bunu düzeltmek için C#'ın bize sağladığı lock  yapısını kullanıyoruz.

Bu kod bize her seferinde doğru sonucu verecek. Basit bir durum olduğu için lock bloğunu rahatça kullandık. Peki eğer elimizde 2 counter varsa ne yapacağız? Yeni durumda counter1  eskisi gibi çalışsın, buna ek olarak da counter1'in 100'ün katını aldığı her değerde counter2'yi 1 arttıralım. 3. bir thread'le de counter2'yi teker teker arttıralım. Bu durumda kodu nasıl thread-safe yapacağız? Bir örneği aşağıdaki gibi;

Kodu daha basit yapmak için tüm işlemlerde mutex1 'i kullanabilirim ama bu doğru değil, counter2 'yi de bağımsız olarak arttırabilmem lazım. Bir counter daha ekleyince kod gereksiz yere karmaşıklaştı.

Burada alternatif olarak STM'yi deneyebilirim artık.

Son kod ile iç içe bir sürü lock kullanmadan işi hallettim.

Shielded bu kontrolleri dilin verdiği lock yapısı ile değil, nesnelere birer zaman etiketi atayarak ve her erişimde bunu kontrol ederek yapıyor. Nesnenin en son haline erişemediğimiz halde de verdiğimiz kod bloğunu baştan çalıştırıyor. Bu tekrar durumunu göz önünde bulundurarak, blok içindeki Shielded<>  olmayan nesnelere ve I/O gibi transaction dışı işlemlere güvenmemek gerekiyor. Yani, run2 'deki bloğun başına bir Console.WriteLine  yazarsak, her çalıştırmada konsola yazılan satır sayısı aynı olmayabilir.

Son olarak, Shielded kütüphanesi içinde Tree, HashSet, Dictionary gibi yapıların transaction ile çalışan hallerini bulmak da mümkün.

Moving AI

Moving AI, University of Denver'da bir yapay zeka çalışma grubu. Jump Point Search algoritmasının anlatıldığı makaledeki sonuçları incelerken denk gelmiştim ama açıkçası sitelerini detaylıca incelememiştim. Bir zamandır da yol bulma algoritmalarını denerken daha büyük ve ayrıntılı haritalar kullanma fikrim vardı. StarCraft harita dosyalarını falan indirdim ama formatları çok karışık diye kurcalamadım. Moving AI ise tam bu sorunuma çözüm oldu :) .

Grubun sitesinde çeşitli benchmark arşivleri var. Bu arşivlerde 512x512'lik düz haritaların yanında StarCraft, Baldurs Gate, WarCraft gibi oyunların da haritaları var. Haritalar basit bir text formatı şeklinde verilmiş. Su, ağaç, bataklık gibi temel gruplara ayrılmış. Haritaların dışında, her harita için algoritmaları test edebileceğimiz test senaryoları da mevcut. Kısacası nimet gibi bir yer :) .

Haritaları okuyup sadık yarim matplotlib'e çizdiren kodu yazdım, otomatik olarak test eden kısımları da yazıp algoritmaları daha ayrıntılı haritalarda test etmeye başlayacağım.

Haritaları matplotlib'de çizdirince aşağıdaki gibi görünüyor (orijinali) (yeşiller ağaçlık alan :) );

map