ctpop ve bitmapler

Bugün çok fantastik birşey gördüm, anlatmazsam ölürüm(uygun bir başlık düşünmem tüm yazıyı yazmamdan daha uzun sürdü o yüzden idare edin hehe).

Diyelim ki bir veri yapısı tasarlıyoruz, bir nodedan bir sürü başka nodea veya elemana pointerlar olacak. Bir yandan da bellek kullanımını minimum tutmak istiyoruz. Pointerları tutan arrayimizde hiç boş yer olmamalı.

Bir bitmap tutuyoruz. Büyük ihtimalle integer oluyor(Java primitive int tipi 32bit olmak zorunda mesela). Diyelim ki bu node'un n. indexine bir eleman/pointer ekleyeceksiniz. Bitmap ilk başta 0 tabii. Şu şekilde bitmap'de ilgili elemanı 1 yapıyoruz:

bmp = bmp | 1 << n

Buraya kadar herşey çok basit. Bu noktadan sonra bu bitmape göre 30. elemanın arrayde nereye denk geldiğini bulmamız lazım. Bunun için şu formülü kullanıyoruz:

ctpop(bmp & ((1<<n)-1))

ctpop, population count fonksiyonu, yani bir sayının iki tabanında gösterilişindeki 1 bitleri sayıyor. Bu Java'da Integer.bitCount fonksiyonu(öhm, static methodu) ile bulunabilir.

Birkaç deneme yaparak nasıl yaptığını anlayabilir ve kendimizi ikna edebiliriz:

In [2]: bmp = 0

In [3]: bmp |= 1 << 15

In [4]: ctpop(bmp & ((1<<15)-1))
Out[4]: 0

In [5]: bmp |= 1 << 21

In [6]: bmp |= 1 << 10

In [7]: ctpop(bmp & ((1<<10)-1))
Out[7]: 0

In [8]: ctpop(bmp & ((1<<15)-1))
Out[8]: 1

In [9]: ctpop(bmp & ((1<<21)-1))
Out[9]: 2

Eğer arraydeki n. yere bir eleman ekliyorsak, n'den itibaren arrayi bir kaydırmamız lazım. En büyük index her zaman arrayde de daha sonda oluyor.

Ne yaptığına bakalım. 25. elemanın arraydeki yerine bakarken, 1 << 25i hesaplıyorum ki bu aslında (2 tabanında) 1 ve yanına 25 tane 0 koymak demek. Daha sonra bu sayıdan 1 çıkararak, en sağdan itibaren(en anlamsız bitten itibaren) tüm 0ları 1 yapıyorum, ilk gördüğüm 1'i 0 yapıyorum, gerisine dokunmuyorum(bu şartlar altında geriye kalan tüm bitler 0 oluyor). Daha sonra bu sayı ile bitmap'i logical and(bazı yerlerde bitwise and diyor, aynı şeyler sanırım?) işlemine sokup ctpop yaptığımda, bitmap'de (1 << n)'den itibaren kaç tane 1 olduğunu saymış oluyorum ve bu da bana array'deki indeximi veriyor. Çok mantıklı.

Bu arada kullandığınız dile göre bu işlemi daha kolay bir şekilde yapabilirsiniz. Bazı diller(Java'da Integer.bitcount, Common Lisp'de logcount gibi) direkt olarak bitCount gibi fonksiyonlar sunuyor. Bir de ben Common Lisp'de hiç kaydır 1 çıkart falan demeden direkt "şu bitle şu bit arasında kaç 1 olduğunu say" şeklinde bir fonksiyon yazdım, bitwise trickler yapmadan, şöyle:

(defun ctpop (bitmap &key (start 0) (end 32))
  (logcount (ldb (byte (- end start) start) bitmap)))

Sıralama algoritmaları ve dillerin kendi sıralama fonksiyonları

Uzun uzun kod örnekleri yazmıştım ama bir yerden sonra sıkıldım. Bugün öğrendiğim birkaç şeyi özet geçeyim:

• Sort işlemini lazy olarak yapmak süper. Çoğu zaman tüm dizinin sıralı haline ihtiyaç duymuyoruz ve bu şekilde arama yapmak karşılaştırma/fonksiyon çağrı sayısnı çok azaltıyor. Yine önce dilin sağladığı imkanları denemekte yarar var. Örneğin kendi yaptığım testlerde, 1000 elemanlı bir diziyi Python'ın sorted() fonksiyonu ile sıralamam, lazy bir quicksort(generator ile) yazıp az hesap yapmamdan 10 kat daha hızlı oldu. İnanılmaz(bu fark tabii ki eleman sayısı arttıkça açılacaktır).

• Aynı şey Clojure için de geçerli. Lazy sort yazacağım diye uğraşmaktansa, builtin sort fonksiyonu ile sıralayabilirsiniz. Kendi yaptığım testlerde, içi Integer dolu diziyi Clojure'un sort fonksiyonuyla çok bariz bir şekilde daha hızlı sıraladım(tabii bu biraz da sıraladığım elemanların Integer olmasıyla alakalıydı sanırım, kodu takip ettiğimde, bu seq'in önce Object[] array'ine dönüştürülüp, karşılaştırma sorasında da her bir elemanın double'a cast edilerek karşılaştırdığını gördüm, bunların çoğu Clojure ile değil Java ile yapılıyor).

• Timsort diye bir sıralama algoritması var. İlk olarak Python için yazılmış. Şu anda Python, Java SE 7 ve Android'de kullanılıyor. Bu hızın kaynağı sanırım bu algoritma.

• Python'da fonksiyon çağrıları çok masraflı. Denemek için bir quicksort algoritmasını binlerce elemanlı bir listede, her karşılaştırma için bir fonksiyon çağırarak ve bir bir builtin Python operatorunu kullanarak(bu operatorlerin de sonuca __gt__ veya __lt__ gibi fonksiyonları çağırdıklarının farkındayım, ama sonuçta testlerimde fonksyion çağrı sayısını arttırdım) denedim. Performans farkı çok bariz. Filter, map gibi higher-order fonksiyonlar list comprehension'lardan performans açısından çok farklı değiller ama(bkz. ilgili SO başlığı). Haftalar sonra gelen düzenleme: Dropbox ekibi bloglarında küçük bir Python kodunun hızlandırılması hakkında şöyle güzel bir yazı yazmış. Sadece fonksiyon çağrısını kaldırarak %15 performans artışı elde etmişler. Bunun gibi daha bir sürü ipucu var. Mutlaka okuyun.

Şimdilik bu kadar.

Clojure ve bir 4Clojure problemi

Clojure(ve genel olarak Lisp dilleri) ile bir süredir ilgileniyorum, canım sıkıldıkça 4clojure'daki problemleri çözüyordum(bu arada Clojure'a başalyan herkese tavsiye ederim, sitenin en güzel yanı, problemi çözdükten sonra başkalarının çözümlerini görebiliyorsunuz, ve çoğu zaman problemi çözmüş birkaç Clojure geliştirici/katkıcısı bulabiliyorsunuz). Bir süre sonra, artık temellerini kavradığımı düşündüğümde, şu ana kadar en az çözülen probleme, 'For Science!'a bir bakayım dedim. Problem tanıdık geldi. Bu problemin bir benzeriyle ilk kez şurda bahsettiğim programlama yarışmasında karşılaşmış, ve o zaman soruya saf saf bakmaktan başka birşey yapamamıştık. Daha sonra, ilk başta alakasız gibi gözüksede, aslında çok benzeyen bir halini, üzerinde çalıştığım bir oyunun yapım aşamasını kolaylaştırmak için çözmüştüm, ilgili yazı şurda.

Alternatif bir yöntem düşünmeden hemen daha önceden çözdüğüm gibi çözmeye başladım. Çözen Python kodunu birkaç dakika içerisinde yazdım. Algoritmam şu şekilde: gezilebilir olup birbirlerine komşu olan tüm alanları grupluyorum, daha sonra eğer başlangıç ve hedef aynı grupdaysa, birbirlerine erişebilirler demektir.

Python koduyla açıklamak daha kolay:

pos_m = None
pos_c = None

groups = []

Burda pos_m, problemdeki fare(mouse - M)nin başlangıç noktasını temsil ediyor. Alanı gezerken fareyle karşılaştığımızda bunu atayacağız. Aynı şekilde pos_c de peynir(cheese)in yeri.

groups da birbirlerine komşu olan tüm noktaların oluşturduğu grupları tutacak.

def check_adjacency(pos, x, y):
    difx = abs(pos[0]-x)
    dify = abs(pos[1]-y)

    return (difx == 1 and dify == 0) or (difx == 0 and dify == 1)

Bu fonksiyonun yaptığı, bir (X, Y) ikilisinden oluşan noktanın, (x, y) noktasına komşu olup olmadığını dönmek. Burda komşu olma şartı, iki noktanın üst üste veya yan yana bulunmaları(haritada çarpraz ilerleme olmadığından, çarprazdakiler komşu sayılmıyor).

def find_groups(x, y):
    r = []
    for group in groups:
        for pos in group:
            if check_adjacency(pos, x, y):
                r.append(group)
                break
    return r

find_groups, (x, y) noktasının komşu olduğu grupların bir listesini dönüyor. Örneğin bir aşamada elimizde [(1, 1), (2, 2)] ve [(2, 4)] grupları varsa ve biz (2, 3) noktasının komşu olduğu grupları arıyorsak, bu iki grupu bize döndürecek. Bu durumda bu iki grupu birleştirmemiz gerekcek çükü artık bu ikisi birbirine (2, 3) ile bağlı.

def merge_groups(grps):
    for group in grps[1:]:
        grps[0] += group
        groups.remove(group)

Birleştirme işlemini de bu yapıyor işte.

Bundan sonrası basit zaten, teker teker gez, grupları bul, grup yoksa yeni oluştur, varsa onu genişlet, birden fazlaysa birleştir. Kodu takip etmek için kullandığım print statement'larını silmeden koyuyorum:

for y in xrange(len(test_grid)):
    for x in xrange(len(test_grid[0])):
        char = test_grid[y][x]
        print x, y, char,
        if char == '#':
            print "block"
        else:
            if char == 'M':
                pos_m = (x, y)
            elif char == 'C':
                pos_c = (x, y)

            grps = find_groups(x, y)
            if len(grps) > 1:
                merge_groups(grps)
                grps[0].append((x, y))
                print "merge"
            elif len(grps) == 0:
                groups.append([(x, y)])
                print "new group"
            else:
                grps[0].append((x, y))
                print "append"

print pos_m, pos_c
for group in groups:
    if pos_m in group and pos_c in group:
        print "M can reach C"

Çok da güzel bir kod olmayabilir(örneğin liste içinde listelerde lineer arama yerine, set kullanılabilir, Clojure kodumda yaptığım gibi) ama problemi hızlıca çözmek için işimi gördü.

Fonksiyonel programlama yolunu henüz çözebilmiş değilim. Hala daha çoğu zaman yaptığım, bir algoritmadaki değişen durumları(state) bir loop içine alıp, tail-call yapmak(Clojure'da recur yani, bu arada recur'un tail-call optimization olmadığının farkındayım).

Yukarıdaki Python fonksiyonlarının Clojure karşılıklarını şu şekilde yazdım:

(defn abs
  "Absolute value of n"
  [n]
  (if (neg? n)
    (- n)
    n))

(defn check-adjacency
  [[posx posy] x y]
  (let [difx (abs (- posx x))
        dify (abs (- posy y))]
    (or (and (= difx 1) (= dify 0)) (and (= difx 0) (= dify 1)))))

(defn find-adjacent-sets
  [sets [x y]]
  (set (filter (fn [set]
                 (some (fn [p]
                         (check-adjacency p x y))
                       set))
               sets)))

(defn get-char
  [grid [x y]]
  (get (grid y) x))

Daha sonra bunları kullanarak problemin çözümü:

(defn can-reach?
  [grid]
  (let [rang (for [y (range (count grid)) 
                   x (range (count (first grid)))] [x y])]
    (loop [positions rang
           sets #{}
           posm nil
           posc nil]
      (if (nil? positions)
        (let [m-set (first (filter #(% posm) sets))
              c-set (first (filter #(% posc) sets))]
          (= m-set c-set))
        (let [pos (first positions)
              ch (get-char grid pos)
              adj-sets (find-adjacent-sets sets pos)
              set-count (count adj-sets)]
          (if (not= ch \#)
            (recur (next positions)
                   (conj (difference sets adj-sets) (union (apply union adj-sets) #{pos}))
                   (if (= ch \M) pos posm)
                   (if (= ch \C) pos posc))
            (recur (next positions)
                   sets
                   posm
                   posc)))))))

4clojure çözümlerde birden fazla fonksiyon kabul etmediğinden, tüm yardımcı fonksiyon tanımlarımı ana fonksiyonumun içine almam gerekti. 4clojure'a yolladığım çözüm şurda.

Clojure hakkında karmaşık duygular içerisindeyim(eheh, bir programlama dili hakkında böyle bir cümle kurmak). Pek çok ileri-seviye özelliklerini henüz bilmiyorum. Fonksiyonel programlamayı da, yukarıda bahsettiğim gibi, henüz çözebilmiş değilim. Macroları şu ana kadar hiç kullanmadım. Bu dönem sonuna kadar SICP'in ilk 3 bölümünü bitirip, tüm alıştırma çözümlerini yayınlamayı planlıyorum(ilk bölüm bitti, ikincisi bitmek üzere, birkaç alıştırmayı çözemedim gerçi). Daha sonra McCarthy'nin ilk Lispini bir dilde(büyük ihtimalle C olacak) implement ettikten sonra muhtemelen type theoryye dalmak için Haskell(veya daha uygun başka bir Lisp dili) ile uğraşacağım(sonunda muhtemelen bu dediklerimin yarısını falan yapmış olacağım ama olsun eheh).

Bu arada birşey farkettim, bir süredir çeşitli programlama problemleriyle ilgileniyorum, bir de yarışma tecrübemiz oldu ve C ile katıldık. C böyle bir iş için seçilebilecek en kötü alternatif. C'de elinizden hiçbir veri yapısı ve veri yapıları üzerinde işlemler yapabileceğiniz hiçbir fonksiyon yok. Çoğu zaman Java, C++ ve Python gibi alternatifler de oluyor bu gibi problemlerde. Java'da zaten elinizin altında yüzlerce sınıf var. C++'da STL var, Python'da zaten bir sürü builtin veri yapısı var. C ile ne gerekiyorsa yazmak zorundasınız. Aslında bu gibi yarışlamarda daha adil olması açısından C kodlarını glib ile derleyebilirler. Performans deseniz, çoğu zaman takıldığınız nokta performans olmuyor(eğer problemi C++ veya en kötü ihtimalle Java ile çözmüşseniz). Kısaca, C ile çözmeye çalışmayın, en azından biraz STL bilip, C++ ile çözülebilir.

Pygame ve düzensiz sprite sheetlerle çalışmak

Pazartesi günü başlayacak Pyweek'e katılacağım, benim ilk oyunum olacağından daha en temel problemler bile benim için yeni, ve çözümlerini yavaş yavaş keşfediyorum. Birkaç gündür basit oyunlar yapıyorum ve iş bir yerden sonra animasyonlara geldi.

2d oyunlarla ilgilendiyseniz, animasyonların aslında sprite adı verilen png/gif/vs. dosyalarından oluştuğunu bilirsiniz. Animasyonlar çoğu zaman(AAA oyunladan bahsetmiyoruz tabii ki) birkaç kareden oluşuyor ve bunlar genelde tek bir dosyaya aralıklarla yerleştirilmiş oluyorlar. Bunlara sprite sheet deniyor. Örneğin bir karakter koşuyorsa, ilk kare, yukarıdan 100, soldan 50. pixelden itibaren, 40px yüksekliğinde ve 30px genişliğinde oluyor. Bir sonraki kare onun biraz yanında vs. Bu şekilde çalışmak gayet kolay oluyor. Bir kere büyük resmi yükledikten sonra, ondan subsurfacelar oluşturuyorsunuz. Peki neden ayrı ayrı resimler değil? Bunun hakkında iki güzel kaynak: 1, 2.

Çizim işinden hiç anlamadığımdan, sprite sheetleri genelde deviantart'dan ediniyorum. Fakat şu ana kadar basit bir şekilde kullanılabilir bir sprite sheet görmedim. Sprite sheetleri basitce ayrıştırmak için en azından spriteların resim üzerinde eşit aralıklarla falan bölünmesi lazım. Benim bulduklarımın hiçbiri bu şekilde değil. Ne eşit aralıklılar, ne de eşit boyutlu. Tüm kareleri tespit edebilmek için, ya elle ölçecektim, ya da benim için ölçecek bir program yazacaktım :) .

Tabii ki program yazdım. Aşağıda nasıl çalıştığının bir örneğini görebilirsiniz. Gösterdiğim sprite sheet'i tarayıp, birbirlerinden ayrılmış tüm parçaları bulup işaretliyor, mouse ile üzerine geldiğinizde, koordinatlarını ve boyutlarını yazıyor. Bunu sadece Pygame kullanarak yapıyor.(büyültmek için üzerine tıklayın)

Biraz da işin en zevkli kısmından, problemin çözümünden ve algoritmadan bahsedeyim. Program şu şekilde çalışıyor:

Her bir pixel için, eğer pixel colorkey'e eşit değilse(colorkey saydam olacak kısmın rengi ve derinliği oluyor), pixelin içinde olduğu veya komşu olduğu grubu ara. Burda grup bir pygame.Rect. Yani dikdörtgensel bir alan. Eğer bu pixeli içeren bir grup yoksa, bu pixeli içeren en küçük Rect'i gruplara ekle. Eğer piksel Rect'in içindeyse, birşey yapma, komşuysa, Rect'i o pixeli kapsayacak şekilde büyült. Eğer bir pixel birden fazla gruba komşuysa(veya içindeyse), bu iki grubu birleştir. Grupların son hali de ekran görüntülerinde gördüğünüz kırmızı alanlar. Aşağıda bir de Travis Touchdown(No More Heroes'dan) sprite sheeti üzerinde çalışmasını görebilirsiniz.

Böyle işte. Scripti şurdan görebilirsiniz. Konuyla alakalı her türlü algoritma öneri/tavsiye/eleştirisine açığım. Hatta mutlu olurum yani, acımasızca eleştirin lütfen :) .

Arduino ile ilk denemeler

Dün ilk Arduino'm elime geçti. Ne olup bittiğini biraz kavradıktan sonra bugün ilk denemelerimi yapmaya başladım. Aşağıdak, Python ile Arduino'ya serial port üzerinden komut gönderme denemelerimin ilki:

Arduino'nun yaptığı, serial port'u dinleyip, gelen verinin 0'dan büyük bir takam olduğunu varsayarak(val -= '0'), bu veriye göre ledleri yakıp söndürmek.

#define ledPin1 13
#define ledPin2 12
#define ledPin3 11

int val = 0;

void setup() {
    pinMode(ledPin1, OUTPUT);
    pinMode(ledPin2, OUTPUT);
    pinMode(ledPin3, OUTPUT);
    Serial.begin(9600);
}

void loop () {
    if (Serial.available()) {
        val = Serial.read();
        val -= '0';

        if (val == 1) {
            digitalWrite(ledPin1, HIGH);
        } else if (val == 2) {
            digitalWrite(ledPin2, HIGH);
        } else if (val == 3) {
            digitalWrite(ledPin3, HIGH);
        } else if (val == 4) {
            digitalWrite(ledPin1, LOW);
        } else if (val == 5) {
            digitalWrite(ledPin2, LOW);
        } else if (val == 6) {
            digitalWrite(ledPin3, LOW);
        }
    }
}

Python ve Pygame ile de klavyeyi izleyip, tuşların basılması veya bırakılması durumlarında serial port'a gerekli verileri gönderdim:

import serial
import pygame

s = serial.Serial('/dev/ttyACM2', 9600)
screen = pygame.display.set_mode((100, 100))
clock = pygame.time.Clock()

keydwn = {pygame.K_LEFT : "1",
          pygame.K_RIGHT: "2",
          pygame.K_DOWN : "3"}

keyup  = {pygame.K_LEFT : "4",
          pygame.K_RIGHT: "5",
          pygame.K_DOWN : "6"}

running = 1
while running:
    screen.fill((00, 00, 00))
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            s.write(keydwn.get(event.key, ""))
        elif event.type == pygame.KEYUP:
            s.write(keyup.get(event.key, ""))

    time = clock.tick(30)

İlk deneme için gayet basit ve güzel :) . Aslında amacım, Python ve Pygame ile yaptığım şeyleri Clojure ile(Pygame kısmı için AWT gerekecekti sanırım) yapmaktı ama sırt ağrım bir yerden sonra dayanılmaz hale geldi(zaten çalışma ortamım rahat değil, bir de Arduino için masaya eğilince) ve bir an önce bitirmeye çalıştım. Bundan sonraki denemelerimi Clojure ile yapmaya çalışacağım.

Onun dışında, Arduino kodunu Pardus ortamında bir türlü derleyemedim, gerekli kütüphaneler/bağımlılıklar yüzünden. Bir ara onunla uğraşacağım.