Forum: Ders Arası RSS
The Algorithm Design Manual, problem 1-28
/ ve * kullanmadan bölme
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 1-28
/ ve * işleçlerini kullanmadan tamsayı bölme işlemi gerçekleştiren bir işlev yazınız. Bu işi hızlı yapsın.

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ı
Bu işi "hızlı yapmayan" çözüm herhalde şöyle olur:
import std.exception;
 
int böl(int sayı, int bölen)
{
    enforce(bölen != 0, "Sıfıra bölünemez.");
 
    // Kolaylık olsun diye artı değerlerle çalışacağız ama sonucun işaretini
    // de unutmayacağız.
    bool eksi_mi = false;
 
    if (sayı < 0) {
        sayı = -sayı;
        eksi_mi = !eksi_mi;
    }
 
    if (bölen < 0) {
        bölen = -bölen;
        eksi_mi = !eksi_mi;
    }
 
    int bölüm = 0;
    int toplam = 0;
 
    // Toplaya toplaya sayıya erişmeye çalışacağız. Kaç kere toplamışsak sonuç
    // odur.
    while (toplam < sayı) {
        ++bölüm;
        toplam += bölen;
    }
 
    // Sayıyı tam tutturamadıysak tamsayı bölmesinden kalanı silmek gerek.
    const mutlakSonuç = bölüm - (toplam != sayı);
 
    return eksi_mi ? -mutlakSonuç : mutlakSonuç;
}
 
unittest
{
    assertThrown(böl(2, 0));
 
    assert(böl(0, 1) == 0);
    assert(böl(4, 2) == 2);
    assert(böl(5, 2) == 2);
    assert(böl(333, 3) == 111);
 
    assert(böl(-4, 2) == -2);
    assert(böl(4, -2) == -2);
    assert(böl(-5, 2) == -2);
 
    assert(böl(-4, -2) == 2);
}
 
void main()
{}
Yukarıdaki programın sorunu, sonucun büyüklüğü ile doğru orantılı zaman almasıdır! Bakalım:
void main()
{
    import std.stdio;
    import std.datetime;
 
    auto ölçümler = benchmark!(() { böl(10_000_000, 1); },
                               () { böl(40_000_000, 1); })(100);
 
    foreach (i, ölçüm; ölçümler) {
        writefln("süre %s: %6s ms", i, ölçüm.to!("msecs", int));
    }
}
Çıktısı dört katı büyük sonucu hesaplamak için dört katı zaman gerektiğini gösteriyor:

süre 0:    805 ms
süre 1:   3187 ms


Yani, bu algoritmanın karmaşıklığı O(sayı/bölen) kadar.

Şimdiki amaç "bu işi hızlı yapmak". :)

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ı
Çözdüm. :)

  • Önceki çözümün tersine, 'toplam' adında bir değişkene eklemek yerine elimdeki sayıyı eksilte eksilte sıfıra gitmek daha mantıklı geldi.

  • Önceki çözümün yavaşlığının nedeni, ekleme miktarı olarak hep bölen değeri kullanmasıydı. Bu çözüm, kendi miktarını kullanmadan önce onun iki katını kullanıyor. Örneğin, 10'a böleceği zaman sayının içinde kaç tane 10 olduğuna bakmadan önce kaç tane 20 olduğuna bakıyor. Özyinelemeli olarak, 20'ye bakmadan önce de kaç tane 40 olduğuna bakıyor, vs.

Sonuçta O(log(sayı/bölen)) karmaşıklığında bir çözüm bulunmuş oldu.
import std.exception;
 
/* Sayıdan miktar kadar değer eksiltir ve kaç kere eksilttiği bilgisini
 * döndürür. İşi bittiğinde 'sayı' parametresi de değişmiştir. */
private int eksilt(ref int sayı, int miktar)
{
    /* Özyinelemeyi sonlandıran koşul. */
    if (sayı < miktar) {
        return 0;
    }
 
    /* Kendi işimize bakmadan önce iki katı büyük miktarın kaç kere
     * eskiltildiğini sayalım. */
    const büyükEksiltilen = eksilt(sayı, miktar + miktar);
 
    /* Şimdi, büyük miktar eksilterek elde ettiğimiz büyük sonuca kendi
     * miktarımızı eksilterek elde edeceğimiz yavaş sonucu ekleyeceğiz. */
 
    int eksiltilen = 0;
 
    while (sayı >= miktar) {
        sayı -= miktar;
        ++eksiltilen;
    }
 
    /* Büyük miktar kendi miktarımızın iki katı olduğuna göre bizden istenen
     * miktarın sonucuna onu iki kere eklemeliyiz. */
    return büyükEksiltilen + büyükEksiltilen + eksiltilen;
}
 
int böl(int sayı, int bölen)
{
    enforce(bölen != 0, "Sıfıra bölünemez.");
 
    // Kolaylık olsun diye artı değerlerle çalışacağız ama sonucun işaretini
    // de unutmayacağız.
    bool eksi_mi = false;
 
    if (sayı < 0) {
        sayı = -sayı;
        eksi_mi = !eksi_mi;
    }
 
    if (bölen < 0) {
        bölen = -bölen;
        eksi_mi = !eksi_mi;
    }
 
    const mutlakSonuç = eksilt(sayı, bölen);
 
    return eksi_mi ? -mutlakSonuç : mutlakSonuç;
}
 
unittest
{
    import std.conv;
    assertThrown(böl(2, 0));
 
    assert(böl(0, 1) == 0);
    assert(böl(4, 2) == 2);
    assert(böl(5, 2) == 2);
    assert(böl(333, 3) == 111);
 
    assert(böl(-4, 2) == -2);
    assert(böl(4, -2) == -2);
    assert(böl(-5, 2) == -2);
 
    assert(böl(-4, -2) == 2);
}
 
void main()
{
    import std.stdio;
    import std.datetime;
 
    auto ölçümler = benchmark!(() { böl(10_000_000, 1); },
                               () { böl(40_000_000, 1); })(100);
 
    foreach (i, ölçüm; ölçümler) {
        writefln("süre %s: %6s ms", i, ölçüm.to!("msecs", int));
    }
}
Daha önce saniyeler süren main içindeki hesaplar artık milisaniye cinsinden ölçülemeyecek kadar küçük: :)

süre 0:      0 ms
süre 1:      0 ms

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-18, 00:36:47 (UTC -08:00)