Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-44
1000 düğümde 3 kopya veriler
acehreli (Moderatör) #1
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: The Algorithm Design Manual, problem 2-44
1000 adet düğümde depolayacağımız 1000 adet verimiz var. Her düğüm tam olarak 3 farklı verinin kopyasını saklayabiliyor. Düğümler kaybedildiğinde (bozulduğunda) veri kaybını en aza indirecek olan bir depolama yöntemi öneriniz. Rasgele üç düğüm bozulduğunda kaç verinin kaybolacağı beklenmelidir?

Ali
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Biraz işin ucunu kaçırdım. :) Çözümlerin bu kadar kapsamlı olmaları gerekmiyor.

Her veriyi üç düğüme üç kopya olarak yazarsak iki düğüm bile kaybolsa hiç veri kaybetmeyiz. Üç düğümün bozulması durumunda da ancak talihsiz verinin üç kopyası kaybolduğunda veri kaybı yaşanır.

Yani, N'nin üçlü kombinasyonlarının sayısı kadar kayıp olasılığı arasından ancak N adedi herhangi bir veriyi kaybettirir. (Bu hesap main() içinde var.)

Aşağıdaki program her konumdaki veriyi Depo yapısının açıklamasındaki gibi çaprazlama saklıyor:
import std.stdio;
import std.random;
import std.range;
import std.exception;
import std.traits;
 
enum veriKopyaAdedi = 3;
 
/* Deponun düğümleri birden fazla sayıda veri saklayabiliyorlar. Düğümün
 * sağlam mı yoksa bozuk mu olduğu anlaşılabiliyor. (Bir enum yerine
 * std.digest.md modülündeki MD5 gibi bir olanaktan yararlanmak daha yakışıklı
 * olabilirdi. :) ) */
struct Düğüm
{
    enum Durum { bozuk, sağlam }
 
    Durum durum = Durum.bozuk;
 
    /* int yerine veri türünü şablon parametresi olarak almak daha kullanışlı
     * olurdu. */
    int[veriKopyaAdedi] veriler;
}
 
/* Depolama ortamındaki bozukluklara karşı güvenliği artırabilmek için her
 * veriyi üç farklı düğümde "çaprazlama olarak" depolar: Kendi konumunun
 * veri[0]'ı, bir sonraki konumun veri[1]'i, ve iki sonraki konumun veri[2]'si
 * olarak.
 *
 * Son iki konum için % işleci ile en baştaki konumları kullanması gerekir. */
struct Depo
{
    Düğüm[] düğümler;
 
    /* Her verinin kopyalarının birbirlerinden ne kadar uzak düğümlerde
     * oldukları. */
    size_t kopyaUzaklığı;
 
    /* Belirtilen uzunlukta boş bir depo oluşturur. */
    this(size_t uzunluk)
    {
        düğümler.length = uzunluk;
 
        foreach (ref düğüm; düğümler) {
            düğüm.durum = Düğüm.Durum.sağlam;
        }
 
        /* Böylece her verinin kopyasını birbirlerinden olabildiğince uzak
         * konumlara yerleştirmiş olacağız. */
        kopyaUzaklığı = düğümler.length / veriKopyaAdedi;
    }
 
    size_t length() const pure nothrow
    {
        return düğümler.length;
    }
 
    /* Konumun geçerli olduğunu denetleyen özel bir işlev. */
    private void konumDenetle(size_t konum) const pure
    {
        enforce(length > konum, format("%s uzunluğundaki depoda %s konumu"
                                       ~ " geçersiz.", length, konum));
    }
 
    /* Belirtilen konumdaki verinin belirtilen kopyasının konumunu
     * bildirir. */
    private size_t kopyaKonumu(size_t konum, size_t kopyaNumarası) const pure
    {
        return (konum + (kopyaNumarası * kopyaUzaklığı)) % length;
    }
 
    /* Veriyi belirtilen konuma yerleştirir.
     *
     * Hm. Konumu kullanıcı vermese ve depo gittikçe büyüse daha kullanışlı
     * olabilirdi. Problemin çözümüyle ilgisi olmayan bu kadar farklı bir
     * konuya dallanmasam da olur. :) */
    void ekle(size_t konum, int veri)
    {
        konumDenetle(konum);
 
        /* Veriyi birden fazla kopya olarak birden fazla düğüme yaz. */
        foreach (kopya; 0 .. Düğüm.veriler.length) {
            düğümler[kopyaKonumu(konum, kopya)].veriler[kopya] = veri;
        }
    }
 
    /* Belirtilen konumdaki veriyi okur. */
    int oku(size_t konum) const
    {
        konumDenetle(konum);
 
        /* Veriyi gerekiyorsa başka düğümlerdeki kopyalarından da okumaya
         * çalış. */
        foreach (kopya; 0 .. Düğüm.veriler.length) {
            const düğümNumarası = kopyaKonumu(konum, kopya);
 
            if (düğümler[düğümNumarası].durum == Düğüm.Durum.sağlam) {
                return düğümler[düğümNumarası].veriler[kopya];
            }
        }
 
        /* Buraya geldiysek bu konum için sağlam kopya bulamadık demektir. */
        throw new Exception(format("Depo, %s numaralı veriyi okuyamayacak"
                                   ~ " derecede bozulmuş.", konum));
    }
}
 
/* Verilen sayıları depolar.
 *
 * Bu işlevin de bir InputRange alması çok daha kullanışlı olurdu. */
Depo depola(int[] sayılar)
{
    auto depo = Depo(sayılar.length);
 
    foreach (konum, sayı; sayılar) {
        depo.ekle(konum, sayı);
    }
 
    return depo;
}
 
/* Deponun rasgele 'adet' adet düğümünü bozar. */
void boz(Depo depo, size_t adet)
{
    enforce(depo.length >= adet, format("%s düğümün %s adedini bozamam."));
 
    size_t rasgeleSağlamDüğümSeç()
    {
        while (true) {
            size_t konum = uniform(0, depo.length);
            if (depo.düğümler[konum].durum == Düğüm.Durum.sağlam) {
                return konum;
            }
        }
    }
 
    foreach (i; 0 .. adet) {
        const talihsiz = rasgeleSağlamDüğümSeç();
        depo.düğümler[talihsiz].durum = Düğüm.Durum.bozuk;
        depo.düğümler[talihsiz].veriler[] = 666;
    }
}
 
/* Depodaki verileri döndürür.
 *
 * Bu işlev de bir OutputRange alarak daha kullanışlı olabilirdi. */
int[] depodanOku(Depo depo)
{
    int[] sonuç;
 
    foreach (konum; 0 .. depo.length) {
        sonuç ~= depo.oku(konum);
    }
 
    return sonuç;
}
 
/* n'nin k'li kombinasyonunu hesaplar. */
T kombinasyon(T)(T n, T k)
    if (isIntegral!T)
{
    enforce(n >= k, format("(%s,%s) kombinasyonu hesaplanamaz."));
 
    T sonuç = 1;
 
    import std.algorithm : min;
    k = min(k, n - k);
 
    foreach (i; n - k + 1 .. n + 1) {
        sonuç *= i;
    }
 
    foreach (i; 2 .. k + 1) {
        sonuç /= i;
    }
 
    return sonuç;
}
 
unittest
{
    assert(kombinasyon(1, 1) == 1);
    assert(kombinasyon(10, 1) == 10);
    assert(kombinasyon(10, 10) == 1);
    assert(kombinasyon(4, 2) == 6);
    assert(kombinasyon(100, 20) == kombinasyon(100, 80));
}
 
void main()
{
    enum bozukDüğümAdedi = 3;
    enum N = 20;
 
    if (bozukDüğümAdedi == 3) {
        /* Bu hesap yalnızca 3 bozuk düğüm durumunda doğrudur. */
        writefln("Hesaplanan kayıp olasılığı : %%%.5s",
                 100.0 * N / kombinasyon(N, 3));
    }
 
    enum deneyAdedi = 100_000;
    size_t veriKaybedilenDurum = 0;
 
    foreach (deney; 0 .. deneyAdedi) {
            /* 0'dan N'ye kadar sayılar depola. */
            auto depo = iota(N).array.depola;
 
            /* Rasgele düğümleri boz. */
            boz(depo, bozukDüğümAdedi);
 
        try {
            int[] sayılar = depodanOku(depo);
 
        } catch (Exception) {
            ++veriKaybedilenDurum;
        }
    }
 
    writefln("Deneyle bulunan kayıp oranı: %%%.5s",
             100.0 * veriKaybedilenDurum / deneyAdedi);
}
Ali
acehreli (Moderatör) #3
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu programda bir hata veya anlamadığım bir gariplik var. main içindeki N'yi 6 yapıyorum ve deney sonuçları beklenenden daha iyi çıkıyor! (%30 yerine %10 veri kaybı oluşuyor.)

Henüz çözemedim ama Depo.kopyaUzaklığı'nın değeriyle ilgili. N==6 olunca kopyaUzaklığı 2 oluyor. kopyaUzaklığı'nı Depo'nun kurucusunda elle 1 olarak sabitleyince deney sonuçları tekrar hesap ettiğim gibi %30 oluyor.

Hiç bir şey anlamıyorum. :)

Ali
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu konu benim için çok eğitici oldu. Amaç da oydu zaten. :)

Bu garipliğin nedenini sonunda anladım.

Buradaki amaç N adet veriyi üçer kopya olarak saklamak ve böylece düğüm kayıpları karşısında veri kaybı şansını azaltmaktı. Benim aklıma ilk gelen yöntem, her veriyi çaprazlama olarak kendi asıl düğümünde sıfırıncı veri konumuna, bir komşu düğümde birinci veri konumuna, ve iki komşu düğümde ikinci veri konumuna yerleştirmek oldu. Yani, N'nin 6 olduğu durumda 0'dan 5'e kadar 6 veriyi şöyle yerleştirmeyi düşünmüştüm:

düğümler: 0 1 2 3 4 5
          ===========
veri 0 -> 0 1 2 3 4 5
veri 1 -> 5 0 1 2 3 4
veri 2 -> 4 5 0 1 2 3

Üzerinde konuşmak kolay olsun diye de 0 numaralı düğüme 0 değerini, vs. yerleştirdim. Dikkat ederseniz, 0 verisi 0,0 dan sağ aşağıya doğru çaprazlama yazılmış. Sağ taraflarında yeterli komşuları olmayan 4 ve 5 verileri de tekrar başa dönüp 0 ve 1 verilerine yazılmışlar.

Tekrarlama pahasına, böylece bir veya iki düğüm bozulduğunda (kaybedildiğinde) hiç veri kaybetmiyoruz çünkü her veri üç farklı düğümde yaşıyor. Örneğin, bozuk olan düğümlerdeki verileri X ile gösteriyorum:

X 1 X 3 4 5
X 0 X 2 3 4
X 5 X 1 2 3

Görüldüğü gibi, 0'dan 5'e kadar bütün veriler yine de korunmuş durumdalar. Öte yandan, aradaki düğümü de bozduğumuzda 0'ın son kopyası da kaybedilmiş olur:

X X X 3 4 5
X X X 2 3 4
X X X 1 2 3

Yani, 0 verisinin hiç kopyası yok ama diğer beş veri okunabiliyor.

Şimdi burada bir karar vermek veya bir soru sormak gerek: Saklanan verilerden teki bile kaybedilmiş olsa bütün veri çöpe mi gidiyor yoksa geri kalanlar yine de kullanılabiliyor mu? Bunun cevabı programa göre değişir. Ben kendimce tek veri kaybında bile hepsi çöpe gitmiştir diye düşünüyorum.

Altının üçlü kombinasyonu 20 olduğundan 3 düğüm kaybı için 20 farklı durum düşünebiliriz. Bu durumlardan 6 tanesi 6 farklı verinin kaybolmasına neden olur:

  • 0 kaybedilir:
X X X 3 4 5
X X X 2 3 4
X X X 1 2 3

  • 1 kaybedilir:
0 X X X 4 5
5 X X X 3 4
4 X X X 2 3

  • 2 kaybedilir:
0 1 X X X 5
5 0 X X X 4
4 5 X X X 3

  • 3 kaybedilir:
0 1 2 X X X
5 0 1 X X X
4 5 0 X X X

  • 4 kaybedilir:
X 1 2 3 X X
X 0 1 2 X X
X 5 0 1 X X

  • 5 kaybedilir:
X X 2 3 4 X
X X 1 2 3 X
X X 0 1 2 X

Buraya kadar mantıklı. Tam bu kadarını anlamışken ve programı yazıp sonuçların da beklediğim gibi çıktıklarını görmüşken biraz daha gerçekçi olmaya karar verdim ve belki de bu düğümler örneğin gerçek hayattaki sunucuları ve diskleri temsil ediyorlardır diye düşündüm. Dolayısıyla, birisi bozulunca komşusunun bozulma olasılığı da yüksektir diye düşünüp verilerin kopyalarını bir komşu atlayarak yazmaya karar verdim:

düğümler: 0 1 2 3 4 5
          ===========
veri 0 -> 0 1 2 3 4 5
veri 1 -> 4 5 0 1 2 3
veri 2 -> 2 3 4 5 0 1

Görüldüğü gibi, 0 numaralı veri bu sefer birer düğüm atlayarak 0, 2, ve 4 düğümlerine yazılmış.

İşte şaşırtıcı sonucu da tam bu noktada aldım: Bir komşu atlayınca benim kabul ettiğim anlamdaki veri kaybı olasılığı 3 kat azaldı! Nasıl olabilirdi? Tabii ki veri kaybetmiş olmak için yine de üç düğüm kaybı gerekiyordu ve yine toplam 6 veri olduğuna göre 20 durum arasından 6 tanesi veri kaybına neden olmalıydı ama öyle olmuyordu!

Sonunda, yukarıdaki veri dağılımına biraz daha dikkatlice bakınca uyandım: Veri kopyalarını öyle dağıtınca 0, 2, ve 4 verileri aynı üç düğümü paylaşıyorlar. (Aynı biçimde; geri kalan 1, 3, ve 5 verileri de geri kalan üç düğümü paylaşıyorlar.)

Dolayısıyla, 0'ın kaybedildiği durum 2 ve 4'ün kaybedildiği durumları da kapsıyor ve 1'in kaybedildiği durum da 3 ve 5'in kaybedildiği durumları kapsıyor:

  • 0, 2, ve 4 kaybedilir:
X 1 X 3 X 5
X 5 X 1 X 3
X 3 X 5 X 1

  • 1, 3, ve 5 kaybedilir:
0 X 2 X 4 X
4 X 0 X 2 X
2 X 4 X 0 X

Hepsi o: Veri kaybına neden olan başka durum yok. Sonuçta, 20 durum arasında veri kaybedilen yalnızca 2 durum oluyor! :) Bir anlamda, daha önceden üç farklı durumun verdiği hasar tek durumda yoğunlaştırılmış diye düşünülebilir.

Programı hep yan yana üç düğüm 3 veriyi paylaşacak biçimde değiştireceğim:

düğümler: 0 1 2 3 4 5
          ===========
veri 0 -> 0 1 2 3 4 5
veri 1 -> 2 0 1 5 3 4
veri 2 -> 1 2 0 4 5 3

Üçe tam bölünmeyen durumlarda da sona kalan 4 veya 5 düğümü ise ilk programdaki kurala göre dağıtacağım. Aşağıda 0, 1, ve 2 ortak çalışıyorlar ve geri kalan dördü de kendi aralarında ortaklar:

düğümler: 0 1 2 3 4 5 6
          =============
veri 0 -> 0 1 2 3 4 5 6
veri 1 -> 2 0 1 6 3 4 5
veri 2 -> 1 2 0 5 6 3 4

Ali
acehreli (Moderatör) #5
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu da son hali:
import std.stdio;
import std.random;
import std.range;
import std.exception;
import std.traits;
import std.conv;
 
enum veriKopyaAdedi = 3;
 
/* Deponun düğümleri birden fazla sayıda veri saklayabiliyorlar. Düğümün
 * sağlam mı yoksa bozuk mu olduğu anlaşılabiliyor. (Bir enum yerine
 * std.digest.md modülündeki MD5 gibi bir olanaktan yararlanmak daha yakışıklı
 * olabilirdi. :) ) */
struct Düğüm
{
    enum Durum { bozuk, sağlam }
 
    Durum durum = Durum.bozuk;
 
    /* int yerine veri türünü şablon parametresi olarak almak daha kullanışlı
     * olurdu. */
    int[veriKopyaAdedi] veriler;
}
 
/* Depolama ortamındaki bozukluklara karşı güvenliği arttırabilmek için her
 * veriyi üç farklı düğümde "çaprazlama olarak" depolar: Kendi konumunun
 * veri[0]'ı, bir sonraki konumun veri[1]'i, ve iki sonraki konumun veri[2]'si
 * olarak.
 *
 * Normalde, veriler hep 3 komşu düğüm tarafındanpaylaşılırlar. Düğümlerin
 * adedinin veriKopyaAdedi'ne tam olarak bölünemediği durumlarda ise sondaki
 * (veriKopyaAdedi + (düğümler.length % veriKopyaAdedi)) adet düğüm verilerini
 * paylaşırlar. */
struct Depo
{
    Düğüm[] düğümler;
 
    /* Verileri her komşu üçlü gruba paylaştırdıktan sonra en sondaki grup
     * üçten daha geniş olabilir. Bu değişkenler son grubun nerede olduğu ve
     * genişliği bilgisini tutuyorlar. */
    size_t sonGrupKonumu;
    size_t sonGrupGenişliği;
 
    /* Belirtilen uzunlukta boş bir depo oluşturur. */
    this(size_t uzunluk)
    {
        enforce(uzunluk >= veriKopyaAdedi,
                format("Kolaylık olsun diye en az %s düğüm gerekiyor.",
                       veriKopyaAdedi));
 
        düğümler.length = uzunluk;
 
        foreach (ref düğüm; düğümler) {
            düğüm.durum = Düğüm.Durum.sağlam;
        }
 
 
        /* En son paylaşım grubunun genişliği veriKopyaAdedi'nden fazla
         * olabilir. */
        const sonaKalanAdet = düğümler.length % veriKopyaAdedi;
        this.sonGrupGenişliği = veriKopyaAdedi + sonaKalanAdet;
        this.sonGrupKonumu = düğümler.length - sonGrupGenişliği;
    }
 
    @property size_t length() const pure nothrow
    {
        return düğümler.length;
    }
 
    string toString() const
    {
        string sonuç;
 
        foreach (kopya; 0 .. Düğüm.veriler.length) {
            foreach (düğüm; düğümler) {
                sonuç ~= (düğüm.durum == Düğüm.Durum.bozuk
                          ? "X"
                          : düğüm.veriler[kopya].to!string)
                         ~ ' ';
            }
 
            sonuç ~= '\n';
        }
 
        return sonuç;
    }
 
    /* Konumun geçerli olduğunu denetleyen özel bir işlev. */
    private void konumDenetle(size_t konum) const pure
    {
        enforce(length > konum, format("%s uzunluğundaki depoda %s konumu"
                                       ~ " geçersiz.", length, konum));
    }
 
    /* Belirtilen konumdaki verinin belirtilen kopyasının konumunu
     * bildirir. */
    private size_t kopyaKonumu(size_t konum, size_t kopyaNumarası) const
    in {
        assert(konum < length);
        assert(kopyaNumarası < Düğüm.veriler.length);
 
    } out(sonuç) {
        assert(sonuç < length);
 
    } body {
        /* Bu konumdaki verinin kendi paylaşım grubunun başı ve genişliği. (En
         * sondaki grup daha geniş olabilir. */
        const paylaşımGrubuBaşı = (konum >= sonGrupKonumu
                                   ? sonGrupKonumu
                                   : (konum / veriKopyaAdedi) * veriKopyaAdedi);
        const paylaşımGrubuGenişliği = (konum >= sonGrupKonumu
                                        ? sonGrupGenişliği
                                        : veriKopyaAdedi);
 
        /* Bu kopyanın kendi grubu içindeki konumu. */
        const grupİçiKonum = ((konum - paylaşımGrubuBaşı + kopyaNumarası)
                              % paylaşımGrubuGenişliği);
 
        return paylaşımGrubuBaşı + grupİçiKonum;
    }
 
    /* Veriyi belirtilen konuma yerleştirir.
     *
     * Hm. Konumu kullanıcı vermese ve depo gittikçe büyüse daha kullanışlı
     * olabilirdi. Problemin çözümüyle ilgisi olmayan bu kadar farklı bir
     * konuya dallanmasam da olur. :) */
    void ekle(size_t konum, int veri)
    {
        konumDenetle(konum);
 
        /* Veriyi birden fazla kopya olarak birden fazla düğüme yaz. */
        foreach (kopya; 0 .. Düğüm.veriler.length) {
            const düğümNumarası = kopyaKonumu(konum, kopya);
            düğümler[düğümNumarası].veriler[kopya] = veri;
        }
    }
 
    /* Belirtilen konumdaki veriyi okur. */
    int oku(size_t konum) const
    {
        konumDenetle(konum);
 
        /* Veriyi gerekiyorsa başka düğümlerdeki kopyalarından da okumaya
         * çalış. */
        foreach (kopya; 0 .. Düğüm.veriler.length) {
            const düğümNumarası = kopyaKonumu(konum, kopya);
 
            if (düğümler[düğümNumarası].durum == Düğüm.Durum.sağlam) {
                return düğümler[düğümNumarası].veriler[kopya];
            }
        }
 
        /* Buraya geldiysek bu konum için sağlam kopya bulamadık demektir. */
        throw new Exception(format("Depo, %s numaralı veriyi okuyamayacak"
                                   ~ " derecede bozulmuş.", konum));
    }
}
 
/* Verilen sayıları depolar.
 *
 * Bu işlevin de bir InputRange alması çok daha kullanışlı olurdu. */
Depo depola(const int[] sayılar)
{
    auto depo = Depo(sayılar.length);
 
    foreach (konum, sayı; sayılar) {
        depo.ekle(konum, sayı);
    }
 
    return depo;
}
 
/* Deponun rasgele 'adet' adet düğümünü bozar. */
void boz(Depo depo, size_t adet)
{
    enforce(depo.length >= adet, format("%s düğümün %s adedini bozamam."));
 
    /* Sağlam düğüm bulana kadar düğüm seçer. */
    size_t rasgeleSağlamDüğümSeç()
    {
        while (true) {
            const size_t konum = uniform(0, depo.length);
            if (depo.düğümler[konum].durum == Düğüm.Durum.sağlam) {
                return konum;
            }
        }
    }
 
    foreach (i; 0 .. adet) {
        const talihsiz = rasgeleSağlamDüğümSeç();
        depo.düğümler[talihsiz].durum = Düğüm.Durum.bozuk;
        depo.düğümler[talihsiz].veriler[] = 666;
    }
}
 
/* Depodaki verileri döndürür.
 *
 * Bu işlev bir OutputRange alsa daha kullanışlı olabilirdi. */
int[] depodanOku(Depo depo)
{
    int[] sonuç;
 
    foreach (konum; 0 .. depo.length) {
        sonuç ~= depo.oku(konum);
    }
 
    return sonuç;
}
 
/* n'nin k'li kombinasyonunu hesaplar. */
T kombinasyon(T)(T n, T k)
    if (isIntegral!T)
{
    enforce(n >= k, format("C(%s,%s) kombinasyonu hesaplanamaz."));
 
    T sonuç = 1;
 
    /* Çarpma işleminde taşma olasılığını azaltmak için k'nin küçük olduğu
     * durumu hesaplayacağız. (Çünkü örneğin, C(1000,990) ile C(1000,10)
     * aynıdır.) */
    import std.algorithm : min;
    k = min(k, n - k);
 
    foreach (i; n - k + 1 .. n + 1) {
        sonuç *= i;
    }
 
    foreach (i; 2 .. k + 1) {
        sonuç /= i;
    }
 
    return sonuç;
}
 
unittest
{
    assert(kombinasyon(1, 1) == 1);
    assert(kombinasyon(10, 1) == 10);
    assert(kombinasyon(10, 10) == 1);
    assert(kombinasyon(4, 2) == 6);
    assert(kombinasyon(100, 20) == kombinasyon(100, 80));
}
 
void main()
{
    enum bozukDüğümAdedi = 3;
    enum N = 21;
 
    writefln("Toplam bozuk düğüm kombinasyonu (C(%s,%s) değeri): %s",
             N, bozukDüğümAdedi, kombinasyon(N, bozukDüğümAdedi));
    /* Bu hesap yalnızca tam bölünen durumlarda tam doğru ama olsun. */
    writefln("Veri kaybına neden olacak yaklaşık durum adedi: %s",
             N / veriKopyaAdedi);
    writefln("Hesaplanan veri kaybı oranı: %%%.5s",
             100.0 * N / veriKopyaAdedi / kombinasyon(N, bozukDüğümAdedi));
 
    enum deneyAdedi = 100_000;
    size_t veriOkunabilenDurum = 0;
    size_t veriKaybedilenDurum = 0;
 
    foreach (deney; 0 .. deneyAdedi) {
        /* 0'dan N'ye kadar sayılar depola. */
        const sayılar = iota(N).array;
        auto depo = sayılar.depola;
 
        /* Rasgele düğümleri boz. */
        boz(depo, bozukDüğümAdedi);
 
        try {
            const çekilenSayılar = depodanOku(depo);
            ++veriOkunabilenDurum;
            assert(çekilenSayılar == sayılar);
 
        } catch (Exception hata) {
            ++veriKaybedilenDurum;
        }
    }
 
    assert(veriOkunabilenDurum + veriKaybedilenDurum == deneyAdedi);
 
    writefln("Deneyle bulunan kayıp oranı: %%%.5s",
             100.0 * veriKaybedilenDurum / deneyAdedi);
}
Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 06:04:24 (UTC -08:00)