Fiber'ın Türkçesi

April 16, 2015

Fiber'ın Türkçesi

Posted by Ali Çehreli (acehreli)
in reply to agora

Permalink

Ali Çehreli (acehreli)

Posted in reply to agora

Permalink

Açıklamak isterdim ama şu sıralar fazla zaman bulamıyorum. Hem konuyu da biraz daha toparlamış olmak istiyorum.

Ama aslında çok basit bir konu: Normalde her iş parçacığı (thread) için tek adet bulunan çağrı yığıtından (call stack (ben "program yığıtı" da diyordum)) birden fazla bulunmasını sağlıyor.

Multi-threading (birden fazla iş parçacığı) ile değil, multi-tasking (birden fazla görev) ile ilgili.

Aşağıdaki programın tek ve ana iş parçacığı (yani, main() ile başlayan iş parçacığı) hangi noktada işlemekte olduğunu otomatik olarak yönetilen çağrı yığıtı sayesinde bilir:

void main()
{
   int a;
   int b;

   int c = foo(a, b);
}

int foo(int x, int y)
{
   bar(x + y);
   return 42;
}

void bar(int param)
{
   string[] arr;
   // ...
}

main foo'yu, foo da bar'ı çağırdığında çağrı yığıtında bu üç işlevin yerel bilgileri (yerel değişkenler, parametreler, vs. gibi yaşam süreçleri otomatik olarak yönetilen değişkenler) kavramsal olarak üst üste tutulur:
'
Çağrı yığıtı kavramsal olarak ▲ ▲
yukarıya doğru büyür. | |

        yığıtın üstü → +--------------+
                       | int param    | ← bar'ın yerel bilgisi
                       | string[] arr |
                       +--------------+
                       | int x        |
                       | int y        | ← foo'nun yerel bilgisi
                       | return value |
                       +--------------+
                       | int a        |
                       | int b        | ← main'in yerel bilgisi
                       | int c        |
        yığıtın dibi → +--------------+

'
bar'dan dönüldüğünde yığıt kısalır ve artık yalnızca main'in ve foo'nun bilgileri vardır.

Fiberler (fiber, coroutines, green threads, vs.) bundan birden fazla bulunmasını sağlar çünkü her fiber kendi çağrı yığıtı bulunan bir işçiktir :).

Kullanım örneklerinden en tanınmış olanı, same fringe problem olarak biliniyor: Elimizde iki adet sıralı ağaç (binary search tree) bulunsun. Bunların saçak elemanları (fringe'leri), yalnızca en dipteki elemanlardır; yani, ağacın üst tarafındaki düğümlerdeki elemanlarla ilgilenmiyoruz. Yalnızca en aşağıdaki ve kendilerinden başka dal çıkmayan elemanlara bakıyoruz. Eğer verilen iki ağacın saçak elemanları aynı sırada ve aynı değerde ise bunların aynı saçağa (same fringe) sahip olduğu söylenir.

Bu algoritmayı nasıl yazarsınız? Tabii, olabildiğince hızlı olmak da istiyoruz: Örneğin, her ağacı ayrı ayrı gezip saçakları bir dizide toplayıp sonra dizileri karşılaştırmak istemiyoruz çünkü o zaman N + M adet işlem yapmış oluruz. Oysa, belki de ilk saçak elemanlarının farklı olduğu bir durumdayızdır. O zaman hemen "saçakları eşit değil" diyebilmek isteriz.

Algoritmanın zorluğu, birden fazla ağacın aynı anda ilerlenmesinin gerekiyor olması. İşin garibi, tek ağacın saçaklarını gezmek çok kolay çünkü ağaçlar özyinelemeli veri yapıları olduklarından özyinelemeli algoritmalara çok uygundurlar. Örneğin, şu ağacın üye işlevlerinin güzelliğine bakın. :) ekle(), yazdır(), ve saçakları() hep özyinelemeli olarak yazılabilmişler:

(Program dmd 2.067 gerektiriyor çünkü std.algorithm.each'i kullandım: map gibidir ama her elemana karşılık yeni bir değer üretmek yerine her elemana karşılık bir yan etki üretmek için kullanılır.)

import std.stdio;
import std.string;
import std.conv;
import std.random;
import std.range;
import std.algorithm;

struct Düğüm
{
   int eleman;
   Düğüm * sol;    // Sol alt ağaç
   Düğüm * sağ;    // Sağ alt ağaç

   void ekle(int eleman)
   {
       if (eleman < this.eleman) {
           ekleVeyaKur(sol, eleman);

       } else if (eleman > this.eleman) {
           ekleVeyaKur(sağ, eleman);

       } else {
           throw new Exception(
               format("%s zaten mevcut", eleman));
       }
   }

   void yazdır() const
   {
       /* Önce sol alt ağaçtaki elemanlar */
       if (sol) {
           sol.yazdır();
           write(' ');
       }

       /* Sonra bu düğümün elemanı */
       write(eleman);

       /* En sonunda da sağ alt ağaçtaki elemanlar */
       if (sağ) {
           write(' ');
           sağ.yazdır();
       }
   }

   void saçaklarıEkle(ref int[] saçaklar) const
   {
       if (!sol && !sağ) {
           saçaklar ~= eleman;

       } else {
           if (sol) {
               sol.saçaklarıEkle(saçaklar);
           }

           if (sağ) {
               sağ.saçaklarıEkle(saçaklar);
           }
       }
   }
}

/* Elemanı bu alt ağaca ekler; 'null' ise düğümü ilkler. */
void ekleVeyaKur(ref Düğüm * düğüm, int eleman)
{
   if (düğüm is null) {
       /* Bu alt ağacın ilk elemanını ekliyoruz. */
       düğüm = new Düğüm(eleman);

   } else {
       düğüm.ekle(eleman);
   }
}

struct Ağaç
{
   Düğüm * kök;

   void ekle(int eleman)
   {
       ekleVeyaKur(kök, eleman);
   }

   void yazdır() const
   {
       if (kök) {
           kök.yazdır();
       }
   }

   int[] saçaklar() const
   {
       int[] saçaklar;

       if (kök) {
           kök.saçaklarıEkle(saçaklar);
       }

       return saçaklar;
   }
}

/* Ağacı (n * 2) adet sayı arasından seçilen 'n' adet rasgele
* elemanla doldurur. */
Ağaç rasgeleAğaç(size_t n)
{
   /* (n * 2) sayı arasından n adet seç. */
   auto sayılar = iota((n * 2).to!int)
                  .randomSample(n, Random(unpredictableSeed))
                  .array;

   /* Karıştır. */
   randomShuffle(sayılar);

   /* O sayıları içeren bir ağaç yap. */
   auto ağaç = Ağaç();
   sayılar.each!(e => ağaç.ekle(e));

   return ağaç;
}

void main()
{
   auto ağaç = rasgeleAğaç(10);
   ağaç.yazdır();
   writeln();

   auto saçaklar = ağaç.saçaklar();
   writefln("Saçakları: %s", saçaklar);
}

Şimdi iki ağaç yapın ve saçak elemanlarının aynı olup olmadıklarını olabildiği kadar kısa sürede bildirin. Örneğin, her iki ağacı ilk saçağa kadar ilerletin ve eşit değillerse işinizi bitirin.

Fiberlerin nasıl yararlı olduğunu sonra göstereceğim.

Ali

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

Forums