Forum: D Programlama Dili RSS
Sayarak sıralama
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ı: Sayarak sıralama
Dün D.learn haber grubuna sayarak sıralama[1] yöntemini aralıklarla gerçekleştirmeyle ilgili bir soru gelmişti.

Sayarak sıralama çok akıllıca bir yöntem ama özellikle elemanların alabildikleri değer aralığı küçük olduğu durumlara uygun. Örneğin, bir milyon değerimiz var ama bunların hepsinin 0 ve 10 arasında olduğunu biliyoruz.

Normal sıralama uyguladığımızda N log(N) adet işlem gerekir. Örneğin, N'nin bir milyon olduğun durumda kabaca 20 milyon adım gerekir. (Logaritmayı 2 tabanında alınca log(1_000_000) kabaca 20'dir.)

Sayarak sıralama şöyle işliyor:

  • Farklı eleman değerleri uzunlukta bir dizi oluştur. (0-10 aralığı için 11 elemanlı dizi.)

  • Diziyi baştan sona ilerleyerek her değerden kaç adet olduğunu o diziye yerleştir. (Örneğin, adetler[0] elemanı 0 değerinden kaç adet bulunduğunun tutsun.)

  • Şimdi o dizi üzerinde ilerleyerek her değerden o kadar adet üret. (Bunu tembel aralık olarak yapabiliriz, aynı dizi üzerine yazarak yapabiliriz, vs.)

Bu algoritmanın karmaşıklığı ise N + M kadar küçük oluyor. Yani bir milyon + 11. Yirmi kere daha az işlem yapmış olduk! :)
import std.stdio;
import std.conv;
import std.datetime;
import std.random;
import std.algorithm;
import std.range;
 
enum toplamEleman = 1_000_000;
enum toplamDeğer = 100;
 
/* Bu 'version', sayarak sıralama işlevinde aralık mı yoksa foreach mi
 * kullanılacağını belirler. Bu satırı çıkartırsanız sayarak sıralama daha
 * hızlı işliyor.  */
version = aralıkKullanarak;
 
void main() {
    // Rasgele elemanlarla dolu bir dizi
    auto dizi = generate(() => uniform(0, toplamDeğer))
                .take(toplamEleman)
                .array;
 
    // Haksızlık olmasın diye iki algoritmaya farklı dizi veriyoruz
    auto diziNormal = dizi.dup;     // Normal sort'un kullanacağı dizi
    auto diziSayarak = dizi.dup;    // Sayarak sıralamanın kullanacağı dizi
 
    // İşlem sürelerini ölçüyoruz
    const ölçümler = benchmark!(() => normalSortİle(diziNormal),
                                () => sayarakSıralamaİle(diziSayarak))(100);
 
    writeln("algorithm.sort ile  : ", to!Duration(ölçümler[0]));
    writeln("Sayarak sıralama ile: ", to!Duration(ölçümler[1]));
}
 
auto normalSortİle(int[] dizi) {
    dizi.sort();
 
    /* Ölçümler anlamlı olsun diye bütün elemanları kullanalım. */
    return dizi.sum;
}
 
auto sayarakSıralamaİle(int[] dizi) {
    // Her değerden kaç adet bulunduğunu tutan dizi
    auto adetler = new uint[toplamDeğer];
 
    /* adetler dizisini dolduruyoruz. Bunun sonucunda örneğin adetler[0]
     * elemanı, dizide kaç adet 0 değeri bulunduğunu gösterecek. */
    dizi.each!(e => ++adetler[e]);
 
    version (aralıkKullanarak) {
 
        /* Her değerden kaç adet varsa o değeri o kadar kere tekrarlıyoruz.
         * Her ne kadar şık olsa da, bu yöntem dmd ile derlendiğinde aşağıdaki
         * 'foreach'li yöntemden daha yavaş kalıyor. */
        auto sonuç = adetler
                     .enumerate
                     .map!(ç => ç[0].repeat(ç[1]))
                     .joiner;
 
        /* Ölçümler anlamlı olsun diye bütün elemanları kullanalım. (Yoksa bu
         * tembel aralığın işlemleri hiç işletilmezdi.) */
        return sonuç.sum;
 
    } else {
 
        /* Yukarıdaki 'enumerate'in ne işe yaradığını gösterebilmek için
         * tembel aralık yöntemi yerine aşağıdaki gibi bir foreach de
         * kullanabiliriz. Bu yöntemde dizinin kendisini sıralayacağız. */
 
        size_t i = 0;    // Asıl dizi üzerindeki indeks
 
        /* Dikkat ederseniz, aşağıdaki 'değer' aslında 'adetler' üzerindeki
         * sayaçtır. */
        foreach (int değer, adet; adetler) {
            // O değerden 'adet' kadar yerleştiriyoruz
            foreach (_; 0 .. adet) {
                dizi[i] = değer;
                ++i;
            }
        }
 
        return dizi.sum;
 
    }  /* version (aralıkKullanarak) else */
}
dmd'ye -O -inline -noboundscheck seçeneklerini verince oluşan programın benim ortamımdaki bir çıktısı:

algorithm.sort ile  : 7 secs, 37 ms, 491 μs, and 3 hnsecs
Sayarak sıralama ile: 1 sec, 703 ms, 90 μs, and 6 hnsecs

Bir milyon eleman ve 100 farklı değer için yedi kat daha hızlı. Hiç fena değil! :)

Ali

[1] https://tr.wikipedia.org/wiki/Sayarak_s%C4%B1ralama
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:
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-20, 01:15:25 (UTC -08:00)