Listenin transpozunu almak

Grid gibi, aynı tipten verinin çok fazla sekilde tekrarlandıgı durumlarda, serialization esnasında yazılan metadata yükünden dolayı veriyi taşımak problem olabiliyor.

Misal aşağıdaki gibi bir Row sınıfının olduğunu düşünün;

Sadece Row sınıfı elemanlarından oluşan bir listeyi JSON'a çevirip göndermeye çalıştığımızda elimizdeki mesaj aşağıdaki gibi bir standart JSON mesajı olacak.

Eğer dediğim gibi, göstereceğimiz veri standart bir Row listesiyse, yani Row sınıfından türeyen herhangi bir sınıfın nesnesini barındırmıyorsa, mesaj içinde sürekli tekrarlanan alan adlarından kurtulmak için listenin transpozunu alabiliriz.

Listenin transpozunu almanın lineer cebirde matrisler üzerinde uygulanan transpoz işleminden bir farkı yok aslında. Örneğin nasıl ki

\[M = \begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}\]

şeklindeki bir matrisin transpozu

\[M^T = \begin{pmatrix}1 & 3 \\ 2 & 4\end{pmatrix}\]

ise, yani satırlarla sütunlar yer değiştiriyorsa liste üzerinde de aynı işlemi yapacağız.

Obje Col1 Col2 Col3 Col4 Col5
Obj1 Column1 Column2 Column3 0 0
Obj2 Column1 Column2 Column3 1 3.1415926535897931

şeklindeki bir obje listesinin transpozu

Obj1 Obj2
Col1 Column1 Column1
Col2 Column2 Column2
Col3 Column3 Column3
Col4 0 1
Col5 0 3.1415926535897931

olacak. Böylece artık her satırda nesne yerine primitif listesi gönderebiliriz.

Aşağıdaki kod basit bir şekilde bu işlemi yapıyor.

Artık göndereceğimiz veri aşağıdaki gibi

Böylece, eleman sayılarına göre mesaj boyutlarındaki değişim aşağıdaki gibi olacak.

Eleman Sayısı Normal(byte) Transpoz(byte)
2 162 133
1000 89674 52719
10000 906712 536757
100000 9167843 5467888

Dolu tabloların iletiminde bu yöntem etkin bir çözüm sağlıyor. Boşa yakın (sparse) tablolarda ya da değişik obje tipleri içeren durumlarda ise çok fazla bir yarar sağlamayacaktır.

Paralel JSON Parser

List, Map gibi, elemanları paralelde ayrı olarak işlenebilecek veri yapılarının birden fazla thread'le işlenebileceği ile ilgili bir fikir vardı aklımda bir zamandır. Şirketimiz sağolsun bana zorunlu olarak "Design Patterns" eğitimi atayınca ben de eğitimde kendime ayırdığım boş zamanların bir kısmında paralel çalışan bir JSON parser yazmayı deneyeyim dedim :)

Kodun, README'de de görülebileceği üzere, epey bir eksiği var. Hatta işe yarar bir koddan daha çok bir taslak diyebilirim. Fakat bu haliyle bile denediğimde yine de fena çalışmadığını görüyorum (1.000.000'luk bir Map objesinde JVM OutOfMemoryException falan atıyor ama olsun :)). Fırsat buldukça geliştirmeye çalışacağım, belki işe yarar bir şey çıkar sonunda.

https://github.com/ocozalp/ParallelJSON

heapq: Python'da heap veri yapısı

Heap veri yapıları, kısaca tanımlamak gerekirse, her node'un kendi çocuklarından daha büyük değere (ya da daha büyük önceliğe) sahip olduğu, ağaç veri yapılarıdır denilebilir. Aşağıdaki örnekte bu sıralama küçükten büyüğe yapılmıştır.

300px-binary-heap

 

Heap'ler, diğer algoritmalardaki (örneğin Dijkstra) kullanımlarının dışında, PriorityQueue gibi veri yapılarında da kullanılır.

Heap üzerinde kullanabileceğimiz işlemler aslında temelde 3 adettir;

  • heapify: Bir diziyi heap özelliğini sağlar hale, yani her elemanı kendi çocuklarından büyük olduğu duruma getirir.
  • pop: En büyük elemanı döner.
  • push: Heap'e yeni bir eleman ekler.

Python'da bu 3 işlevi karşılayan ve heap işlemlerini gayet kolayca yapmamızı sağlayan heapq adında bir modül mevcut. Modül epey küçük, testiyle commentiyle 500 satır falan ama graph algoritmalarıyla falan uğraşıyorsanız gayet gereksiz bir ayrıntıdan sizi çok güzel kurtarıyor.

Modülün içindeki tüm metodlar dışarıdan verilen bir dizi üzerinde çalışıyor. Bilinmesi gereken bir ayrıntı, dizide eğer primitive tipler ya da tuple'lar tutmuyorsak, yani kendi yazdığımız bir sınıftan nesnelerin bir arrayini heap'e çevirmeye çalışıyorsak, sınıf içinde __lt__ metodunun yazılması gerekiyor.

Örneğin yukarıdaki resimdeki dizinin orijinal halinin [10, 7, 9, 2, 1, 8] şeklinde olduğunu düşünelim.

 

 

Bu diziyi heap haline getirmek için heapify metodunu kullanıyoruz. Bu metod diziyi bir heap'e çeviriyor, görüldüğü gibi her n. eleman 2*n ve 2*n+1 elemandan daha küçük (heapq heap'lerinin değişik bir tarafı min-heap olması yani diziyi küçükten büyüğe sıralaması).

 

Dizinin en küçük yani en önemli elemanını almak için heappop metodunu kullanıyoruz. Normalde bu elemana arr[0] şeklinde de erişebiliriz ama bu metod ilk elemanı heapten çıkarıp heap'i tekrar düzenliyor.

 

Heap'e eleman eklemek için ise heappush metodunu kullanıyoruz.

 

heapq'da, tüm işimizi görecek bu temel metodların dışında, nlargest, nsmallest, heappushandpop gibi işimizi kolaylaştıran ve temel metodları kullanarak yapılabilecek metodlar da mevcut.

Kısa bir soru

Arada bir teknik mülakatların sorularını inceliyorum. Bazıları basit olsa da nedense bir hoşuma gidiyor. Bu da onlardan bir tanesi :)

Bu soruyla bir tane teknik mülakatta karşılaşmıştım. Sonrasında mülakat sorularını incelerken bir yerde daha denk geldim. Sorunun kendisi gayet kısa, verilen bir dizide toplamları N'e eşit olan alt dizilerin sayılarının bulunması isteniyor.

Misal elimizdeki dizi [1, 23, -5, 7, 21, 3, 3, 2, -5], toplam olarak istenen N değeri de 23 olsun.

En basit çözüm olarak aşağıdaki çözüm verilebilir.

 

Bu çözüm tüm index çiftleri için toplamı hesaplayıp, toplam N'e eşitse sonucu 1 arttırıyor. \(O(n^3)\)'lük bir çözüm, bu yüzden büyük diziler için çok da güzel bir çözüm değil. Aşağıdaki çözüm ise kümülatif toplamları tuttuğundan çözümü en içteki for'dan kurtarıyor ve complexity \(O(n^2)\) oluyor.

 

Bu iki çözümü de \(O(n)\)'e yaklaştırmak istiyoruz. Kümülatif toplamları hesapladığımıza göre, totals dizisinin i. elemanı için yapmamız gereken (aslında 2. çözümde de yaptığımız) kümülatif toplamı totals[i] - N olan elemanların sayısını bulmak. Bunun içinse tekrar tekrar lineer arama yapmamıza gerek yok.

 

Son çözümde, her kümülatif toplamdan önceki toplamları bir hashtable'da tuttuk. Böylece, istenen değerlerinin sayısını O(1) zamanda hesaplayabiliyoruz. \(O(n)\) zaman da diziyi dolaşmakla geçiyor ve son çözümün complexity'si \(O(n)\) oluyor.

Umarım bir hata yapmamışımdır :)